Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

Guangxu Yang; Jiapeng Zhang; Xinyu Mao

REVIEW 4 major objections 4 minor 29 references

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

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

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

Pith's one-line read Every (k−1)-round protocol solving k-step pointer chasing with 2/3 accuracy on uniform inputs must send $\Omega(n/k + k)$ bits, matching the 1991 upper bound up to logarithmic factors.

desk verdict Genuinely new framework and near-optimal bound for pointer chasing, but a key monotonicity step in Claim 3.5 looks reversed; the proof needs repair before the result is established. read the letter →

arxiv 2411.10996 v1 pith:J2UFYHSI submitted 2024-11-17 cs.CC

Xinyu Mao , Guangxu Yang , Jiapeng Zhang This is my paper · ORCID

classification cs.CC MSC 68Q11

keywords pointerchasingcommunicationcomplexitygadgetlessliftingroundeliminationdensityincrementdistributionallowerboundsround-communicationtrade-off

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

This paper closes the main gap in the round-communication trade-off for the $k$-step pointer chasing problem. It establishes that any $(k-1)$-round deterministic protocol that errs with probability at most $1/3$ on uniform inputs must communicate $\Omega(n/k + k)$ bits, essentially matching the $O((n/k+k)\log n)$ upper bound from 1991, up to a logarithmic factor. The proof introduces gadgetless lifting, a framework that derives lower bounds for arbitrary protocols by first proving them for restricted protocols whose shared information is only coordinate-wise, then simulating general protocols by such restricted ones. This avoids two barriers of earlier techniques: the $k\log n$ loss typical of round elimination and the square-root loss typical of entropy-based information complexity arguments. The new lower bound carries over to randomized protocols and to applications such as direct-sum statements and local differential privacy.

What carries the argument

The central object is the decomposition-and-sampling process DS together with the density-restoring partition of Lemma 2.3. DS maintains a rectangle $A\times B$ inside a leaf of the protocol tree on which Alice's coordinates outside a fixed set $D_A$ and Bob's coordinates outside a fixed set $D_B$ remain $\gamma$-dense, and the current pointer $pt_{r-1}$ is constant. Each time the protocol's owner changes, the process splits the current rectangle according to the parity of the pointer's next coordinate and then applies the density-restoring partition; the size of the removed fixed-coordinate sets is tracked as the 'fixed size'. The key identity is Lemma 3.3, which bounds the protocol's accuracy by $n^{1-\gamma}/2 + n^{-\gamma}(k-1)\mathbb{E}[|D_A|+|D_B|]$, and Lemma 3.6, which bounds $\mathbb{E}[|D_A|+|D_B|]$ by $O(\mathrm{CC}(\Pi))$ via a density-increment telescoping argument. Together these produce the lower bound.

What would settle it

Recompute Claim 3.5: since $D_B^{(\ell-1)} \supseteq D_B$ holds pointwise, the printed chain $\Pr[E_\ell] \le n^{-\gamma}\mathbb{E}[|D_B^{(\ell-1)}|] \le n^{-\gamma}\mathbb{E}[|D_B|]$ cannot be right in that order. If the intended bound uses $\mathbb{E}[|D_B^{(\ell-1)}|]$ without the second inequality, or uses a different averaging that avoids comparing a larger set to a smaller one, then Lemma 3.3 may survive; re-running the telescoping density-increment argument with the corrected inequality would either confirm the $\Omega(n/k+k)$ bound or reveal a missing term.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a decomposition-and-sampling argument showing that accuracy and communication are linked through a quantity called the average fixed size. Starting from any $(k-1)$-round protocol, the process DS walks down the protocol tree while maintaining a rectangle on which the pointers up to the current round are fixed and the remaining 'alive' coordinates are dense in min-entropy. Conditioned on a certain 'bad' flag never being raised, the protocol's advantage on the resulting rectangle is at most $n^{1-\gamma}/2$; the probability that the flag is raised is charged to the expected number of fixed coordinates. A density-increment argument then shows that this average fixed size is at most $O(\mathrm{CC}(\Pi))$. Combining these bounds yields accuracy $\le 0.54 + O((k/n)\cdot\mathrm{CC}(\Pi))$, so any protocol with accuracy $2/3$ must have $\mathrm{CC}(\Pi) = \Omega(n/k + k)$. This is Theorem 1.2; by the standard minimax principle it gives the same lower bound for randomized $(k-1)$-round protocols, and the paper derives improved direct-sum and local-differential-privacy corollaries.

