Pith. sign in

REVIEW 2 major objections 5 minor 26 references

Optimal Separation and Strong Direct Sum for Randomized Query Complexity

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · 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 two optimal bounds in randomized query complexity: some total functions require $\Omega(R(f)\log(1/\epsilon))$ queries for $\epsilon$-error, and every function's $k$-instance cost is $\Omega(k\,\bar{R}_{\epsilon/k}(f))$.

desk verdict Promising techniques and plausible results, but Lemma 9's output direction is wrong and Theorem 1 is unproven as written; the fixes look easy. read the letter →

arxiv 1908.01020 v1 pith:I5AM3X2M submitted 2019-08-02 cs.CC

Eric Blais , Joshua Brody This is my paper · ORCID
classification cs.CC
keywords randomizedquerycomplexitydecisiontreedirectsumtheoremerrorreductionpointerfunctionresilientaverage-casecommunicationlifting
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

Randomized query algorithms can always reduce their error from $1/3$ to any $\epsilon$ by repetition, at a cost factor $O(\log(1/\epsilon))$. This paper proves that this logarithmic cost is unavoidable for total functions: there exists a total function whose $\epsilon$-error randomized query complexity is $\Omega(R(f)\cdot \log(1/\epsilon))$. It also proves a strong direct sum theorem: for every function $f$, computing $k$ independent instances with error $\epsilon$ costs $\Omega(k \cdot \bar{R}_{\epsilon/k}(f))$ in the average-case query model, matching the obvious upper bound. Together these results yield a total function whose $k$-fold query complexity is $\Theta(k \log k \cdot R(f))$, and via a lifting theorem the same superlinear direct-sum behavior transfers to public-coin randomized communication complexity. These are the first results to show that the standard upper bounds are tight in these settings.

What carries the argument

The argument runs on two mechanisms. For the separation theorem, the central object is a pointer function $\mathrm{PtrFcn}$ defined on an $n\times m$ grid of cells; a $1$-input has a unique all-ones column containing a special cell whose row pointers all lead to zero-valued linked cells, half of which point back to the special cell. This function is first reduced to a partial 'gap identity' function via an intermediate BlueRed gadget, and then composed with a $t$-resilient function $\varphi:\{0,1\}^N \to \Gamma$ that encodes each cell's alphabet symbol into bits in such a way that any algorithm must query a constant fraction of a cell's bits to learn its value. The resilience property collapses the distinction between bit queries and cell queries, removing the logarithmic gap between upper and lower bounds. For the direct sum theorem, the machinery is an abort model: randomized algorithms may output $\bot$ with probability at most $\delta$ and err with probability at most $\epsilon$, and a minimax principle connects this abort-enabled randomized complexity to distributional complexity. The proof of the strong direct sum selects one of the $k$ coordinates $i^*$ and, using four Markov-inequality averaging bounds, builds a deterministic algorithm for one copy of $f$ with error $\epsilon/k$ and query cost $O(q/k)$, where $q$ is the cost of the $k$-copy algorithm.

What would settle it

Enumerate all inputs for a small function $f$ and a distribution $\mu$ with $k=2$ and check whether the four inequalities in Lemma 15 can be satisfied simultaneously; if no input $z$ satisfies all four, the proof's construction of the one-copy algorithm fails, so the strong direct sum proof would need another route.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is twofold. Theorem 1 states that for infinitely many input lengths $n$ and for every error parameter $\epsilon$ down to $2^{-(n/\log n)^{1/3}}$, there is a total Boolean function $f$ on $n$ bits for which the $\epsilon$-error randomized query complexity is $\Omega(R(f) \cdot \log(1/\epsilon))$, matching the success-amplification upper bound up to constants. Theorem 2 states that for every total function $f$, every $k \ge 2$, and every $0 \le \epsilon \le 1/20$, the average randomized query complexity of the $k$-fold function $f^k$ is $\Omega(k \cdot \bar{R}_{\epsilon/k}(f))$, which combined with the simple union-bound upper bound gives $\Theta(k \cdot \bar{R}_{\epsilon/k}(f))$. The proofs introduce a pointer function with resilient encodings to make bit-query and cell-query costs coincide, and an abort-enabled distributional model with a minimax principle to prove the direct sum. Consequences include a total function with $R(f^k) = \Theta(k \log k\, R(f))$ (Corollary 3) and, by a query-to-communication lifting theorem, a total function whose public-coin randomized communication complexity satisfies $R^{\mathrm{cc}}(f^k) = \Theta(k \log k\, R^{\mathrm{cc}}(f))$ (Corollary 4).

