Pith. sign in

REVIEW 4 major objections 5 minor 34 references

Lower Bounds for Non-adaptive Local Computation Algorithms

T0 review · 4 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that any non-adaptive local computation algorithm that constant-approximates maximum matching or minimum vertex cover, or computes a maximal independent set, requires Δ^{Ω(log Δ / log log Δ)} queries.

desk verdict Important and likely correct lower bound for non-adaptive LCAs, but the proof as written skips a load-bearing reduction from observed trees to degree sequences and leaves the MIS section as a sketch. read the letter →

arxiv 2505.00915 v1 pith:LX4QH3H3 submitted 2025-05-01 cs.DS

Amir Azarmehr , Soheil Behnezhad , Alma Ghafari , Madhu Sudan This is my paper · ORCID
classification cs.DS MSC 68Q2568W2005C70
keywords non-adaptiveLCAlocalcomputationalgorithmsmaximummatchingminimumvertexcovermaximalindependentsetlowerbounddistributedMPC
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Local Computation Algorithms (LCAs) answer queries about a global solution by inspecting a small part of the input; a non-adaptive LCA must fix its entire probe pattern in advance. The paper proves that any LCA of this kind that constant-approximates maximum matching or minimum vertex cover, or outputs a maximal independent set, needs $Δ^{{Ω(log Δ / log log Δ)}}$ queries, where Δ is the maximum degree. This matches, up to constants in the exponent, the query count of the best known non-adaptive LCAs obtained from distributed algorithms, and it is the first separation from adaptive LCAs, which solve the same problems with poly(Δ) queries. A corollary is that a whole family of potential faster massively parallel algorithms for approximate matching—those built from non-adaptive LCAs—is ruled out.

What carries the argument

The load-bearing object is a blueprint made of two isomorphic recursively defined cluster trees (clusters of vertices, edges labeled by degrees), a dummy cluster attached to every cluster, and a perfect matching between corresponding clusters of the two trees. The final graph is obtained by replacing each blueprint edge with a random regular bipartite graph between the two clusters. Two facts carry the argument: (1) random bipartite subgraphs make the explored subgraph a tree with high probability, so the algorithm's observation is just a degree sequence; and (2) a coupling between paths starting from a significant and a misleading edge fails only when the label sequence is distinguishing, and any distinguishing sequence must contain a subsequence of r small labels $δ^{0}$, $δ^{1}$, ..., $δ^{{r-1}}$, an event whose probability is at most (ℓ/$δ^{{(r+1)/2}}$)^r ≤ 1/$κ^{2}$. The dummy cluster guarantees that walks longer than r log Δ steps are absorbed with probability close to 1, so only moderately long walks matter.

What would settle it

Evaluate the paper's hard distribution at a concrete value such as Δ=$2^{{20}}$ with query count $Δ^{{0.1 log Δ / log log Δ}}$, and measure the total variation distance between the degree sequences observed from a significant edge and from a misleading edge; a constant distance would refute the central indistinguishability claim, as would any non-adaptive LCA with $Δ^{{o(log Δ / log log Δ)}}$ queries that constant-approximates maximum matching on all bounded-degree graphs.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: any possibly randomized non-adaptive LCA that returns an O(1) approximation of maximum matching, an O(1) approximation of minimum vertex cover, or a maximal independent set with constant probability requires $Δ^{{Ω(log Δ / log log Δ)}}$ queries. The proof constructs a family of graphs in which each edge is either significant (part of a large matching) or misleading (belongs to a sparse set), and shows via a coupling over the query tree that the degree sequence observed by any non-adaptive LCA is nearly the same whether the queried edge is significant or misleading. Hence a constant approximation to the maximum matching cannot include a constant fraction of significant edges without also accepting misleading edges. The same construction, with minor modifications, handles vertex cover and maximal independent set.

Load-bearing premise

The load-bearing premise is that a non-adaptive LCA's observation can be reduced to the degree sequence of the explored tree; if random vertex labels ever carried extra distinguishing information, the proof's total-variation bound would not control the algorithm's success.

Editorial extensions