Load-bearing premise

The proof's central charge—that with little communication only few coordinates can be fixed, forcing any accurate protocol to pay in rounds—rests on Claim 3.5's bound on the probability that the 'bad' flag is raised; as printed, one inequality in that claim appears to have its direction reversed, and if that is a substantive error rather than a typo the accuracy-to-fixed-size connection does not go through.

Editorial extensions

If this is right

Every $(k-1)$-round randomized protocol for $\mathrm{PC}_k$ with error at most $1/3$ needs $\Omega(n/k+k)$ bits.
The new bound matches the 1991 upper bound up to a $\log n$ factor, shrinking a gap that had remained open for pointer chasing.
The direct-sum corollary improves the previous $\Omega(t n/k^3 - t k \log n)$ bound to $\Omega(t n/k^2 + t)$ for solving $t$ independent copies.
The local-differential-privacy corollary improves the sample-complexity lower bound for $(k-1)$-round sequentially interactive protocols solving pointer chasing.
Because the framework does not rely on round elimination or on information complexity, it offers a route around the square-root and $k\log n$ barriers that constrained earlier round-communication trade-offs.

Reading between the lines

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

Gadgetless lifting may apply to other problems that, like pointer chasing, are not liftable through a gadget, such as set pointer chasing and bipartite matching, where round elimination has known limitations.
A multiparty or number-in-hand version of the decomposition-and-sampling process could yield similar trade-offs for multiparty pointer chasing.
The upper-bound side still carries a $\log n$ factor; testing whether the parity-skip idea can be generalized for large $k$ would decide whether $O(n/k+k)$ communication without the $\log n$ is achievable.

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.

Desk Editor's Note

read the letter

One thing to know: this paper is worth engaging. The gadgetless lifting framework is a genuine new idea, and the main theorem—Ω(n/k + k) for (k−1)-round pointer chasing—would close the gap to Nisan–Wigderson up to log factors. The density increment argument in Lemma 3.6 is clean, and the applications follow naturally.

The soft spot is Claim 3.5. The proof bounds Pr[E_ℓ] by n^{−δ} E[|D_B^{(ℓ−1)}|], then concludes this is ≤ n^{−δ} E[|D_B|] "because D_B becomes smaller and smaller during the execution." But in Algorithm 1, D_B is updated by removing C_j, so it shrinks. Hence |D_B^{(ℓ−1)}| ≥ |D_B| pointwise, and the inequality has the wrong direction. This is not cosmetic: the union bound then yields n^{−δ} Σ_ℓ E[|D_B^{(ℓ−1)}|], which can be as large as (k−1)n^{1−δ}, too weak to imply the Ω(n/k + k) bound. Since Claim 3.5 supplies the second term in Lemma 3.3, the main theorem does not follow as written.

Could it be a typo? Possibly. If D_B were the set of already-fixed coordinates, which grows over time, the inequality direction would work. But that conflicts with the stated update rule and with the sentence "D_B becomes smaller." The authors need to clarify which convention is meant and repair the derivation. This is a load-bearing issue, but it looks fixable; the rest of the proof machinery is well-structured. Also, the extracted text I read is full of OCR artifacts, so some of this may be transcription, but the monotonicity statement is explicit.

Who is this for: communication complexity researchers, especially those working on round-communication tradeoffs and lifting theorems. They will get real value from the framework even if the proof needs revision.