Load-bearing premise

For the strong direct sum theorem, the proof requires that among all inputs to the k-copy problem there is one particular input that simultaneously satisfies four separate averaging bounds; the argument only shows each bound holds for most inputs, and does not guarantee a single input satisfying all four.

Editorial extensions

If this is right

  • The success-amplification upper bound $R_\epsilon(f) = O(R(f)\log(1/\epsilon))$ is tight for total functions in the worst case, so no general simulation can reduce error more cheaply.
  • The strong direct sum theorem holds in the average randomized query model for every function: computing $k$ instances with error $\epsilon$ is exactly as expensive (up to constants) as $k$ times the cost of one instance with error $\epsilon/k$, with no amortization.
  • There exists a total function with $R(f^k) = \Theta(k \log k\, R(f))$; the $\log k$ factor is necessary for some functions, not just an artifact of the upper bound.
  • The same $\Theta(k \log k\, R^{\mathrm{cc}}(f))$ behavior appears in public-coin randomized communication complexity for a total function, answering whether amortized communication can be superlinear.

Reading between the lines

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

  • The resilient-encoding trick that aligns bit-query and cell-query costs may be reusable in other composed-function settings where a large alphabet creates a gap between bit and cell complexity, potentially tightening other separations.
  • The abort-based distributional proof might extend to the XOR and majority compositions conjectured in the paper, since the abort model sidesteps the barrier that blocks ordinary distributional strong direct sums.
  • If the four Markov inequalities in Lemma 15 cannot be satisfied simultaneously for some function and distribution, the strong direct sum might still be true but would require a different proof; this is a concrete place to probe the proof's robustness.
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

2 major / 5 minor

Summary. The paper claims two main results. Theorem 1 states that for infinitely many input lengths n and every 2^{-(n/log n)^{1/3}} < ε ≤ 1/3, there is a total function f whose ε-error randomized query complexity satisfies R_ε(f) = Ω(R(f) · log(1/ε)). Theorem 2 states a strong direct sum theorem in the average-case randomized query model: for every f, every k ≥ 2, and every 0 ≤ ε ≤ 1/20, one has Rbar_ε(f^k) = Ω(k · Rbar_{ε/k}(f)). The paper then derives Corollary 3, a total function with R(f^k) = Θ(k log k · R(f)), and Corollary 4, the analogous superlinear direct sum for public-coin randomized communication complexity via the GPW lifting theorem. The proof of Theorem 1 proceeds through the partial function GapID, an intermediate total-ish function BlueRed, a pointer function PtrFcn, and finally a resilient-function encoding EncFcn. The proof of Theorem 2 introduces algorithms that may abort, proves a distributional strong direct sum lemma (Lemma 15), and converts it back to the average randomized model with a Yao minimax principle for aborting algorithms.

Significance. If the proofs can be repaired as indicated below, these would be strong results: Theorem 1 gives the first optimal separation within bounded-error randomized query complexity by matching the standard success-amplification upper bound, and Theorem 2 gives the first strong direct sum theorem in the average-case randomized query model. The corollaries answer an open problem of Drucker and, via lifting, an open problem of Feder, Kushilevitz, Naor, and Nisan. The paper is self-contained relative to known external results, and the use of resilient functions to eliminate alphabet-size logarithmic gaps is an elegant idea. The lower-bound structure is a genuine reduction rather than a curve fit, and the paper is clear about its model distinctions.