If this is right

  • The reduction from distributed algorithms to non-adaptive LCAs is optimal up to exponent constants for constant approximations of maximum matching, minimum vertex cover, and maximal independent set.
  • Adaptivity is strictly necessary for poly(Δ)-query LCAs for these problems: no non-adaptive algorithm can match the adaptive poly(Δ) upper bounds.
  • Any attempt to improve massively parallel algorithms for approximate matching cannot succeed by improving non-adaptive LCAs; the suggested LCA-to-MPC route is closed.
  • The lower bound holds for randomized non-adaptive LCAs as well, by the minimax principle applied to the deterministic construction.
  • The query-complexity threshold Δ^{Θ(log Δ / log log Δ)} is the exact frontier for non-adaptive LCAs for these problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The dummy-cluster trick—forcing every long random walk to hit an uninformative absorbing cluster with constant probability per step—might be a general recipe for strengthening radius-based distributed lower bounds into LCA lower bounds for other local problems.
  • If the coupling argument can be tightened, similar lower bounds may hold for exact maximum matching or for approximation ratios below some threshold, where adaptive LCAs are also less understood.
  • The paper's reduction of the algorithm's view to the degree sequence suggests that non-adaptive LCA lower bounds in general graphs reduce to understanding random labeled trees; defining a canonical label-free model might simplify future lower bounds.
  • One could test whether the MPC consequence is the real bottleneck: the same lower bound does not rule out faster MPC algorithms built from adaptive LCAs or from direct graph sparsification, so the open MPC problem remains open but is narrowed.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. This paper formalizes non-adaptive LCAs and proves a lower bound of Δ^{Ω(log Δ / log log Δ)} queries for any non-adaptive LCA that with constant probability computes an O(1)-approximation of maximum matching or minimum vertex cover, or a maximal independent set, where Δ is the maximum degree. The proof constructs a hard distribution based on a modified Kuhn-Moscibroda-Wattenhofer cluster-tree construction, adds dummy clusters to kill very long walks, and uses couplings over acyclic explored subgraphs in the style of recent sublinear-time lower bounds. The paper also proves a conditional result showing that a non-adaptive MVC LCA with query complexity Δ^{(log Δ)^{1-ε}} would yield an MPC algorithm for approximate maximum matching in (log n)^{1/2-Ω(ε)} rounds, and interprets Theorem 1.1 as ruling out that route.

Significance. If the lower bound is correct, it is the first separation between adaptive and non-adaptive LCAs for these problems, it matches the Parnas-Ron upper bound up to constants in the exponent, and it closes a concrete avenue toward improved MPC algorithms. The combination of the KMW cluster-tree construction with coupling-based sublinear-time lower bound techniques is a genuine technical contribution. The main caveat is that the proof as written contains a load-bearing reduction to degree-only observations that is not formally justified, and the MIS section is only a sketch; both need to be completed before the result can be considered established.

major comments (4)
  1. [§5, paragraph after Claim 5.4] The reduction to degree-only observation is not justified and is load-bearing. Definition 3.1 gives the algorithm the actual vertices returned by adjacency-list queries, so a non-adaptive LCA may use equality patterns among returned vertices, in particular whether a query returns the parent vertex. Claim 5.4 only shows that the induced subgraph on discovered vertices is a tree; it does not imply that the degree sequence determines the full observed query tree, because two explorations can have identical degree sequences while disagreeing on which query positions map to the same graph vertex. Claim 5.8 bounds the total variation of the degree sequence only, while Claim 5.1 transfers this to output probabilities, which requires the output to be a function of the degree sequence. The sentence "we can assume without loss of generality" after Claim 5.4 is the only support for this step, and it is not implied by the preceding claims. Please provide a formal proof that restricting to degree sequences is without loss, or strengthen the coupling to bound the total variation of the fully labeled observed query tree, including equality patterns.
  2. [§5, final paragraph of Claim 5.7] The proof defers a "careful treatment" of revisiting vertices, but this is exactly the place where the degree sequence fails to determine the observed query tree. The sketched fix asserts that special edges are traversed with probability at most 1/Δ, that special edges do not appear inside identical subtrees, and that traversing a special edge increases the maximum color by at most 1, and then asserts the coupling fails with probability at most 2/κ^2. These assertions are not proved, and the probability bound needs a careful accounting over all steps because the special edge is chosen from the remaining outgoing edges after one edge of a given label has been removed. Please supply the full proof of the special-edge handling, or otherwise prove that the coupling can be extended to the labeled query tree.
  3. [§7, Theorem 7.1 and surrounding text] The MIS lower bound is only a sketch. The text says "it can be shown" that the coupling maintains the invariant with probability 1-o(1), but no proof is given. This is not a routine adaptation: when the algorithm explores the line graph G' = L(G), the query graph can contain triangles corresponding to three edges sharing an endpoint in G, so the tree argument of Claims 5.3-5.4 does not apply directly to G'. The translation between queries in G' and queries in G also needs a formal treatment under the non-adaptive LCA model. Since MIS is one of the three problems in Theorem 1.1, this is load-bearing; please provide the full proof or explicitly state MIS as a corollary that depends on a completed coupling argument.
  4. [§8, Theorem 8.2 and Remark 8.3] Theorem 8.2 is stated for any non-adaptive LCA that O(1)-approximates minimum vertex cover, but the proof requires the stronger hypothesis that the LCA also outputs a matching of size within a constant of its vertex cover, as stated in Remark 8.3. As written, the implication in Theorem 8.2 does not follow from its stated hypothesis. Please restate the theorem to include the certificate assumption, or prove the implication without it. This does not affect the lower bound in Theorem 1.1, but it is the formal basis for the MPC motivation.
