{"id":"27d8d13e-0070-4e57-a852-e3b2fa6db4d6","arxiv_id":"1908.01020","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"There is a total function whose randomized query complexity grows as Ω(R(f) log 1/ε), and every function obeys a strong direct sum theorem for average query complexity.","lead":"This paper proves two optimal results about randomized query complexity: error levels can cause a logarithmic blowup, and solving k copies of a problem costs k times as much. It answers open questions from Drucker (2012) and Feder, Kushilevitz, Naor, and Nisan (1995).","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9's BlueRed-to-PtrFcn reduction has reversed output labels: an all-red BlueRed 1-input maps to a PtrFcn 0-input, so B outputs the wrong value with high probability; Theorem 1 and Corollaries 3-4 are unsupported as written.","rationale":"Reader's verdict is REJECT. We agree with rejection, but not primarily because of the stated weakest assumption. Re-examining Lemma 15: each of the four Markov steps bounds a bad set of y's by Pr(X_i > 4E[X_i]) < 1/4, not <= 1/4; with four sets the union still has measure less than 1, so a good z exists. The only defect is that the conditional prefix-error expectation is bounded by epsilon, whereas unconditional error epsilon only gives epsilon/(1-delta) after conditioning on non-abort; replacing 4epsilon by, say, 16epsilon/3 restores the <1/4 bound. This is a constant-slack issue, not a missing-z issue. The real load-bearing flaw is Lemma 9's polarity. The reduction sends BlueRed-1 (all red) to a PtrFcn instance with no all-1 column, i.e. PtrFcn 0, and sends BlueRed-0 (half blue) to a PtrFcn 1-input with blue cells as special/good cells. B is defined to output the same as A, so on BlueRed-1 it outputs 0 with probability at least 1-epsilon while the correct label is 1. This is a sign error; complementing B's output appears to fix both cases, but as printed the reduction proves nothing about R(BlueRed) from R(PtrFcn). Since Theorem 1 and Corollaries 3 and 4 rely on Lemma 9, the paper's central separation claim is not established in this version. The preprint may be repairable, but the burden is on the authors to provide a corrected lemma.","tokens_in":15811,"tokens_out":16833,"duration_ms":158626,"concrete_test":"Analytically re-run the proof of Lemma 9 on a BlueRed 1-input x with all colored entries red and any exact PtrFcn algorithm A. The constructed z has PtrFcn(z)=0; if B returns A(z), its success probability on x equals the probability A(z)=1, which is at most epsilon, so the claimed error bound fails. Then test the proposed fix: change B's output to the complement of A's value; verify both BlueRed cases and the Claim 6 bound. If the complemented version goes through, Lemma 9 is a repairable sign error; otherwise the reduction itself is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 9 (Section 2.4), the reduction answers a black BlueRed entry by <1,_,...> and a red entry by <0,_,...>. Take x in BlueRed^{-1}(1), i.e. every column has exactly one colored entry and all colored entries are red. In the constructed PtrFcn instance z, every column contains at least one 0-entry, so no column is all-1 and PtrFcn(z)=0. The proof makes B output the same value as A(z). Since A computes PtrFcn with error at most epsilon, B outputs 0 with probability at least 1-epsilon, but the correct BlueRed value is 1. So B errs with probability at least 1-epsilon, contradicting the claimed error bound of 2epsilon. The reduction direction is reversed: to be correct, B must output the complement of A's value, and the BlueRed-0 case analysis must be re-done with that output rule. Lemma 9 is the bridge from GapID to PtrFcn; Theorem 1 and the corollaries depend on it. As written, the separation result is not established. The reader's Lemma 15 concern about four Markov bad sets is not the main problem: each bad set has measure strictly less than 1/4, so their union has measure less than 1; the conditional-error bound there is off by a 1/(1-delta) factor but is repairable.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16109,"tokens_out":14641,"duration_ms":146898,"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":[{"comment":"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.","section":"Section 2.4, Lemma 9"},{"comment":"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.","section":"Section 3.2, Lemma 15"}],"minor_comments":[{"comment":"The pseudocode is labeled 'Algorithm 2' but the text refers to it as Algorithm 1; please renumber consistently.","section":"Section 2.5"},{"comment":"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.","section":"Section 2.5"},{"comment":"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.","section":"Section 2.6"},{"comment":"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.","section":"Section 3.4, proof of Corollary 3"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The two major issues are local and appear repairable: one sign/output-label reversal in Lemma 9 and one index-range error in Lemma 15. The Lemma 15 Markov-existence concern raised by an earlier reader does not appear to be an obstruction. I recommend a major revision rather than rejection because the central results are plausible and the required fixes are within the scope of the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know upfront. The paper is serious and the two main results would be important if they hold: a first separation inside bounded-error randomized query complexity for total functions, and a strong direct sum with the epsilon/k error parameter. The machinery is well chosen—resilient functions to get rid of alphabet-size losses, and an abort model to get around Shaltiel's barrier. I finished the paper believing the theorems are probably true and the proof strategy is sound. But the version on arXiv does not prove them, because Lemma 9 contains a concrete error.\n\nThe problem is in the BlueRed-to-PtrFcn reduction (Section 2.4). Take x in BlueRed^{-1}(1): every column has exactly one colored entry and it is red. The reduction maps black entries to <1,...> and red entries to <0,...>, so every column of z contains a 0, hence no column is special and PtrFcn(z)=0. The proof then has B output A(z), and since A is an epsilon-error algorithm for PtrFcn, A(z)=0 with probability at least 1-epsilon. But the correct BlueRed value is 1. So B errs with probability at least 1-epsilon, contradicting the claimed 2epsilon bound. The fix is to output the complement of A's value in the no-blue case and redo the BlueRed-0 analysis; that direction is repairable, but as written it takes down Theorem 1 and Corollaries 3 and 4.\n\nThe other flagged issue, Lemma 15's four Markov inequalities, is much softer. Each bad set has measure strictly less than 1/4 (Markov is strict for >), so their union has measure less than 1 and a good z does exist. There is a small conditional-probability factor that needs checking, but it is a constants fix; the reader's worry about union of four 1/4 sets appears to be a misreading.\n\nOn credit: the exposition is clear, the reductions are spelled out, and the paper engages properly with prior work. The bounds in the chain (Lemmas 8, 10, 12, 14) look plausible. The citation pattern is clean; no self-citations force the results. If I were refereeing, I'd ask for a major revision: fix Lemma 9, patch the constants in Lemma 15, and resubmit. The results deserve a serious referee, and I'd send it out.","headline":"Promising techniques and plausible results, but Lemma 9's output direction is wrong and Theorem 1 is unproven as written; the fixes look easy.","tokens_in":16590,"tokens_out":7227,"would_cite":false,"duration_ms":68199,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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))$.","keywords":["randomized query complexity","decision tree complexity","direct sum theorem","error reduction","pointer function","resilient function","average-case query complexity","communication complexity lifting"],"falsifier":"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.","tokens_in":15617,"feed_emoji":"🎯","tokens_out":16292,"duration_ms":134250,"temperature":0.7,"pith_summary":"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.","feed_headline":"For random queries, tiny error costs log(1/ε) and k copies cost k×","feed_subtitle":"A total function hits the log(1/ε) error cost; every function pays k× per copy at scaled error.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the pointer-function construction and the partial gap-identity function that the separation proof builds on and modifies.","marker":"[2]"},{"why":"Provides the t-resilient functions used to encode cell alphabet symbols so that bit queries and cell queries have comparable cost.","marker":"[12]"},{"why":"Defines the original pointer function framework from which the paper's PtrFcn variant is taken.","marker":"[16]"},{"why":"The query-to-communication lifting theorem that transfers Corollary 3 to public-coin randomized communication complexity.","marker":"[17]"}],"fun_headline_variants":["Random query separation: error costs log(1/ε) and multi-copy has k log k","Tiny error costs log(1/ε); k copies cost k log k for random queries","Error costs log(1/ε), multi-copy costs k log k: query complexity duality","Log(1/ε) error price and k log k copy price: randomized query tightness","Separation and direct sum: random queries hit log(1/ε) and k log k"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random query separation: error costs log(1/ε) and multi-copy has k log k","Tiny error costs log(1/ε); k copies cost k log k for random queries","Error costs log(1/ε), multi-copy costs k log k: query complexity duality","Log(1/ε) error price and k log k copy price: randomized query tightness","Separation and direct sum: random queries hit log(1/ε) and k log k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000308,"raw_usage":{"total_tokens":1865,"prompt_tokens":1157,"completion_tokens":708,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":773,"completion_tokens_details":{"reasoning_tokens":586}},"tokens_in":773,"tokens_out":708,"duration_ms":6788,"temperature":1.0,"reasoning_tokens":586,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:28:55.954638+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Separations in query complexity based on pointer functions","cited_arxiv_id":null,"evidence_quote":"Supplies the pointer-function construction and the partial gap-identity function that the separation proof builds on and modifies."},{"cited_title":"The bit extraction problem or t-resilient functions","cited_arxiv_id":null,"evidence_quote":"Provides the t-resilient functions used to encode cell alphabet symbols so that bit queries and cell queries have comparable cost."},{"cited_title":"Deterministic communication vs","cited_arxiv_id":null,"evidence_quote":"Defines the original pointer function framework from which the paper's PtrFcn variant is taken."},{"cited_title":"Query-to-communication lifting for BPP","cited_arxiv_id":null,"evidence_quote":"The query-to-communication lifting theorem that transfers Corollary 3 to public-coin randomized communication complexity."}],"review_version":1}