major comments (2)
  1. [Section 2.4, Lemma 9] The BlueRed-to-PtrFcn reduction as written outputs the wrong value in the all-red case. For x ∈ BlueRed^{-1}(1), every column has exactly one red entry and all other entries are black. Under the stated mapping (black ↦ <1,⊥,...>, red ↦ <0,⊥,...>), the constructed z has a 0 in every column, so no column is all-1 and PtrFcn(z) = 0. Since B outputs the same value as A(z), and A computes PtrFcn with error at most ε, B outputs 0 with probability at least 1−ε, which is the wrong answer for BlueRed(x) = 1. The reduction should output the complement of A(z) when no blue cell has been probed; with that change the second case of the proof also works through Claim 6, because on a PtrFcn 1-input A outputs 1 with high probability and a probe of the special blue cell already gives the correct BlueRed value 0. As written, however, Lemma 9's claimed error bound is false, and Theorem 1 and Corollaries 3–4 rest on it.
  2. [Section 3.2, Lemma 15] The construction of A′ contains an implementability error: it verifies that A(z(i∗←x))_{≤i∗} = f^k(z(i∗←x)). This equality includes coordinate i∗, whose value is f(x); checking it would require A′ to evaluate the very function f on its input x before completing its computation. A query algorithm cannot perform this check. I believe the intended check is on the first i∗−1 coordinates only, i.e. A(z(i∗←x))_{<i∗} = f^k(z(i∗←x))_{<i∗}; with that replacement, A′ can perform the check using the fixed string z, and the stated abort and error bounds follow from the four conditions on z. I also note that the simultaneous existence of z is not obstructed by a four-way Markov union: three of the four bounds are probabilistic averaging conditions, each with bad set of measure at most 1/4, and the fourth is an expectation bound that follows directly from averaging over y. The chosen z can therefore be found by intersecting the three good events.
minor comments (5)
  1. [Section 2.5] The pseudocode is labeled 'Algorithm 2' but the text refers to it as Algorithm 1; please renumber consistently.
  2. [Section 2.5] In the proof of Lemma 10, the sentence 'Exactly half of the columns are good' should read 'Exactly half of the linked cells are good'; it is the linked cells, not the columns themselves, that carry the good/not-good property.
  3. [Section 2.6] The displayed expression for N says N = O(mn|Γ|), but the encoded function has n·m cells each encoded by C = O(log |Γ|) bits, so the correct bound is N = O(mn log |Γ|); the current expression overcounts by an exponential factor.
  4. [Section 3.4, proof of Corollary 3] In the sentence 'By Theorem 2, the randomized communication complexity of f^k satisfies ...', the phrase should be 'randomized query complexity'; communication complexity is not involved until Corollary 4.
  5. [Throughout] The notation for average-case randomized query complexity is inconsistent: the abstract uses \(\overline{\mathrm R}\), while the body often writes \(R\) for both the worst-case and the average-case quantity; please disambiguate consistently.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivations reduce to external theorems and self-contained reductions, not to their own conclusions.

full rationale

I walked the claimed derivation chains for Theorem 1, Theorem 2, and Corollaries 3 and 4. Theorem 1 is built from a lower bound on GapID (Lemma 7), a reduction from GapID to BlueRed (Lemma 8), a reduction from BlueRed to PtrFcn (Lemma 9), a matching upper bound for PtrFcn (Lemma 10), and an encoding using resilient functions whose existence is imported from Chor et al. [12] (Theorem 11 and Lemma 12). Each step is either proved in the paper or cited from external work; none of the cited results are by the present authors and none assume the target separation. Theorem 2 is proved via an abort model, a Yao minimax principle adapted in Lemma 14, and a distributional strong direct sum lemma (Lemma 15) using only averaging and Markov's inequality; the lower bound is not an input to itself. Corollary 3 combines Theorems 1 and 2, and Corollary 4 invokes the external query-to-communication lifting theorem of Goos, Pitassi, and Watson [17]. I found no fitted parameters renamed as predictions, no self-definitional equivalences, and no load-bearing self-citations. A skeptical reviewer's concern about Lemma 9's output labeling, or about the existence of a z satisfying all four Markov bounds in Lemma 15, would be a correctness or proof-gap issue, not a circularity issue: the claimed reductions are not equivalent to their inputs by construction. Accordingly, the circularity score is 0.

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

The paper introduces new functions (PtrFcn, BlueRed, EncFcn) and an abort model, but these are mathematical constructions, not postulated entities with hidden degrees of freedom. No free parameters are fitted to data; constants like δ=1/40 are proof parameters.