minor comments (5)
  1. [Title/abstract] The title contains a typo: "Local Computation Algorithm s" should be "Local Computation Algorithms".
  2. [§5, Claim 5.7] The denominator in the probability of taking a critical step is written as \bar d_r + Δ_r + 1, but Claim 4.16 states dB(C) = \bar d_r + Δ_r + 2 for non-leaf clusters; please reconcile the discrepancy.
  3. [§5, Claim 5.7] The quantity ℓ = 2 log κ uses log without specifying the base; the subsequent asymptotic estimates should state the base or use asymptotic notation throughout.
  4. [§5, Lemma 5.2] In the approximation-ratio display, the equality "= (r+1)/(δ-(r+1)) + 2ε + o(1)" should be an inequality "≤" because it follows from the upper bound on N in Claim 4.20.
  5. [§8, Claim 8.8] The final sentence says "the total size of the messages is bounded by M Q^2" but the preceding discussion bounds per-machine and total message sizes in terms of n and Q; please check whether M should be n or clarify the notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bound is derived from an independent graph construction, and the degree-only reduction after Claim 5.4 is a proof gap rather than a circular step.

full rationale

The paper's main theorem is a query-complexity lower bound proved against an explicit input distribution built from a modified Kuhn–Moscibroda–Wattenhofer construction. The derivation chain is: construct the hard distribution, show that the explored subgraph is a tree with high probability (Claim 5.4, with proof included), couple the explorations from significant and misleading edges (Claims 5.7 and 5.8), and conclude that each significant edge is output with probability o(1) (Claim 5.1). No parameter is fitted to the target lower bound, and the claimed impossibility is not defined in terms of itself. The self-citations to Behnezhad–Roghani–Rubinstein are methodological reuse of coupling and cycle-freeness arguments; the relevant proof for Claim 5.3 is included in the paper, and the KMW construction is external prior work that the paper modifies rather than merely relabels. The MPC application in Section 8 is explicitly conditional and does not feed back into the lower-bound proof. One passage does deserve note: immediately after Claim 5.4 the paper asserts 'we can assume without loss of generality that the algorithm computes the output based on the sequence of degrees.' This is an unproved reduction from the full observed query tree to the degree sequence, and it is load-bearing for transferring the degree-sequence coupling to the algorithm's decisions. However, this is a correctness or completeness gap in the proof, not circularity: it does not make the lower bound equivalent to its input, does not fit any parameter to the desired conclusion, and does not rely on a self-citation for its validity. Under the stated rules, circularity requires exhibiting a specific reduction by construction or a fitted parameter renamed as prediction; no such reduction is present. The honest finding is therefore no significant circularity, score 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new physical entities are posited; the dummy cluster and cluster tree are components of the mathematical construction, not unexplained entities. The free parameters are construction parameters chosen to make the lower bound go through; none are fitted to empirical data.

free parameters (3)
  • epsilon = c/6 where c is the target approximation ratio
    Chosen by hand to make the approximation-ratio upper bound in Lemmas 5.2 and 6.2 fall below c; it sets the dummy cluster size |D|=2*epsilon*N.
  • delta = solves Delta = delta^(r+1) + 1/epsilon
    Chosen so the constructed graph has maximum degree Delta and so delta >= (3/c + 1)(r+1), a condition used in the probability estimates of Claim 5.7 and the approximation-ratio calculations.
  • r = log Delta / log log Delta
    Depth parameter of the KMW cluster tree; set to match the exponent of the claimed lower bound. This is the same parameter used in the upper bound, not a fitted constant.
