Pith. sign in

REVIEW 1 major objections 5 minor 40 references

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication

T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper proves that finding a falsified clause in a random O(log n)-CNF requires Ω(n) bits of randomized communication.

desk verdict First randomized communication lower bound for search on random (log n)-CNFs, with a correctable overstatement in Theorem 4's clause-density range. read the letter →

arxiv 2507.12124 v1 pith:NZGCYRG5 submitted 2025-07-16 cs.CC

Artur Riazanov , Anastasia Sofronova , Dmitry Sokolov , Weiqiang Yuan This is my paper · ORCID
classification cs.CC MSC 68Q1168Q1703F20
keywords randomizedcommunicationcomplexityfalsifiedclausesearchproblemrandomCNFformulassubcube-likeprotocolsexpandergraphslowerboundsproofclause-variablegraph
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

1 major / 5 minor

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.

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 (1)
  1. [Theorem 4 (Section 1.1) and its proof (Section 3.1)] 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.
minor comments (5)
  1. [Appendix A, proof of Lemma 8] The binomial coefficient in the displayed sum is written as binom(m,m-j); it should be binom(Delta,j).
  2. [Section 3.1, definition of delta-good partition] 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.
  3. [Section 3.4, Claim 25] 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.
  4. [Proof of Theorem 4] 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.
  5. [Bibliography] The reference [ABSR W04] displays an extra space in the author name; please fix the formatting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main lower bound is proved from expansion, density-restoring partition, and closure lemmas whose assumptions do not include the target theorem.

full rationale

The derivation chain is: Theorem 4 is reduced to the bipartite expander statement Theorem 7 via Lemma 8; Theorem 7 is proved from Lemma 17 (conversion to subcube-like protocols), Lemma 22 (closure construction), and Lemma 23 (lower bound against subcube-like protocols). Lemma 17 is proved in Section 3.3 using density-restoring partitions from [GPW20]. Lemma 22 is proved in Appendix B even though it is attributed as implicit in [GNRS24]. Lemma 8 is proved in Appendix A. The only externally imported ingredient is Lemma 6, the expansion of random clause-variable graphs, cited from [Sok24, Lemma A.2] and described as a standard computation; this is a parameter-free random-graph fact whose stated assumptions do not contain the communication lower bound being proved, and it is independently published prior work rather than an assumption designed for this paper. The same-group citations [Sok20, Sok24, GNRS24, SS22] are used for tools such as closure iteration, expansion, and density restoration, not as a substitute for the main proof. No fitted parameter is renamed as a prediction, and no equation is defined in terms of the claimed conclusion. The skeptical concern that Theorem 4's m = O(n 2^Delta) range includes satisfiable formulas and should be m = Theta(n 2^Delta), or conditioned on unsatisfiability, is a statement-level correctness issue rather than a circularity: the proof in Section 3.1 explicitly applies Lemma 8 with m = alpha 2^Delta n and a 1/10-good partition. Thus no circular step is exhibited.

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

No free parameters are fitted to data; constants α, β, δ, η, γ are chosen inside the proofs as absolute constants, not inferred from measurements. The paper relies on standard background theorems (Yao's principle, Chvátal–Szemerédi, density-restoring partition) and on Lemma 6 from [Sok24]. No new physical or mathematical entities are postulated; the closure sets and subcube-like protocols are proof devices from prior work.

assumptions (5)
  • domain assumption Random Δ-CNF graphs satisfy the (r,Δ,(1-η)Δ)-expander property for r=Ω(n/Δ) (Lemma 6, cited from [Sok24, Lemma A.2]).
    This unproved-in-preprint expansion lemma is load-bearing: it supplies rΔ=Ω(n), which the final Ω(n) communication bound needs.
  • domain assumption Chvátal–Szemerédi theorem: if m≥ln2·2^Δ n then φ∼F(m,n,Δ) is unsatisfiable whp (Theorem 3).
    The Search problem is only well-defined on unsatisfiable formulas; the paper relies on this threshold to make the random instance total.
  • standard math Yao's minimax principle: a distributional lower bound against deterministic protocols with error ε under a product distribution implies a lower bound for randomized protocols.
    Used in Section 2 to justify proving the lower bound against deterministic protocols under the uniform distribution.
  • standard math Density Restoring Partition lemma (Lemma 15 from [GPW20]) partitions any distribution into structured pieces with controlled loss of min-entropy.
    This is the engine of the subcube-like conversion in Section 3.3 and is cited from the literature rather than reproved.
  • standard math The uniform distribution over each rectangle reached by a deterministic protocol is a product distribution, so min-entropy arguments apply.
    This standard fact is implicit when the paper computes min-entropy deficiencies inside protocol rectangles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication." pith.science (2026). https://pith.science/paper/NZGCYRG5

@misc{pith2026250712124,
  author       = {Pith},
  title        = {Pith review of: Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NZGCYRG5}},
  note         = {Machine review of arXiv:2507.12124}
}
abstract