assumptions (3)
  • standard math Yao's minimax principle for randomized algorithms that err and abort
    Used in Lemma 14 to relate distributional and randomized query complexity with abort; standard zero-sum game argument.
  • domain assumption Chor et al. existence of n/3-resilient functions with output length at least 0.08n
    Theorem 11 from Chor et al. is invoked in Section 2.6 to encode large alphabet symbols into bits without losing query complexity.
  • domain assumption Göös-Pitassi-Watson query-to-communication lifting theorem
    Theorem 16, cited from [17], transfers the query complexity direct sum result to communication complexity in Corollary 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Separation and Strong Direct Sum for Randomized Query Complexity." pith.science (2026). https://pith.science/paper/I5AM3X2M

@misc{pith2026190801020,
  author       = {Pith},
  title        = {Pith review of: Optimal Separation and Strong Direct Sum for Randomized Query Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I5AM3X2M}},
  note         = {Machine review of arXiv:1908.01020}
}
abstract

We establish two results regarding the query complexity of bounded-error randomized algorithms. * Bounded-error separation theorem. There exists a total function $f : \{0,1\}^n \to \{0,1\}$ whose $\epsilon$-error randomized query complexity satisfies $\overline{\mathrm{R}}_\epsilon(f) = \Omega( \mathrm{R}(f) \cdot \log\frac1\epsilon)$. * Strong direct sum theorem. For every function $f$ and every $k \ge 2$, the randomized query complexity of computing $k$ instances of $f$ simultaneously satisfies $\overline{\mathrm{R}}_\epsilon(f^k) = \Theta(k \cdot \overline{\mathrm{R}}_{\frac\epsilon k}(f))$. As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function $f$ for which $\mathrm{R}(f^k) = \Theta( k \log k \cdot \mathrm{R}(f))$. This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of G\"o\"os, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies $\mathrm{R}^{\mathrm{cc}} (f^k) = \Theta( k \log k \cdot \mathrm{R}^{\mathrm{cc}}(f))$, answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).

Figures

Figures reproduced from arXiv: 1908.01020 by the authors.

Figure 1
Figure 1. A 1-input for PtrFcn. PtrFcn(x) = 1 iff there is a unique column whose cells all have value 1; there is a special cell within this column which has nontrivial row pointers; these pointers all point to cells with value 0; and half of these linked cells point back to the special cell. Note: blank cells in the figure represent inputs that can be arbitrary. Section 2.5, we provide a matching upper bound on this query co… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Separations in query complexity using cheat sheets

    Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings 48th Annual ACM Symposium on Theory of Computing , pages 863–876, 2016

    work page 2016

  2. [2]

    Separations in query complexity based on pointer functions

    Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. Journal of the ACM , 64(5):32, 2017

    work page 2017

  3. [3]

    Nearly optimal separations between communication (or query) complexity and partitions

    Andris Ambainis, Martins Kokainis, and Robin Kothari. Nearly optimal separations between communication (or query) complexity and partitions. In Proceedings 31st Annual Conference on Computational Complexity , page 4, 2016

    work page 2016

  4. [4]

    Separations in communication complexity using cheat sheets and information complexity

    Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G¨ o¨ os, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha. Separations in communication complexity using cheat sheets and information complexity. In Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science, pages 555–564, 2016

    work page 2016

  5. [5]

    An information statistics approach to data stream and communication complexity

    Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702–732, 2004

    work page 2004

  6. [6]

    How to compress interactive commu- nication

    Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive commu- nication. SIAM Journal on Computing , 42(3):1327–1363, 2013

    work page 2013

  7. [7]

    Decision trees with AND, OR queries

    Yosi Ben-Asher and Ilan Newman. Decision trees with AND, OR queries. In Proceedings 10th Annual Structure in Complexity Theory Conference , pages 74–81, 1995

    work page 1995

  8. [8]

    Randomized query complexity of sabotaged and com- posed functions

    Shalev Ben-David and Robin Kothari. Randomized query complexity of sabotaged and com- posed functions. Theory of Computing , 14(1):1–27, 2018

    work page 2018