assumptions (5)
  • standard math Yao's min-max principle: deterministic lower bound on a fixed input distribution implies randomized lower bound.
    Used in the proof of Theorem 1.1 from Lemma 5.2 and Theorem 6.3.
  • domain assumption The input distribution of Definition 4.18 is well-defined: regular bipartite subgraphs with the stated degrees exist and the total vertex count satisfies n = Theta(N) with Delta = 2^{O(sqrt(log n log log n))}.
    The construction requires n to be super-polynomial in Delta; Theorem 1.1 does not state this regime explicitly.
  • domain assumption After conditioning on the explored subgraph being a tree, the algorithm's observation can be reduced to the degree sequence; random vertex labels carry no distinguishing information.
    Stated before Claim 5.7 as 'without loss of generality' but not formally proven; it is load-bearing for Claim 5.8.
  • domain assumption The label-based coupling (Definition 5.5) is a valid coupling of uniformly random neighbors in the randomly permuted adjacency lists.
    Relies on the random permutation of each adjacency list and the equality of outgoing label multisets for equal-degree clusters (Claim 4.17).
  • standard math For large Delta, delta >= (3/c + 1)(r+1) holds given Delta = delta^(r+1) + 1/epsilon and r = log Delta / log log Delta.
    Stated in Section 4.4; used in the approximation-ratio bounds of Lemmas 5.2 and 6.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lower Bounds for Non-adaptive Local Computation Algorithms." pith.science (2026). https://pith.science/paper/LX4QH3H3

@misc{pith2026250500915,
  author       = {Pith},
  title        = {Pith review of: Lower Bounds for Non-adaptive Local Computation Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LX4QH3H3}},
  note         = {Machine review of arXiv:2505.00915}
}
abstract