Recommendation: send it to a serious referee. The core idea is important and the result is likely true. The referee should concentrate on Claim 3.5 and ask for a corrected proof or a clear explanation of the set convention.

Referee Report

4 major / 4 minor

Summary. The paper claims an Omega(n/k + k) communication lower bound for (k-1)-round deterministic protocols solving the k-step pointer chasing problem PC_k with success probability at least 2/3 under the uniform distribution, improving a previous Omega(n/k - k log n) bound. The proof introduces a framework called gadgetless lifting: a decomposition-and-sampling process DS walks down the protocol tree while maintaining a rectangle together with coordinate sets D_A and D_B, using density-restoring partitions to isolate structured sub-rectangles. The main lemmas relate the protocol's accuracy to the expected final size of D_A and D_B, and then bound that expected size by O(CC(Π)), from which the lower bound is derived. The paper also draws corollaries for direct-sum and local-differential-privacy settings.

Significance. If the proof is repaired, the result would be a substantial improvement: it nearly matches the Nisan--Wigderson upper bound up to a log n factor and demonstrates a new technique, gadgetless lifting, that may be useful beyond pointer chasing. The paper is self-contained except for the density-restoring partition lemma, whose proof is included; the argument does not assume the lower bound it aims to prove, and the only hand-chosen parameter delta is a proof parameter. The density-increment strategy is attractive and clearly motivated despite the technical problems listed below.

major comments (4)

[3.2, Claim 3.5] The proof of Claim 3.5 contains a monotonicity step in the wrong direction under the algorithm's own update rule. The text derives Pr[E_l] <= n^{-delta} E[|D_B^{(l-1)}|] and then concludes <= n^{-delta} E[|D_B|], with the justification that 'D_B becomes smaller and smaller during execution.' However, Algorithm 1 updates D_B as D_B := D_B \ C_j (line 30), so D_B^{(l-1)} is a superset of the final D_B pointwise; hence E[|D_B^{(l-1)}|] >= E[|D_B|], not <=. Since Claim 3.5 supplies the second term in Lemma 3.3, the accuracy bound that drives Theorem 1.2 does not follow from the written proof. If the intended convention is that D_B is the growing set of already-fixed coordinates, then the update rule and the sentence 'D_B becomes smaller' both conflict with that convention; either way the proof must be repaired.
[2.1, Lemma 2.3] The stated premise of Lemma 2.3 contradicts its conclusion. If every x in B agrees on the set D, then for any part B_i and any C_i subset of D, every x in B_i agrees on D \ C_i. The distribution F_i(D \ C_i) is therefore a point mass and cannot be delta-dense for nonempty D \ C_i. The proof in the appendix does not use this premise; it establishes a decomposition in which D is the set of coordinates that remain unfixed after removing C_i. As written, the invocation at Algorithm 1 line 14 is also invalid at initialization, because B = [n]^n and D_A = [n] do not satisfy the stated premise.
[3.1, Lemma 3.2 and initialization] The loop invariant (heart) as stated cannot hold at initialization. With D_A = D_B = [n] and B = C = [n]^n, there is no c_A in [n]^[n] such that x(D_A) = c_A for all x in B. Moreover, the proof later uses D_A and D_B in two incompatible ways: Claim 3.4 uses the density of F(p_{k-1}) when p_{k-1} is in D_A, which makes sense only if D_A is the set of alive (not yet fixed) coordinates, while Lemma 3.6 treats |D_A| + |D_B| as increasing with the number of fixed coordinates (w_i = |C_I| and sum w_i = |D_A| + |D_B|). The authors should fix a single convention and restate the invariants, the definition of 'fixed size' in Lemma 3.3, and the density accounting in Lemma 3.6 accordingly.
[3.2, Claim 3.4] The parity assumption in Claim 3.4 is inconsistent. The proof assumes k-1 is odd and then bounds Pr[x_A(p_{k-1}) mod 2 = f*]. If k-1 is odd, then k is even and p_k = x_B(p_{k-1}) by the definition of PC_k, so the relevant final value is Bob's, not Alice's. The displayed probability corresponds to the case k odd, which would require k-1 even. This parity mismatch needs to be corrected or the claim's proof must be adapted to the other case.

