{"id":"3b3a615b-91b8-4c94-bd3b-197feb07fde4","arxiv_id":"2507.12124","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Falsified-clause search in random O(log n)-CNFs requires Ω(n) randomized two-party communication, with high probability over the formula and variable partition.","lead":"The paper proves that in a random unsatisfiable Boolean formula whose clauses each contain about log n variables, two parties cannot efficiently find a clause falsified by a given assignment: any randomized protocol must communicate a constant fraction of the n variables. This strengthens the case that random formulas are hard to refute, because it moves the lower bound into the randomized communication model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 as stated allows satisfiable formulas; the m=O(n2^Δ) range must be restricted to m=Θ(n2^Δ) with sufficiently large constant and unsatisfiability required.","rationale":"The reader's verdict is CONDITIONAL with the same repair, but their named weakest assumption was the unproved expansion Lemma 6 cited from [Sok24]. I agree that Lemma 6 is a dependency, but it is a standard and correct random-graph fact; the hidden constant in r=Ω(n/Δ) depends on η, and the proof of Lemma 8 uses it consistently. The genuinely load-bearing issue is the statement of Theorem 4: as written it quantifies over m=O(n2^Δ), which includes satisfiable formulas and makes the central claim false or ill-posed. The abstract and the proof both target the unsatisfiable regime, so this is a repairable statement error. I also checked the technical core: subcube-like conversion (Lemma 17), closure construction (Lemma 22/26), and the δ-good reduction appear sound; minor issues such as the unqualified claim |J_ℓ|≤d in Claim 25 (which should be O(d/Δ)) are absorbed by the exponential factor in the intended Δ=c log n regime, and the exp(-d) term for constant-depth protocols is handled by a trivial union bound not stated in the paper. None of these rise to the level of rejecting the central claim; they reinforce CONDITIONAL. Hence I recommend no change from the reader's CONDITIONAL verdict.","tokens_in":16678,"tokens_out":39013,"duration_ms":440062,"concrete_test":"Instantiate Theorem 4 with m=1, a value permitted by m=O(n2^Δ). The formula is a single random Δ-clause, satisfiable with probability 1-2^{-Δ}; on satisfying inputs no falsified clause exists, so Search φ is not a total problem and the Ω(n) assertion is not even well-formed. This settles that the hypothesis must be strengthened. Then check that with m=α2^Δ n for some constant α>ln2 (and φ conditioned on being unsatisfiable), the derivation of Theorem 4 from Theorem 7 via Lemma 8 goes through unchanged; if yes, the result is valid for the intended regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4 (Section 1.1) states: let c>0 be large, n>0, Δ≥c log n, m=O(n2^Δ). If φ∼F(m,n,Δ) and X,Y is a uniform partition, then whp the randomized communication complexity of Search φ is Ω(n). This hypothesis allows m=1, or more generally any m below the Chvátal–Szemerédi threshold m≥ln2·2^Δ n (Theorem 3). In that regime φ is satisfiable whp, so the search problem 'output a clause falsified by (x,y)' has no valid output on satisfying assignments; the problem is not well-defined, and for small m the statement is trivially false or meaningless. The proof in Section 3.1 does not use the full O range: Lemma 8 assumes m=α2^Δ n with α>0 constant and c≥40, and the argument needs φ to be unsatisfiable so every input has a falsified clause. Thus the theorem statement must be repaired to m=Θ(n2^Δ) with sufficiently large hidden constant, and/or condition on unsatisfiability, exactly as the abstract's 'randomly sampled unsatisfiable (log n)-CNF' suggests. This is a statement-level gap rather than a defect in the expander/subcube machinery, which appears to work for the intended parameter regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for a random O(log n)-CNF formula over n variables with sufficiently many clauses, the randomized two-party communication complexity of the Falsified Clause Search problem (given an assignment, find a clause it falsifies) is linear in n. The authors first reduce the general random CNF case to a bipartite expander case via a delta-good partition lemma, then convert any communication protocol into a subcube-like protocol with codimension O(d) and error exp(-d), and finally use an expander-closure argument to show that any subcube-like protocol of codimension d has success probability at most d*2^{-Omega(Delta)} + exp(-d). Combining these yields Theorem 4. Detailed proofs of the structural lemmas are provided in appendices.","tokens_in":16947,"tokens_out":22949,"duration_ms":261902,"significance":"If correct, the main result is significant: it provides the first linear randomized communication lower bound for Falsified Clause Search on a natural random distribution of CNF formulas, avoiding ad hoc gadget constructions, and it strengthens the connection between proof complexity and communication complexity for random formulas. The technical machinery is also valuable: the refined conversion to subcube-like protocols with O(d) codimension and exp(-d) error (Lemma 17) improves on the O(d/epsilon) bound of [GGJL25], and the closure argument (Lemma 22) is presented in full. The proof is detailed and mostly self-contained, with the main external ingredient being the random graph expansion lemma (Lemma 6) cited from [Sok24]. The central derivation appears sound for the intended parameter regime.","major_comments":[{"comment":"The theorem states m=O(n2^Delta) with no lower bound on m. This allows, for example, m=1, where the formula is satisfiable with high probability; in that case Search phi is not a total problem (Definition 1 requires a falsified clause for every input), and under the standard partial-function interpretation a protocol with O(log n) communication solves it on the promise domain, contradicting the claimed Omega(n) bound. The proof does not cover the full O range: the derivation applies Lemma 8, which assumes m=alpha*2^Delta n with constants alpha>0 and c>=40, and the reduction to Theorem 7 presupposes that every input assignment falsifies at least one clause (i.e., phi is unsatisfiable). The statement should be repaired to m=Theta(n*2^Delta) with a sufficiently large hidden constant (so that phi is unsatisfiable with high probability, e.g., m>=ln2*2^Delta n as in Theorem 3), or explicitly condition on phi being unsatisfiable, as the abstract does. This is a statement-level gap; the expander and closure machinery appears to work for the intended regime.","section":"Theorem 4 (Section 1.1) and its proof (Section 3.1)"}],"minor_comments":[{"comment":"The binomial coefficient in the displayed sum is written as binom(m,m-j); it should be binom(Delta,j).","section":"Appendix A, proof of Lemma 8"},{"comment":"The notation G_A - Error_A - Error_B is ambiguous because both Error sets are subsets of [m], whereas the proof in Appendix A actually removes the left vertices and their neighborhoods on the right side, as made explicit in Lemma 22. The convention should be clarified.","section":"Section 3.1, definition of delta-good partition"},{"comment":"The bound |J_ell| <= d is used without derivation; it follows from Lemma 22(3) only when Delta is sufficiently large, which holds here given Delta = Theta(log n), but this step should be stated.","section":"Section 3.4, Claim 25"},{"comment":"The phrase 'with probability of success at least epsilon - 2^{-Omega(Delta)}' should specify that this success probability is measured with respect to the uniform distribution over all assignments, not the promise domain of a partial function.","section":"Proof of Theorem 4"},{"comment":"The reference [ABSR W04] displays an extra space in the author name; please fix the formatting.","section":"Bibliography"}],"recommendation":"major_revision","confidential_remarks":"The paper is well-written and the technical core is convincing. The main theorem statement needs correction to match the abstract and the proof; once m is restricted to the range used by Lemma 8 and unsatisfiability is guaranteed, the result should hold. The reliance on prior work ([Sok24, GNRS24, GGJL25]) is appropriate and clearly attributed. The statement-level gap in Theorem 4, if not caught, could mislead readers; it is easily fixable with a parameter-range adjustment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper delivers what it says: the first linear randomized communication lower bound for falsified-clause search on random O(log n)-CNFs, via a clean combination of subcube-like conversion, expansion, and closure. The improved subcube conversion with exp(-d) error is a genuinely reusable step, and the closure lemma is proved in full rather than hand-waved. The main derivation reads correctly: Lemma 8 gets you from random CNFs to the bipartite expander case, Theorem 7 does the heavy lifting, and the constants work out with rΔ = Ω(n).\n\nThe soft spot is exactly what the stress-test note flags: Theorem 4 as stated says m = O(n2^Δ), which allows clause densities below the satisfiability threshold. For those formulas, Search has no well-defined output, so the statement is either false or meaningless. The proof, however, never uses that full range; it invokes Lemma 8 with m = α2^Δ n and c ≥ 40, and needs the formula to be unsatisfiable. The repair is straightforward: state m = Θ(n2^Δ) with a sufficiently large hidden constant, and/or explicitly condition on unsatisfiability. The abstract already says 'unsatisfiable'; the theorem should match. This is a statement-level gap, not a defect in the machinery.\n\nOne more thing: the paper leans on Lemma 6 from [Sok24] for expansion of the random clause-variable graph. That is a cited standard computation, so it is not a problem, but it is the load-bearing probabilistic input.\n\nOverall: the result is new, the proof is mostly self-contained, and the central argument holds up once the theorem statement is corrected. This deserves a serious referee. Send it out, with a request to fix the m range.","headline":"First randomized communication lower bound for search on random (log n)-CNFs, with a correctable overstatement in Theorem 4's clause-density range.","tokens_in":17480,"tokens_out":2004,"would_cite":true,"duration_ms":23709,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q11","68Q17","03F20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that finding a falsified clause in a random O(log n)-CNF requires Ω(n) bits of randomized communication.","keywords":["randomized communication complexity","falsified clause search problem","random CNF formulas","subcube-like protocols","expander graphs","communication complexity lower bounds","proof complexity","random clause-variable graph"],"falsifier":"A concrete way to refute the claim is to exhibit, for random instances of $F(m,n,\\Delta)$ with $\\Delta = c\\log n$, a set $S$ of $r = \\omega(n/\\Delta)$ clauses whose union of variables is smaller than $(1-\\eta)\\Delta|S|$; such a set would violate the expansion lemma that the proof inherits from [Sok24]. Equivalently, one could design a randomized two-party protocol that finds a falsified clause with constant probability while communicating $o(n)$ bits, which would directly contradict Theorem 4. A more computational check would be to evaluate, on instances up to moderate $n$, whether the $(1/10)$-good partition property of Lemma 8 fails with non-negligible probability under uniformly random variable splits.","tokens_in":16483,"feed_emoji":"📡","tokens_out":16036,"duration_ms":161977,"temperature":0.7,"pith_summary":"The paper proves that a random unsatisfiable $O(\\log n)$-CNF over $n$ variables is hard for two-party randomized communication: when the variables are split uniformly at random between Alice and Bob, any randomized protocol that finds a clause falsified by the given assignment must communicate $\\Omega(n)$ bits with high probability. The result applies to the natural random-CNF distribution, not an ad hoc formula construction, and it treats the randomized tree-like communication model, which is incomparable with the deterministic dag-like model used in earlier work on random $O(\\log n)$-CNFs. This matters because communication lower bounds for the Falsified Clause Search problem translate, through a standard framework, into lower bounds on proof length for propositional proof systems; random CNFs are the natural candidate formulas for hardness in all such systems. The proof works by converting any short protocol into a 'subcube-like' protocol whose rectangles fix only $O(d)$ variables while keeping the rest pseudorandom, then using expansion of the random clause-variable graph to show that even such structured protocols cannot certify a falsified clause with more than tiny probability.","feed_headline":"Finding a falsified clause in random CNFs needs linear communication","feed_subtitle":"Any randomized two-party protocol must send Ω(n) bits to find a falsified clause in a random O(log n)-CNF.","key_machinery":"The argument is carried by two mechanisms. The first is the conversion of an arbitrary depth-$d$ communication protocol into a $\\gamma$-subcube-like protocol (Lemma 17): a rectangle whose two sides are products of a fixed partial assignment on a set of coordinates with a distribution that is $\\gamma$-spread (min-entropy at least $\\gamma$ per variable) on the remaining coordinates; the conversion fixes only $O(d/(1-\\gamma))$ coordinates in total while keeping the error at $\\exp(-d)$, using entropy deficiency and the density-restoring partition of Lemma 15. The second is the closure trick (Lemma 22), which attaches to each protocol node $v$ two growing sets of clauses, $\\mathrm{Cl}_X(v)$ and $\\mathrm{Cl}_Y(v)$, such that after deleting those clauses, their neighbourhoods, and the coordinates fixed at $v$, the bipartite clause-variable graphs $G_1$ and $G_2$ remain $(r,\\Delta,\\beta\\Delta)$-expanders. This keeps the 'pseudorandom' part of the graph expanding as the protocol progresses. At a leaf, the answer clause $i$ either lies in the closure, which is small ($|\\mathrm{Cl}_X(v)|,|\\mathrm{Cl}_Y(v)| \\le d/((\\alpha-\\beta)\\Delta)$), or it has at least $\\alpha\\Delta/2$ neighbours among variables that are still $\\gamma$-spread, making the probability that the leaf's rectangle falsifies $i$ at most $2^{-\\gamma \\alpha \\Delta/2}$. Summing over the leaves with the closure bound gives Theorem 7's error estimate.","core_discovery":"Formally, the paper establishes Theorem 4: for a large enough constant $c>0$, clause width $\\Delta \\ge c \\log n$, and $m = O(n 2^\\Delta)$ clauses sampled uniformly with repetition (the distribution $F(m,n,\\Delta)$), if $\\varphi$ is drawn from $F(m,n,\\Delta)$ and $(X,Y)$ is a uniformly random partition of the $n$ variables, then with high probability the randomized communication complexity of Search $\\varphi$ — the problem of outputting a clause of $\\varphi$ falsified by the input assignment $(x,y)$ — is $\\Omega(n)$. The proof reduces the general random formula to a bipartite instance on two $(r,\\Delta,\\alpha\\Delta)$-expander graphs via a $\\delta$-good partition lemma, and then proves a structural bound against all protocols: any protocol of depth $d \\le O(\\Delta r)$ has success probability at most $d \\cdot 2^{-\\Omega(\\Delta)} + \\exp(-d)$ (Theorem 7). Because the random clause-variable graph is an expander with $r = \\Omega(n/\\Delta)$, the product $r\\Delta$ is linear in $n$, and the bound becomes $\\Omega(n)$. A separate contribution is a refined conversion of arbitrary protocols to subcube-like protocols (Lemma 17): codimension $O(d)$ with error $\\exp(-d)$, improving the $O(d/\\varepsilon)$ dependence of prior work and making the argument work in the inverse-polynomial error regime.","pith_inferences":["The $\\exp(-d)$ error in Lemma 17 is strong enough that the conversion might be reusable as a standalone 'lifting with tiny error' tool: one could try to apply it to search problems other than falsified-clause, such as collision-finding or set-intersection, where small-error regime lower bounds are currently hard to obtain.","A natural open direction the paper leaves implicit is the constant-width case: the proof's expansion radius $r = \\Omega(n/\\Delta)$ and the dependence on $2^\\Delta$ in $m$ both rely on $\\Delta$ growing logarithmically, so the technique gives no evidence about random $O(1)$-CNFs, where Feige's conjecture primarily lives.","The uniform random partition is used to make error clauses rare; an editor's test would be whether a fixed balanced partition (e.g., first half vs second half of variables) also yields a $\\delta$-good partition for typical random formulas, which would simplify connections to proof complexity where the split is not random."],"forward_implications":["Random $O(\\log n)$-CNFs are now hard in a communication model incomparable with the earlier deterministic dag-like one: the lower bound rules out randomized tree-like proof systems whose proofs reduce to such protocols, extending hardness of natural random formulas to a new class of proof systems.","The refined subcube-like conversion (Lemma 17) gives $O(d)$ codimension with $\\exp(-d)$ error, applicable when $d = \\Omega(\\log n)$; prior conversion bounds degenerated for error $\\varepsilon = O(d/n)$, so this sharpening is needed for the inverse-polynomial error regime used here.","Because the bound is $\\Omega(n)$ and $n$ bits always suffice (one player sends the full assignment), the randomized communication complexity of Search $\\varphi$ for these formulas is linear, not merely superlogarithmic.","The $\\delta$-good partition lemma (Lemma 8) shows that a uniformly random split of variables preserves the hardness of the general random CNF up to an exponentially small loss, so the bipartite expander analysis is the true bottleneck of the lower bound."],"supporting_citations":[{"why":"Supplies Lemma A.2, the expansion of random clause-variable graphs stated here as Lemma 6, which is the key graph-theoretic input and gives $r = \\Omega(n/\\Delta)$.","marker":"[Sok24]"},{"why":"Introduced subcube-like protocols and the conversion of arbitrary protocols into them; the paper refines that conversion to codimension $O(d)$ with $\\exp(-d)$ error, and the simplified conversion algorithm is taken from here.","marker":"[GGJL25]"},{"why":"Provides the density-restoring partition (Lemma 15) used inside the protocol conversion to keep the unfixed part $\\gamma$-spread while controlling entropy deficiency.","marker":"[GPW20]"},{"why":"The closure construction of Lemma 22, which deletes a small set of clauses to maintain expansion on the pseudorandom part of the graph, is implicit in this paper and used directly here.","marker":"[GNRS24]"},{"why":"Provides the iterative closure construction that the paper uses to maintain expansion properties during protocol simulation.","marker":"[Sok20]"},{"why":"Established the approach of splitting variables uniformly at random between Alice and Bob for random formulas and reducing the general case to a bipartite expander instance; the clean-up argument of Lemma 8 follows this template.","marker":"[HP17]"},{"why":"Proved random $O(\\log n)$-CNFs are hard for Cutting Planes via deterministic dag-like communication using the same random-split and bipartite reduction; the current paper's analysis is positioned against this baseline.","marker":"[FPPR22]"},{"why":"Guarantees that random formulas in $F(m,n,\\Delta)$ with $m \\ge \\ln 2 \\cdot 2^\\Delta n$ are unsatisfiable with high probability, so the falsified-clause search problem is well-posed.","marker":"[CS88]"},{"why":"Foundation of the structure-vs-randomness approach ('rectangles are nonnegative juntas') that underlies the conversion to subcube-like protocols and the use of min-entropy spread.","marker":"[GLM+16]"},{"why":"Demonstrated a direct structure-vs-randomness proof of a Search lower bound without a Unique Disjointness reduction, the approach the present paper adapts to random CNFs.","marker":"[YZ24]"}],"fun_headline_variants":["Random CNF search needs linear communication","Falsified clause search in random CNFs is hard","Linear communication lower bound for random CNF search","Searching random CNFs requires Ω(n) communication","Any protocol must send Ω(n) bits for falsified clause"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument rests on the expansion of random clause-variable graphs: a random $O(\\log n)$-CNF's clause-variable graph is an $(r,\\Delta,(1-\\eta)\\Delta)$-expander for sets of up to $r = \\Omega(n/\\Delta)$ clauses (Lemma 6, cited from prior work rather than proved here), and it is the product $r\\Delta = \\Omega(n)$ that converts the structural protocol bound into the linear communication lower bound.","fun_headline_variants_meta":{"raw":{"variants":["Random CNF search needs linear communication","Falsified clause search in random CNFs is hard","Linear communication lower bound for random CNF search","Searching random CNFs requires Ω(n) communication","Any protocol must send Ω(n) bits for falsified clause"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1331,"prompt_tokens":883,"completion_tokens":448,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":499,"completion_tokens_details":{"reasoning_tokens":373}},"tokens_in":499,"tokens_out":448,"duration_ms":5519,"temperature":1.0,"reasoning_tokens":373,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:55:23.953039+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete way to refute the claim is to exhibit, for random instances of $F(m,n,\\Delta)$ with $\\Delta = c\\log n$, a set $S$ of $r = \\omega(n/\\Delta)$ clauses whose union of variables is smaller than $(1-\\eta)\\Delta|S|$; such a set would violate the expansion lemma that the proof inherits from [Sok24]. Equivalently, one could design a randomized two-party protocol that finds a falsified clause with constant probability while communicating $o(n)$ bits, which would directly contradict Theorem 4. A more computational check would be to evaluate, on instances up to moderate $n$, whether the $(1/10)$-good partition property of Lemma 8 fails with non-negligible probability under uniformly random variable splits.","supporting_citations":[],"review_version":1}