We study *non-adaptive* Local Computation Algorithms (LCA). A reduction of Parnas and Ron (TCS'07) turns any distributed algorithm into a non-adaptive LCA. Plugging known distributed algorithms, this leads to non-adaptive LCAs for constant approximations of maximum matching (MM) and minimum vertex cover (MVC) with complexity $\Delta^{O(\log \Delta / \log \log \Delta)}$, where $\Delta$ is the maximum degree of the graph. Allowing adaptivity, this bound can be significantly improved to $\text{poly}(\Delta)$, but is such a gap necessary or are there better non-adaptive LCAs? Adaptivity as a resource has been studied extensively across various areas. Beyond this, we further motivate the study of non-adaptive LCAs by showing that even a modest improvement over the Parnas-Ron bound for the MVC problem would have major implications in the Massively Parallel Computation (MPC) setting; It would lead to faster truly sublinear space MPC algorithms for approximate MM, a major open problem of the area. Our main result is a lower bound that rules out this avenue for progress. We prove that $\Delta^{\Omega(\log \Delta / \log \log \Delta)}$ queries are needed for any non-adaptive LCA computing a constant approximation of MM or MVC. This is the first separation between non-adaptive and adaptive LCAs, and already matches (up to constants in the exponent) the algorithm obtained by the black-box reduction of Parnas and Ron. Our proof blends techniques from two separate lines of work: sublinear time lower bounds and distributed lower bounds. Particularly, we adopt techniques such as couplings over acyclic subgraphs from the recent sublinear time lower bounds of Behnezhad, Roghani, and Rubinstein (STOC'23, FOCS'23, STOC'24). We apply these techniques to a very different instance, (a modified version of) the construction of Kuhn, Moscibroda and Wattenhoffer (JACM'16) from distributed computing.

Figures

Figures reproduced from arXiv: 2505.00915 by the authors.

Figure 4
Figure 4. [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 4.1
Figure 4.1. An illustration of the cluster tree (Definition 4.1) for r = 3. The shades represent the cluster colors. C0 is the root. The edge labels are displayed only in the direction away from the root. E0 := {(C0, C1)}, d(C0, C1) := 1, d(C1, C0) := δ, and the tree is rooted at C0. For r > 0, the tree Tr is constructed by adding some leaf clusters to Tr−1: 1. For every non-leaf cluster C ∈ Cr−1, a child cluster C ′ is created… view at source ↗
Figure 4.2
Figure 4.2. An example of distinguishing sequences, follow [PITH_FULL_IMAGE:figures/full_fig_p011_4_2.png] view at source ↗
Figures from the paper (2 more)
Figure 4.3
Figure 4.3. Figure 4.3: Another example of distinguishing sequences, fo [PITH_FULL_IMAGE:figures/full_fig_p012_4_3.png]
Figure 4.4
Figure 4.4. Figure 4.4: An illustration of the full blueprint (Definition 4.15) for r = 2. 4.3 Full Blueprint Finally, we present the full blueprint. Definition 4.15 (Full blueprint). The full blueprint includes 1. two instances of the cluster tree Tr, referred to as T (0) and T (1), and 2.…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 20 canonical work pages

  1. [1]

    Sp ace-Efficient Local Computation Algorithms

    Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Sp ace-Efficient Local Computation Algorithms. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Di screte Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , pages 1132–1139, 2012

    work page 2012

  2. [2]

    The stochast ic matching problem with (very) few queries

    Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochast ic matching problem with (very) few queries. In Vincent Conitzer, Dirk Bergemann, and Yilin g Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maast richt, The Netherlands, July 24-28, 2016 , pages 43–60. ACM, 2016. doi: 10.1145/2940716.2940769

    arXiv 2016

  3. [3]

    Lower bounds for maximal matchings and maximal ind ependent sets

    Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika¨ el Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal ind ependent sets. Journal of the ACM (JACM) , 68(5):1–30, 2021

    work page 2021

  4. [4]

    A distributed (2 + ε)- approximation for vertex cover in o(log ∆ / ε log log ∆) rounds

    Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Sc hwartzman. A distributed (2 + ε)- approximation for vertex cover in o(log ∆ / ε log log ∆) rounds. J. ACM , 64(3):23:1–23:11,

    work page

  5. [5]

    The locality of dis- tributed symmetry breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johan nes Schneider. The locality of dis- tributed symmetry breaking. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 20 12, pages 321–330. IEEE Computer Society, 2012. doi: 10.1109/FOCS.2012.60

    doi:10.1109/focs.2012.60 2012

  6. [6]

    Time-Optimal Sublinear Algorithms f or Matching and Vertex Cover

    Soheil Behnezhad. Time-Optimal Sublinear Algorithms f or Matching and Vertex Cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science , FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 873–884. IEEE, 2021

    work page 2021

  7. [7]

    Stochastic matching with few queries: (1- ε) approximation

    Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Stochastic matching with few queries: (1- ε) approximation. In Konstantin Makarychev, Yury Makaryche v, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, page...

    arXiv 2020

  8. [8]

    Sublinear time algorithms and complexity of approximate maximum matching

    Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinste in. Sublinear time algorithms and complexity of approximate maximum matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023, page 267–280, New York, NY, USA, 2023. Association for Computing Machinery. doi: 10.1145/356424 6.3585231

    work page doi:10.1145/356424 2023

Show all 34 references
  1. [9]

    Local computation algorithms for maximum matching: New lower bounds

    Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinste in. Local computation algorithms for maximum matching: New lower bounds. In 2023 IEEE 64th Annual Symposium on Foun- dations of Computer Science (FOCS) , pages 2322–2335. IEEE, 2023. 28

    2023

  2. [10]

    Approximating maximum matching requires almost quadratic time

    Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinst ein. Approximating maximum matching requires almost quadratic time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 444–454, 2024

    2024

  3. [11]

    Canonne and Tom Gur

    Cl´ ement L. Canonne and Tom Gur. An adaptivity hierarch y theorem for property testing. Comput. Complex. , 27(4):671–716, 2018. doi: 10.1007/S00037-018-0168-4

    2018 doi

  4. [12]

    Servedio, Li-Yang Tan, and Erik Wainga rten

    Xi Chen, Rocco A. Servedio, Li-Yang Tan, and Erik Wainga rten. Adaptivity is exponentially powerful for testing monotonicity of halfspaces. In Approximation, Randomization, and Combi- natorial Optimization. Algorithms and Techniques, APPROX /RANDOM 2017, August 16-18, 2017, Be...

    2017 doi

  5. [13]

    Served io, and Erik Waingarten

    Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Served io, and Erik Waingarten. Lower bounds for convexity testing. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, Janu ary 12-15, 2025 , pages 446–488, 2025. doi: 1...

    2025 doi

  6. [14]

    Monotonicity testing over general poset do mains

    Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhod nikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset do mains. In Proceedings on 34th An- nual ACM Symposium on Theory of Computing, May 19-21, 2002, Mont r´ eal, Qu´ ebec, Canada, page...

    2002

  7. [15]

    Local computation of maximal independe nt set

    Mohsen Ghaffari. Local computation of maximal independe nt set. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denv er, CO, USA, October 31 - November 3, 2022 , pages 438–449, 2022

    2022

  8. [16]

    Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local comp utation

    Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local comp utation. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Disc rete Algorithms, SODA 2019, San ...

    2019 doi

  9. [17]

    Th e power of adaptivity in quan- tum query algorithms

    Uma Girish, Makrand Sinha, Avishay Tal, and Kewen Wu. Th e power of adaptivity in quan- tum query algorithms. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , pages 1488–1497, 2024. doi: 10.1145/361826...

    2024

  10. [18]

    Three theorems regar ding testing graph properties

    Oded Goldreich and Luca Trevisan. Three theorems regar ding testing graph properties. In 42nd Annual Symposium on Foundations of Computer Science, FO CS 2001, 14-17 October 2001, Las Vegas, Nevada, USA , pages 460–469, 2001. doi: 10.1109/SFCS.2001.959922

    2001

  11. [19]

    On the benefits of adaptivity in p roperty testing of dense graphs

    Mira Gonen and Dana Ron. On the benefits of adaptivity in p roperty testing of dense graphs. In Approximation, Randomization, and Combinatorial Optimiza tion. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th Internati onal Workshop, RANDOM 2007, Pri...

    2007

  12. [20]

    Piotr Indyk, Eric Price, and David P. Woodruff. On the powe r of adaptivity in sparse recovery. In IEEE 52nd Annual Symposium on Foundations of Computer Science , FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011 , pages 285–294, 2011. doi: 10.1109/FOCS.2011.83. 29

    2011 doi

  13. [21]

    Space Efficient Approximation to Maximum Matching Size from Uniform Edge Sa mples

    Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi- Fard, and Jakab Tardos. Space Efficient Approximation to Maximum Matching Size from Uniform Edge Sa mples. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 , Salt Lake City, UT, USA, January 5-8,...

    2020

  14. [22]

    Karloff, Siddharth Suri, and Sergei Vassilvits kii

    Howard J. Karloff, Siddharth Suri, and Sergei Vassilvits kii. A Model of Computation for MapReduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on D iscrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2 010, pages 938–948. SIAM, 2010

    2010

  15. [23]

    Local computation: Lower and upper bounds

    Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer . Local computation: Lower and upper bounds. J. ACM , 63(2):17:1–17:44, 2016. doi: 10.1145/2742012

    2016 doi

  16. [24]

    Prop erly learning monotone functions via local correction

    Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan. Prop erly learning monotone functions via local correction. In 63rd IEEE Annual Symposium on Foundations of Computer Science , FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 75–86, 2022. doi: 10.1109/FOCS5445...

    2022

  17. [25]

    Locality in distributed graph algorith ms

    Nathan Linial. Locality in distributed graph algorith ms. SIAM J. Comput. , 21(1):193–201,

  18. [26]

    Round Compression for Parallel Graph A lgorithms in Strongly Sublinear Space

    Krzysztof Onak. Round Compression for Parallel Graph A lgorithms in Strongly Sublinear Space. CoRR, abs/1807.08745, 2018

    2018 arXiv

  19. [27]

    Approximating the Minimum V ertex Cover in Sublinear Time and a Connection to Distributed Algorithms

    Michal Parnas and Dana Ron. Approximating the Minimum V ertex Cover in Sublinear Time and a Connection to Distributed Algorithms. Theor. Comput. Sci. , 381(1-3):183–196, 2007

    2007

  20. [28]

    Sofya Raskhodnikova and Adam D. Smith. A note on adaptiv ity in testing properties of bounded degree graphs. Electron. Colloquium Comput. Complex. , TR06-089, 2006

    2006

  21. [29]

    F ast local computation algorithms

    Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. F ast local computation algorithms. In Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 223–238, 2011

    2011

  22. [30]

    An impro ved constant-time approximation algorithm for maximum matchings

    Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An impro ved constant-time approximation algorithm for maximum matchings. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda , MD, USA, May 31 - June 2, 2009 ,...

    2009

  23. [33]

    For every non-leaf cluster C∈C r−1, a child cluster C ′ is created with d(C, C′) = δr

  24. [34]

    Then, for every i ∈ {0, 1,

    For every leaf cluster C ∈C r−1, let pC be the parent of C and i∗ be the integer such that d(C, pC ) = δi∗ . Then, for every i ∈ {0, 1, . . . , r}−{ i∗} a child cluster C ′ is added with d(C, C′) = δi. For every new edge (C, C′) where C ′ is the leaf, we let the upward label d...

  25. [1992]

    doi: 10.1137/0221015

    doi

  26. [2017]

    doi: 10.1145/3060294

    doi

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.