minor comments (4)

[Throughout] The text has numerous OCR/mechanical corruptions that should be cleaned: for example, 'avarage' in Lemma 3.3, 'F/a.pc/l.pc/s.pc/e.pc' in place of 'False', '/one.sup' in footnotes, and 'Widgerson' for 'Wigderson' in the references.
[3.3, Lemma 3.6] The step '2T + k <= 3T' uses k <= T, but only k-1 <= T is guaranteed. Replacing the constant 3 by, say, 4 fixes the calculation without changing the asymptotic conclusion.
[3.2, Claim 3.5] The random variable X_l used in the proof of Claim 3.5 is never defined in the text. The proof should define it explicitly (apparently the sampled value of the relevant pointer coordinate) before using it in the probability calculation.
[1.1] The conjecture that the lower bound is tight up to the log n factor is reasonable, but the proposed parity-based deterministic protocol for the k = Theta(log n) case is only sketched; a precise statement of the protocol and its communication cost would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the lower bound follows from an internal density-increment argument; self-citations are non-load-bearing.

full rationale

The main theorem (Theorem 1.2, restated as Theorem 3.1) is derived by combining Lemma 3.3 (accuracy vs average fixed size) and Lemma 3.6 (average fixed size is bounded by O(CC(Π))). Neither lemma defines its key quantity in terms of the target n/k + k bound. Claim 3.4 bounds accuracy inside a leaf rectangle via the δ-density invariant, and Lemma 3.6 tracks the potential D∞(R) = D∞(A(D_A)) + D∞(B(D_B)) through the iterations; this is a self-contained density-increment argument and does not presuppose the lower bound. Lemma 2.3 (density-restoring partition) is attributed to [GPW17], but its full proof is included in the appendix, so the paper does not import the result as an unverified black box. The citations to the authors' own prior work ([YZ24], and [LMM+22] which includes a co-author) appear only as background and inspiration for the restricted-protocol definition and for the lifting literature; no formal step in Section 3 invokes these self-citations as the reason the lower bound holds. The only substantive concern in the manuscript is not circularity but a possible proof error: in Claim 3.5 (Section 3.2), the chain Pr[E_ℓ] ≤ n^{-δ} E[|D_B^{(ℓ-1)}|] ≤ n^{-δ} E[|D_B|] uses the sentence 'D_B becomes smaller and smaller during the execution' in the wrong direction, since Algorithm 1 updates D_B := D_B \ C_j and hence |D_B^{(ℓ-1)}| ≥ |D_B| pointwise. If uncorrected, this would break Lemma 3.3, but that is a correctness/repair issue, not a reduction of the claimed lower bound to its own inputs. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors, and no known result is merely relabeled. Accordingly, the circularity score is 0.

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

No new primitive or physical entity is introduced. 'Gadgetless lifting' is a proof framework, not an entity with independent falsifiable evidence. The proof's only free parameter is the constant 0.1 inside δ.

free parameters (1)

δ (density threshold) = 1 − 0.1/log n
The constant 0.1 is chosen by hand to balance the density increment and the error terms in the proof. It is not fitted to data but is an ad hoc proof parameter.

assumptions (3)

standard math Density-restoring partition (Lemma 2.3)
Proven in the appendix via a greedy algorithm; originally from Göös, Pitassi, and Watson (2017).
domain assumption Protocols can be padded to exactly k rounds and communicate exactly CC(Π) bits on every input
Standard in communication complexity, stated in Section 2.2.
standard math Yao's minimax principle
Used to convert the deterministic distributional lower bound into a randomized lower bound in Corollary 1.3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing." pith.science (2026). https://pith.science/paper/J2UFYHSI