We show that for a randomly sampled unsatisfiable $O(\log n)$-CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in $n$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 17 canonical work pages

  1. [1]

    Razborov, and Avi Wigderson

    Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Pseudorandom generators in propositional proof complexity. SIAM J. Comput. , 34(1):67--88, 2004. https://doi.org/10.1137/S0097539701389944 doi:10.1137/S0097539701389944

    work page doi:10.1137/s0097539701389944 2004

  2. [2]

    Lower bounds for k-dnf resolution on random 3-cnfs

    Michael Alekhnovich. Lower bounds for k-dnf resolution on random 3-cnfs. Comput. Complex. , 20(4):597--614, 2011. https://doi.org/10.1007/s00037-011-0026-0 doi:10.1007/s00037-011-0026-0

    doi:10.1007/s00037-011-0026-0 2011

  3. [3]

    Razborov

    Michael Alekhnovich and Alexander A. Razborov. Lower bounds for polynomial calculus: N on-binomial case. Proceedings of the Steklov Institute of Mathematics , 242:18--35, 2003. Available at http://people.cs.uchicago.edu/ razborov/files/misha.pdf. Preliminary version in FOCS '01

    work page 2003

  4. [4]

    Karp, Toniann Pitassi, and Michael E

    Paul Beame, Richard M. Karp, Toniann Pitassi, and Michael E. Saks. The efficiency of resolution and davis--putnam procedures. SIAM J. Comput. , 31(4):1048--1075, 2002. https://doi.org/10.1137/S0097539700369156 doi:10.1137/S0097539700369156

    work page doi:10.1137/s0097539700369156 2002

  5. [5]

    Lower bounds for lov[a-acute]sz--schrijver systems and beyond follow from multiparty communication complexity

    Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for lov[a-acute]sz--schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput. , 37(3):845--869, 2007. https://doi.org/10.1137/060654645 doi:10.1137/060654645

    doi:10.1137/060654645 2007

  6. [6]

    Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles

    Paul Beame and Michael Whitmeyer. Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles . In Keren Censor-Hillel, Fabrizio Grandoni, Jo\" e l Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , volume 334 of Leibniz Intern...

    2025

  7. [7]

    Many hard examples for resolution

    Va s ek Chv\' a tal and Endre Szemer \'e di. Many hard examples for resolution. J. ACM , 35(4):759--768, October 1988. URL: http://doi.acm.org/10.1145/48014.48016, https://doi.org/10.1145/48014.48016 doi:10.1145/48014.48016

    work page arXiv 1988

  8. [9]

    de Rezende, Jakob Nordstr \" o m, and Marc Vinyals

    Susanna F. de Rezende, Jakob Nordstr \" o m, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA , pages 295--304. IEEE Comp...

    work page doi:10.1109/focs.2016.40 2016