Show all 26 references
  1. [9]

    Information equals amortized communication

    Mark Braverman and Anup Rao. Information equals amortized communication. IEEE Trans- actions on Information Theory , 60(10):6058–6069, 2014

    2014

  2. [10]

    Robust polynomials and quantum algorithms

    Harry Buhrman, Ilan Newman, Hein R¨ ohrig, and Ronald de Wolf. Robust polynomials and quantum algorithms. Theory Comput. Syst. , 40(4):379–395, 2007

    2007

  3. [11]

    Informational complexity and the direct sum problem for simultaneous message complexity

    Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao. Informational complexity and the direct sum problem for simultaneous message complexity. In Proceedings 42nd Annual IEEE Symposium on Foundations of Computer Science , pages 270–278, 2001

    2001

  4. [12]

    The bit extraction problem or t-resilient functions

    Benny Chor, Oded Goldreich, Johan H˚ astad, Joel Friedman, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science , pages 396–407, 1985

    1985

  5. [13]

    Improved direct product theorems for randomized query complexity

    Andrew Drucker. Improved direct product theorems for randomized query complexity. Com- putational Complexity, 21(2):197–244, 2012

    2012

  6. [14]

    Amortized communication com- plexity

    Tom´ as Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan. Amortized communication com- plexity. SIAM Journal on Computing , 24(4):736–750, 1995

    1995

  7. [15]

    Exponential separation of information and communica- tion

    Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communica- tion. In Proceedings 55th Annual IEEE Symposium on Foundations of Computer Science, pages 176–185, 2014. 16

    2014

  8. [16]

    Deterministic communication vs

    Mika G¨ o¨ os, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In Proceedings 56th Annual IEEE Symposium on Foundations of Computer Science , pages 1077–1088, 2015

    2015

  9. [17]

    Query-to-communication lifting for BPP

    Mika G¨ o¨ os, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. In Proceedings 58th Annual IEEE Symposium on Foundations of Computer Science , 2017

    2017

  10. [18]

    A direct product theorem

    Russell Impagliazzo, Ran Raz, and Avi Wigderson. A direct product theorem. In Proceedings 9th Annual Structure in Complexity Theory Conference , pages 88–96, 1994

    1994

  11. [19]

    Optimal direct sum results for deterministic and randomized decision tree complexity

    Rahul Jain, Hartmut Klauck, and Miklos Santha. Optimal direct sum results for deterministic and randomized decision tree complexity. Inf. Process. Lett., 110(20):893–897, 2010

    2010

  12. [20]

    Super-logarithmic depth lower bounds via the direct sum in communication complexity

    Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3):191–204, 1995

    1995

  13. [21]

    Woodruff, and Grigory Yaroslavtsev

    Marco Molinaro, David P. Woodruff, and Grigory Yaroslavtsev. Beating the direct sum theorem in communication complexity with implications for sketching. InProceedings 24th Annual ACM- SIAM Symposium on Discrete Algorithms , pages 1738–1756, 2013

    2013

  14. [22]

    Amplification of one-way infor- mation complexity via codes and noise sensitivity

    Marco Molinaro, David P Woodruff, and Grigory Yaroslavtsev. Amplification of one-way infor- mation complexity via codes and noise sensitivity. In Proceedings 42nd Annual International Colloquium on Automata, Languages, and Programming , pages 960–972. Springer, 2015

    2015

  15. [23]

    Towards better separation between determinis- tic and randomized query complexity

    Sagnik Mukhopadhyay and Swagato Sanyal. Towards better separation between determinis- tic and randomized query complexity. In Proceedings 35th Annual Foundations of Software Technology and Theoretical Computer Science, pages 206–220, 2015

    2015

  16. [24]

    Noam Nisan, Steven Rudich, and Michael E. Saks. Products and help bits in decision trees. SIAM Journal on Computing , 28(3):1035–1050, 1999

    1999

  17. [25]

    Towards proving strong direct product theorems

    Ronen Shaltiel. Towards proving strong direct product theorems. Computational Complexity, 12(1-2):1–22, 2003

    2003

  18. [26]

    The power of asymmetry in constant-depth circuits

    Alexander Sherstov. The power of asymmetry in constant-depth circuits. SIAM Journal on Computing, 47(6):2362–2434, 2018. 17

    2018

Pith tools

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