@misc{pith2026241110996,
  author       = {Pith},
  title        = {Pith review of: Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J2UFYHSI}},
  note         = {Machine review of arXiv:2411.10996}
}

read the original abstract

We prove an \Omega(n/k+k) communication lower bound on (k-1)-round distributional complexity of the k-step pointer chasing problem under uniform input distribution, improving the \Omega(n/k - k log n) lower bound due to Yehudayoff (Combinatorics Probability and Computing, 2020). Our lower bound almost matches the upper bound of O(n/k + k) communication by Nisan and Wigderson (STOC 91). As part of our approach, we put forth gadgetless lifting, a new framework that lifts lower bounds for a family of restricted protocols into lower bounds for general protocols. A key step in gadgetless lifting is choosing the appropriate definition of restricted protocols. In this paper, our definition of restricted protocols is inspired by the structure-vs-pseudorandomness decomposition by G\"o\"os, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24). Previously, round-communication trade-offs were mainly obtained by round elimination and information complexity. Both methods have some barriers in some situations, and we believe gadgetless lifting could potentially address these barriers.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 21 canonical work pages

[1]

Polynomial pass lower bounds for graph streaming algorithms

Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. In Proceedings of the 51st Annual ACM SIGACT Symposium on theory of computing , pages 265--276, 2019

work page 2019
[2]

How to compress interactive communication

Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 67--76, 2010

work page 2010
[3]

Direct products in communication complexity

Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct products in communication complexity. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 746--755. IEEE, 2013

work page 2013
[4]

Nearly optimal communication and query complexity of bipartite matching

Joakim Blikstad, Jan Van Den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Nearly optimal communication and query complexity of bipartite matching. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1174--1185. IEEE, 2022

work page 2022
[5]

Query-to-communication lifting for bpp using inner product

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting for bpp using inner product. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

work page 2019
[6]

An adaptivity hierarchy theorem for property testing

Cl \'e ment L Canonne and Tom Gur. An adaptivity hierarchy theorem for property testing. computational complexity , 27:671--716, 2018

work page 2018
[7]

Memory bounds for continual learning

Xi Chen, Christos Papadimitriou, and Binghui Peng. Memory bounds for continual learning. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 519--530. IEEE, 2022

work page 2022
[8]

Lower bounds on communication complexity

Pavol Duris, Zvi Galil, and Georg Schnitger. Lower bounds on communication complexity. In Proceedings of the sixteenth annual ACM symposium on Theory of computing , pages 81--91, 1984

1984

Show all 29 references

[9]

Some bounds on multiparty communication complexity of pointer jumping

Carsten Damm, Stasys Jukna, and Ji r \' Sgall. Some bounds on multiparty communication complexity of pointer jumping. Computational Complexity , 7:109--127, 1998

1998
[10]

Graph distances in the data-stream model

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM Journal on Computing , 38(5):1709--1727, 2009

2009
[11]

A simple lower bound for monotone clique using a communication game

Mikael Goldmann and Johan H stad. A simple lower bound for monotone clique using a communication game. Information Processing Letters , 41(4):221--226, 1992

1992
[12]

Lower bounds for quantile estimation in random-order and multi-pass streaming

Sudipto Guha and Andrew McGregor. Lower bounds for quantile estimation in random-order and multi-pass streaming. In Automata, Languages and Programming: 34th International Colloquium, ICALP 2007, Wroc aw, Poland, July 9-13, 2007. Proceedings 34 , pages 704--715. Springer, 2007

2007
[13]

Superlinear lower bounds for multipass graph processing

Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. Algorithmica , 76:654--683, 2016

2016
[14]

Deterministic communication vs

Mika G \"o \"o s, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 1077--1088. IEEE, 2015

2015
[15]

Query-to-communication lifting for bpp

Mika G \"o \"o s, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for bpp. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 132--143, 2017