Show all 40 references
  1. [10]

    Complexity theoretic limitations on learning dnf's

    Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf's. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory , volume 49 of Proceedings of Machine Learning Research , pages 815--830, Columbi...

    2016

  2. [11]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montr \' e al, Qu \' e bec, Canada, May 21-24, 2002 , page 5. IEEE Computer Society, 2002. URL: http://doi.ieeeco...

    2002 arXiv

  3. [12]

    Random ( n) -CNFs are Hard for Cutting Planes

    Noah Fleming, Denis Pankratov, Toniann Pitassi, and Robert Robere. Random ( n) -CNFs are Hard for Cutting Planes . J. ACM , 69(3):19:1--19:32, 2022. https://doi.org/10.1145/3486680 doi:10.1145/3486680

    2022 doi

  4. [13]

    Quantum communication advantage in tfnp

    Mika G\" o \" o s, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in tfnp. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1465–1475, New York, NY, USA, 2025. Association for Computing Machinery. https://doi.org...

    2025

  5. [14]

    Monotone circuit lower bounds from resolution

    Ankit Garg, Mika G \" o \" o s, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput. , 16:1--30, 2020. URL: https://doi.org/10.4086/toc.2020.v016a013, https://doi.org/10.4086/TOC.2020.V016A013 doi:10.4086/TOC.2020.V016A013

    2020 doi

  6. [15]

    Mika G \" o \" o s, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication versus partition number. ACM Trans. Comput. Theory , 10(1):4:1--4:20, 2018. https://doi.org/10.1145/3170711 doi:10.1145/3170711

    2018 doi

  7. [16]

    Extension complexity of independent set polytopes

    Mika G \" o \" o s, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM J. Comput. , 47(1):241--269, 2018. https://doi.org/10.1137/16M109884X doi:10.1137/16M109884X

    2018 doi

  8. [17]

    Adventures in monotone complexity and TFNP

    Mika G \" o \" o s, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP . In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA , volume 124 of LI...

    2019 doi

  9. [18]

    Rectangles are nonnegative juntas

    Mika G \" o \" o s, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM J. Comput. , 45(5):1835--1869, 2016. https://doi.org/10.1137/15M103145X doi:10.1137/15M103145X

    2016 doi

  10. [19]

    Supercritical tradeoffs for monotone circuits

    Mika G\" o \" o s, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov. Supercritical tradeoffs for monotone circuits. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1359–1370, New York, NY, USA, 2025. Association for Computing Machinery....

    2025

  11. [20]

    Hardness condensation by restriction

    Mika G \" o \" o s, Ilan Newman, Artur Riazanov, and Dmitry Sokolov. Hardness condensation by restriction. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-...

    2024

  12. [22]

    Communication lower bounds via critical block sensitivity

    Mika G \" o \" o s and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing , 47(5):1778--1806, 2018. https://doi.org/10.1137/16M1082007 doi:10.1137/16M1082007

    2018 doi

  13. [23]

    Query-to-communication lifting for BPP

    Mika G \" o \" o s, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP . SIAM Journal on Computing , 49(4), 2020. https://doi.org/10.1137/17M115339X doi:10.1137/17M115339X

    2020 doi

  14. [24]

    Linear lower bound on degrees of positivstellensatz calculus proofs for the parity

    Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science , 259(1):613--622, 2001. URL: http://www.sciencedirect.com/science/article/pii/S0304397500001572, https://doi.org/10.1016/S0304-3975(00)00157-2 doi:...

    2001 doi

  15. [25]

    On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity

    Trinh Huynh and Jakob Nordstr \" o m. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Confer...

    2012

  16. [26]

    Random formulas, monotone circuits, and interpolation

    Pavel Hrubes and Pavel Pudl \' a k. Random formulas, monotone circuits, and interpolation. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 121--131. IEEE Computer Society, 2017. ht...

    2017 doi

  17. [27]

    Upper and lower bounds for tree-like cutting planes proofs

    Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart. Upper and lower bounds for tree-like cutting planes proofs. In Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), Paris, France, July 4-7, 1994 , pages 220--228. IEEE Computer Society,...

    1994

  18. [28]

    Proof complexity of natural formulas via communication arguments

    Dmitry Itsykson and Artur Riazanov. Proof complexity of natural formulas via communication arguments. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference) , volume 200 of LIPIcs , pag...

    2021 doi

  19. [29]

    Resolution over linear equations modulo two

    Dmitry Itsykson and Dmitry Sokolov. Resolution over linear equations modulo two. Ann. Pure Appl. Log. , 171(1), 2020. URL: https://doi.org/10.1016/j.apal.2019.102722, https://doi.org/10.1016/J.APAL.2019.102722 doi:10.1016/J.APAL.2019.102722

    2020

  20. [30]

    Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic

    Jan Kraj \' cek. Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. Symb. Log. , 62(2):457--486, 1997. https://doi.org/10.2307/2275541 doi:10.2307/2275541

    1997 doi

  21. [31]

    Monotone circuits for connectivity require super-logarithmic depth

    Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discret. Math. , 3(2):255--265, 1990. https://doi.org/10.1137/0403021 doi:10.1137/0403021

    1990 doi

  22. [32]

    Lifting with sunflowers

    Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA , volume 215 of LIPIcs , page...

    2022 doi

  23. [33]

    Search problems in the decision tree model

    L \' a szl \' o Lov \' a sz, Moni Naor, Ilan Newman, and Avi Wigderson. Search problems in the decision tree model. SIAM J. Discret. Math. , 8(1):119--132, 1995. https://doi.org/10.1137/S0895480192233867 doi:10.1137/S0895480192233867

    1995 doi

  24. [34]

    Analytic and algorithmic solution of random satisfiability problems

    Marc Mezard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science (New York, N.Y.) , 297:812--815, 09 2002. https://doi.org/10.1126/science.1073287 doi:10.1126/science.1073287

    2002 doi

  25. [35]

    Lifting nullstellensatz to monotone span programs over any field

    Toniann Pitassi and Robert Robere. Lifting nullstellensatz to monotone span programs over any field. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, ...

    2018

  26. [36]

    Lower bounds for resolution and cutting plane proofs and monotone computations

    Pavel Pudl \' a k. Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log. , 62(3):981--998, 1997. https://doi.org/10.2307/2275583 doi:10.2307/2275583

    1997 doi

  27. [37]

    Razborov

    Alexander A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Comb. , 10(1):81--93, 1990. https://doi.org/10.1007/BF02122698 doi:10.1007/BF02122698

    1990 doi

  28. [38]

    Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential lower bounds for monotone span programs. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jer...

    2016 doi

  29. [39]

    (semi)algebraic proofs over \( \) 1 variables

    Dmitry Sokolov. (semi)algebraic proofs over \( \) 1 variables. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 2...

    2020

  30. [41]

    A lower bound for k-dnf resolution on random CNF formulas via expansion

    Anastasia Sofronova and Dmitry Sokolov. A lower bound for k-dnf resolution on random CNF formulas via expansion. Electron. Colloquium Comput. Complex. , TR22-054 , 2022. URL: https://eccc.weizmann.ac.il/report/2022/054

    2022

  31. [42]

    Communication Complexity of Set-Intersection Problems and Its Applications

    Shuo Wang, Guangxu Yang, and Jiapeng Zhang. Communication Complexity of Set-Intersection Problems and Its Applications . Technical report, ECCC, 2023. URL: https://eccc.weizmann.ac.il/report/2023/164

    2023

  32. [43]

    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. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 630–639, New York, NY, USA, 2024. Association for Computing Machinery. ht...

    2024

Pith tools

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