2017
[16]

Exponential separations in local differential privacy

Matthew Joseph, Jieming Mao, and Aaron Roth. Exponential separations in local differential privacy. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 515--527. SIAM, 2020

2020
[17]

On the power of unique 2-prover 1-round games

Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 767--775, 2002

2002
[18]

On quantum and probabilistic communication: Las vegas and one-way protocols

Hartmut Klauck. On quantum and probabilistic communication: Las vegas and one-way protocols. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 644--651, 2000

2000
[19]

Interaction in quantum communication

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman. Interaction in quantum communication. IEEE Transactions on Information Theory , 53(6):1970--1982, 2007

1970
[20]

On monotone formulae with restricted depth

Maria Klawe, Wolfgang J Paul, Nicholas Pippenger, and Mihalis Yannakakis. On monotone formulae with restricted depth. In Proceedings of the sixteenth annual ACM symposium on Theory of computing , pages 480--487, 1984

1984
[21]

Lifting with sunflowers

Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. Leibniz international proceedings in informatics , 215, 2022

2022
[22]

A tight unconditional lower bound on distributed randomwalk computation

Danupon Nanongkai, Atish Das Sarma, and Gopal Pandurangan. A tight unconditional lower bound on distributed randomwalk computation. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , pages 257--266, 2011

2011
[23]

Rounds in communication complexity revisited

Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In Proceedings of the twenty-third annual ACM symposium on Theory of computing , pages 419--429, 1991

1991
[24]

On limitations of the transformer architecture

Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. arXiv preprint arXiv:2402.08164 , 2024

2024 arXiv
[25]

The communication complexity of pointer chasing

Stephen J Ponzio, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. The communication complexity of pointer chasing. Journal of Computer and System Sciences , 62(2):323--355, 2001

2001
[26]

Separation of the monotone nc hierarchy

Ran Raz and Pierre McKenzie. Separation of the monotone nc hierarchy. In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 234--243. IEEE, 1997

1997
[27]

Communication Complexity: and Applications

Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications . Cambridge University Press, 2020

2020
[28]

Pointer chasing via triangular discrimination

Amir Yehudayoff. Pointer chasing via triangular discrimination. Combinatorics, Probability and Computing , 29(4):485--494, 2020

2020
[29]

Communication lower bounds for collision problems via density increment arguments

Guangxu Yang and Jiapeng Zhang. Communication lower bounds for collision problems via density increment arguments. STOC 2024 (to appear) , 2024

2024

Pith tools

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

[1] [1]

Polynomial pass lower bounds for graph streaming algorithms

Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. In Proceedings of the 51st Annual ACM SIGACT Symposium on theory of computing , pages 265--276, 2019

work page 2019

[2] [2]

How to compress interactive communication

Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 67--76, 2010

work page 2010

[3] [3]

Direct products in communication complexity

Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct products in communication complexity. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 746--755. IEEE, 2013

work page 2013

[4] [4]

Nearly optimal communication and query complexity of bipartite matching

Joakim Blikstad, Jan Van Den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Nearly optimal communication and query complexity of bipartite matching. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1174--1185. IEEE, 2022

work page 2022

[5] [5]

Query-to-communication lifting for bpp using inner product

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting for bpp using inner product. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

work page 2019

[6] [6]

An adaptivity hierarchy theorem for property testing

Cl \'e ment L Canonne and Tom Gur. An adaptivity hierarchy theorem for property testing. computational complexity , 27:671--716, 2018

work page 2018

[7] [7]

Memory bounds for continual learning

Xi Chen, Christos Papadimitriou, and Binghui Peng. Memory bounds for continual learning. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 519--530. IEEE, 2022

work page 2022

[8] [8]

Lower bounds on communication complexity

Pavol Duris, Zvi Galil, and Georg Schnitger. Lower bounds on communication complexity. In Proceedings of the sixteenth annual ACM symposium on Theory of computing , pages 81--91, 1984

1984