pith. sign in

arxiv: 2606.03249 · v1 · pith:4LZGXEK7new · submitted 2026-06-02 · 💻 cs.CC · quant-ph

Quantum-Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya , Farzan Byramji , Arkadev Chattopadhyay , Yogesh Dahiya , Shachar Lovett This is my paper

Pith reviewed 2026-06-28 07:40 UTC · model grok-4.3

classification 💻 cs.CC quant-ph
keywords communication complexityquantum communicationAND functionsDe Morgan sparsityBoolean functionstotal functionsRazborov conjecture
0
0 comments X

The pith

For every Boolean function f, the bounded-error quantum and classical deterministic communication complexities of f composed with AND are polynomially related up to polylog factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that quantum communication protocols cannot be exponentially more powerful than classical deterministic ones when computing functions built by composing an arbitrary Boolean function f with pairwise AND operations. This extends Razborov's 2002 result, which was limited to symmetric outer functions f, to the general case. The key step is showing that both the quantum bounded-error complexity and the classical deterministic complexity are characterized, up to a polynomial factor, by the logarithm of the De Morgan sparsity of f. A reader should care because this settles a major open problem in quantum communication complexity for a broad class of total Boolean functions.

Core claim

For every Boolean function f, both the bounded-error quantum communication complexity and the classical deterministic communication complexity of F(x, y) = f(x1 ∧ y1, ..., xn ∧ yn) are polynomially related up to polylogarithmic factors in n. This is established by proving that each is characterized up to polynomial loss by the logarithm of the De Morgan sparsity of f. The result builds on structural characterizations of non-sparse Boolean functions.

What carries the argument

The logarithm of the De Morgan sparsity of the outer function f, which serves as a common characterization for both quantum and classical communication complexities up to polynomial factors.

If this is right

  • The quantum and classical complexities are at most polynomially larger than the log De Morgan sparsity.
  • They are at least the log De Morgan sparsity divided by a polynomial factor.
  • This equivalence holds for all Boolean functions f, not just symmetric ones.
  • It implies that there is no exponential quantum advantage for computing such AND-functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar polynomial relations might exist for other gate compositions like OR.
  • De Morgan sparsity could be useful for analyzing communication complexity in other settings.
  • The extension of the structural characterizations might apply to related problems in circuit complexity.

Load-bearing premise

The structural characterizations of non-sparse Boolean functions can be extended to resolve the conjecture for general AND-functions.

What would settle it

Identification of a Boolean function f for which the bounded-error quantum communication complexity of f ∘ AND₂ exceeds a polynomial in the logarithm of its De Morgan sparsity, or differs superpolynomially from the classical complexity.

Figures

Figures reproduced from arXiv: 2606.03249 by Arkadev Chattopadhyay, Farzan Byramji, Shachar Lovett, Sreejata Kishor Bhattacharya, Yogesh Dahiya.

Figure 1
Figure 1. Figure 1: A semi-adaptive max-degree restriction tree for [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
read the original abstract

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims to resolve the open problem of polynomial equivalence between bounded-error quantum and classical deterministic communication complexity for all AND-functions of the form F(x,y) = f(x1 ∧ y1, ..., xn ∧ yn). It proves that both complexities are characterized up to polynomial loss by the logarithm of the De Morgan sparsity of f, by extending the structural characterizations of non-sparse Boolean functions from Chattopadhyay, Dahiya, and Lovett (2025).

Significance. If correct, this settles a major open question in quantum communication complexity posed since Razborov (2002), establishing that quantum protocols cannot be exponentially more efficient than classical deterministic ones for the entire class of AND-functions (up to polylog n factors). The sparsity-based characterization provides a strong structural tool and gives concrete evidence supporting the broader conjecture that no exponential quantum-classical separation exists for total Boolean functions.

major comments (2)
  1. [Abstract and §1] Abstract (final sentence) and §1: The central claim depends on extending the structural results of Chattopadhyay-Dahiya-Lovett (2025) to obtain the communication-complexity characterization for general f. The manuscript must explicitly delineate which parts of the 2025 characterization are used verbatim, which are extended, and how the extension controls the polylogarithmic factors in n; without this, the polynomial relation cannot be verified as load-bearing.
  2. The reduction from communication complexity to De Morgan sparsity (and vice versa) is stated to hold up to polynomial loss, but the precise loss factors and their dependence on the sparsity parameter are not shown to be independent of the particular extension steps from the 2025 paper.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed reading and for identifying areas where greater explicitness would strengthen the presentation. We agree that the manuscript would benefit from a clearer breakdown of the relationship to Chattopadhyay-Dahiya-Lovett (2025) and will revise accordingly. Below we respond point by point.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract (final sentence) and §1: The central claim depends on extending the structural results of Chattopadhyay-Dahiya-Lovett (2025) to obtain the communication-complexity characterization for general f. The manuscript must explicitly delineate which parts of the 2025 characterization are used verbatim, which are extended, and how the extension controls the polylogarithmic factors in n; without this, the polynomial relation cannot be verified as load-bearing.

    Authors: We accept this observation. The current draft states that we extend the 2025 structural results but does not provide a dedicated paragraph or subsection that separates verbatim citations, the precise technical extensions required for the AND-function communication setting, and the tracking of polylog(n) factors through those extensions. In the revised manuscript we will insert such a delineation (likely as a new subsection of §1 or an appendix table) that lists each 2025 lemma or theorem used, indicates whether it is applied directly or modified, and shows that the resulting polylogarithmic overhead remains independent of the particular extension steps and is absorbed into the overall polynomial loss. revision: yes

  2. Referee: [—] The reduction from communication complexity to De Morgan sparsity (and vice versa) is stated to hold up to polynomial loss, but the precise loss factors and their dependence on the sparsity parameter are not shown to be independent of the particular extension steps from the 2025 paper.

    Authors: We agree that the current text does not explicitly verify independence of the loss factors from the extension steps. The revised version will contain an expanded analysis (in the section presenting the reductions) that isolates the loss terms arising from the 2025 structural results, shows that these terms depend only on the sparsity parameter s(f) and on n through polylog factors already bounded in the 2025 work, and confirms that no additional dependence is introduced by our extensions. This will make the claimed polynomial relation fully verifiable from the stated bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on extending structural characterizations from the 2025 paper by overlapping authors (Chattopadhyay, Dahiya, Lovett), but this prior result is a separate publication providing independent support. The current work performs the extension to general AND-functions and derives the polynomial relation via the log De Morgan sparsity characterization. No step reduces by construction to a self-definition, fitted input renamed as prediction, or unverified self-citation chain; the central claim has new content from the extension. This matches the default expectation of no circularity for papers building on prior independent work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract; the central claim rests on the validity and extendability of the 2025 structural characterization result.

axioms (1)
  • domain assumption Structural characterizations of non-sparse Boolean functions from Chattopadhyay, Dahiya, and Lovett (2025) hold and extend to general AND-functions.
    The abstract states the new result is proved by extending this prior work.

pith-pipeline@v0.9.1-grok · 5788 in / 1326 out tokens · 20844 ms · 2026-06-28T07:40:41.229944+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

146 extracted references · 42 canonical work pages

  1. [1]

    2009 , url =

    Sanjeev Arora and Boaz Barak , title =. 2009 , url =

    2009

  2. [2]

    Sherstov , title =

    Alexander A. Sherstov , title =. 2016 , url =

    2016

  3. [3]

    Vereshchagin and Ronald de Wolf , title =

    Harry Buhrman and Nikolai K. Vereshchagin and Ronald de Wolf , title =. 22nd Annual. 2007 , url =

    2007

  4. [4]

    Spectral Norm of Symmetric Functions , booktitle =

    Anil Ada and Omar Fawzi and Hamed Hatami , editor =. Spectral Norm of Symmetric Functions , booktitle =. 2012 , url =. doi:10.1007/978-3-642-32512-0\_29 , timestamp =

    work page doi:10.1007/978-3-642-32512-0 2012

  5. [5]

    Quantum Log-Approximate-Rank Conjecture is Also False , booktitle =

    Anurag Anshu and Naresh Goud Boddu and Dave Touchette , editor =. Quantum Log-Approximate-Rank Conjecture is Also False , booktitle =

  6. [6]

    Mande , title =

    Arkadev Chattopadhyay and Nikhil S. Mande , title =. Electron. Colloquium Comput. Complex. , volume =. 2017 , url =. TR17-062 , timestamp =

    2017

  7. [7]

    Scott Aaronson and Yaoyun Shi , title =. J. 2004 , url =. doi:10.1145/1008731.1008735 , timestamp =

    work page doi:10.1145/1008731.1008735 2004

  8. [8]

    Robert Beals and Harry Buhrman and Richard Cleve and Michele Mosca and Ronald de Wolf , title =. J. 2001 , url =. doi:10.1145/502090.502097 , timestamp =

    work page doi:10.1145/502090.502097 2001

  9. [9]

    Multiparty Communication Complexity and Threshold Circuit Size of AC

    Paul Beame and Dang. Multiparty Communication Complexity and Threshold Circuit Size of AC. 50th Annual. 2009 , url =. doi:10.1109/FOCS.2009.12 , timestamp =

    work page doi:10.1109/focs.2009.12 2009

  10. [10]

    Harry Buhrman and Ronald de Wolf , title =. Theor. Comput. Sci. , volume =. 2002 , url =. doi:10.1016/S0304-3975(01)00144-X , timestamp =

    work page doi:10.1016/s0304-3975(01)00144-x 2002

  11. [11]

    Theory Comput

    Mark Bun and Robin Kothari and Justin Thaler , title =. Theory Comput. , volume =. 2020 , url =. doi:10.4086/TOC.2020.V016A010 , timestamp =

    work page doi:10.4086/toc.2020.v016a010 2020

  12. [12]

    Mark Bun and Justin Thaler , title =. Found. Trends Theor. Comput. Sci. , volume =. 2022 , url =. doi:10.1561/0400000107 , timestamp =

    work page doi:10.1561/0400000107 2022

  13. [13]

    6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities,

    James Aspnes and Eric Blais and Murat Demirbas and Ryan O'Donnell and Atri Rudra and Steve Uurtamo , title =. 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities,. 2010 , url =. doi:10.1007/978-3-642-16988-5\_7 , timestamp =

    work page doi:10.1007/978-3-642-16988-5 2010

  14. [14]

    Short proofs are narrow - resolution made simple , journal =

    Eli Ben. Short proofs are narrow - resolution made simple , journal =. 2001 , url =. doi:10.1145/375827.375835 , timestamp =

    work page doi:10.1145/375827.375835 2001

  15. [15]

    31st Annual Symposium on Foundations of Computer Science (FOCS) , volume =

    Jehoshua Bruck and Roman Smolensky , title =. 31st Annual Symposium on Foundations of Computer Science (FOCS) , volume =

  16. [16]

    Sparsity Lower Bounds for Probabilistic Polynomials , booktitle =

    Josh Alman and Arkadev Chattopadhyay and Ryan Williams , editor =. Sparsity Lower Bounds for Probabilistic Polynomials , booktitle =. 2025 , url =. doi:10.4230/LIPICS.ITCS.2025.3 , timestamp =

    work page doi:10.4230/lipics.itcs.2025.3 2025

  17. [17]

    Quantum Log-Approximate-Rank Conjecture is Also False , booktitle =

    Anurag Anshu and Naresh Goud Boddu and Dave Touchette , editor =. Quantum Log-Approximate-Rank Conjecture is Also False , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00063 , timestamp =

    work page doi:10.1109/focs.2019.00063 2019

  18. [18]

    Quantum Inf

    Yaoyun Shi and Yufan Zhu , title =. Quantum Inf. Comput. , volume =. 2009 , url =. doi:10.26421/QIC9.5-6-7 , timestamp =

    work page doi:10.26421/qic9.5-6-7 2009

  19. [19]

    Electron

    Arkadev Chattopadhyay and Anil Ada , title =. Electron. Colloquium Comput. Complex. , volume =. 2008 , url =. TR08-002 , timestamp =

    2008

  20. [20]

    Mande and Suhail Sherif , title =

    Arkadev Chattopadhyay and Nikhil S. Mande and Suhail Sherif , title =. J.ACM , volume =. 2020 , publisher =

    2020

  21. [21]

    Lower Bounds for the Polynomial Calculus and the Gr

    Russell Impagliazzo and Pavel Pudl. Lower Bounds for the Polynomial Calculus and the Gr. Comput. Complex. , volume =. 1999 , url =. doi:10.1007/S000370050024 , timestamp =

    work page doi:10.1007/s000370050024 1999

  22. [22]

    Information Processing Letters , volume =

    Avrim Blum , title =. Information Processing Letters , volume =. 1992 , url =. doi:10.1016/0020-0190(92)90237-P , timestamp =

    work page doi:10.1016/0020-0190(92)90237-p 1992

  23. [23]

    Language and Automata Theory and Applications - 8th International Conference

    Javier Esparza and Michael Luttenberger and Maximilian Schlund , title =. Language and Automata Theory and Applications - 8th International Conference. 2014 , url =. doi:10.1007/978-3-319-04921-2\_1 , timestamp =

    work page doi:10.1007/978-3-319-04921-2 2014

  24. [24]

    Learning Decision Trees from Random Examples , booktitle =

    Andrzej Ehrenfeucht and David Haussler , editor =. Learning Decision Trees from Random Examples , booktitle =. 1988 , url =

    1988

  25. [25]

    Learning decision trees from random examples

    Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation. 1989. doi:https://doi.org/10.1016/0890-5401(89)90001-1

    work page doi:10.1016/0890-5401(89)90001-1 1989

  26. [26]

    28th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Generic oracles and oracle classes , author=. 28th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 1987 , organization=

    1987

  27. [27]

    Query complexity, or why is it difficult to separate

    Tardos, G. Query complexity, or why is it difficult to separate. Combinatorica , volume=. 1989 , publisher=

    1989

  28. [28]

    One-way functions and the nonisomorphism of

    Hartmanis, Juris and Hemachandra, Lane A , journal=. One-way functions and the nonisomorphism of. 1991 , publisher=

    1991

  29. [29]

    2007 , url =

    Hartmut Klauck , title =. 2007 , url =. doi:10.1137/S0097539702405620 , timestamp =

    work page doi:10.1137/s0097539702405620 2007

  30. [30]

    Troy Lee and Adi Shraibman , title =. Comput. Complex. , volume =. 2009 , url =. doi:10.1007/S00037-009-0276-2 , timestamp =

    work page doi:10.1007/s00037-009-0276-2 2009

  31. [31]

    Sherstov , title =

    Alexander A. Sherstov , title =. 2011 , url =. doi:10.1137/080733644 , timestamp =

    work page doi:10.1137/080733644 2011

  32. [32]

    Sherstov , title =

    Alexander A. Sherstov , title =. J. 2014 , url =. doi:10.1145/2629334 , timestamp =

    work page doi:10.1145/2629334 2014

  33. [33]

    Sherstov , title =

    Alexander A. Sherstov , title =. Quantum Inf. Comput. , volume =. 2010 , url =. doi:10.26421/QIC10.5-6-5 , timestamp =

    work page doi:10.26421/qic10.5-6-5 2010

  34. [34]

    2012 , url =

    Stasys Jukna , title =. 2012 , url =. doi:10.1007/978-3-642-24508-4 , isbn =

    work page doi:10.1007/978-3-642-24508-4 2012

  35. [35]

    Chicago Journal of Theoretical Computer Science , volume=

    Ashley Montanaro , title=. Chicago Journal of Theoretical Computer Science , volume=

  36. [36]

    Exponential Separation between Quantum Communication and Logarithm of Approximate Rank , booktitle =

    Makrand Sinha and Ronald de Wolf , editor =. Exponential Separation between Quantum Communication and Logarithm of Approximate Rank , booktitle =

  37. [37]

    On Computing Boolean Functions by Sparse Real Polynomials , booktitle =

    Matthias Krause and Pavel Pudl. On Computing Boolean Functions by Sparse Real Polynomials , booktitle =

  38. [38]

    Mande , editor =

    Arkadev Chattopadhyay and Nikhil S. Mande , editor =. A Lifting Theorem with Applications to Symmetric Functions , booktitle =

  39. [39]

    Eyal Kushilevitz and Noam Nisan , title =

  40. [40]

    Noam Nisan , title =

  41. [41]

    Linear decision lists and partitioning algorithms for the construction of neural networks

    Tur \'a n, Gy \"o rgy and Vatan, Farrokh. Linear decision lists and partitioning algorithms for the construction of neural networks. Foundations of Computational Mathematics. 1997

    1997

  42. [42]

    Deductive Learning

    Leslie G. Valiant , title =. Communications of the. 1984 , url =. doi:10.1145/1968.1972 , timestamp =

    work page doi:10.1145/1968.1972 1984

  43. [43]

    41st International Conference on Current Trends in Theory and Practice of Computer Science

    Kei Uchizawa and Eiji Takimoto , title =. 41st International Conference on Current Trends in Theory and Practice of Computer Science. 2015 , url =. doi:10.1007/978-3-662-46078-8\_34 , timestamp =

    work page doi:10.1007/978-3-662-46078-8 2015

  44. [44]

    International Conference on Theory and Applications of Satisfiability Testing , pages=

    Unified characterisations of resolution hardness measures , author=. International Conference on Theory and Applications of Satisfiability Testing , pages=. 2014 , organization=

    2014

  45. [45]

    Information Processing Letters , volume=

    A combinatorial characterization of treelike resolution space , author=. Information Processing Letters , volume=. 2003 , publisher=

    2003

  46. [46]

    A lower bound for

    Pudl. A lower bound for. Proceedings of the eleventh annual ACM-SIAM Symposium on Discrete Algorithms

  47. [47]

    Electron

    Oliver Kullmann , title =. Electron. Colloquium Comput. Complex. , number =. 1999 , url =

    1999

  48. [48]

    Near Optimal Separation Of Tree-Like And General Resolution , journal =

    Eli Ben. Near Optimal Separation Of Tree-Like And General Resolution , journal =. 2004 , url =

    2004

  49. [49]

    Information Processing Letters , volume =

    Olaf Beyersdorff and Nicola Galesi and Massimo Lauria , title =. Information Processing Letters , volume =. 2013 , url =

    2013

  50. [50]

    On the Pseudo-Deterministic Query Complexity of

    Shafi Goldwasser and Russell Impagliazzo and Toniann Pitassi and Rahul Santhanam , editor =. On the Pseudo-Deterministic Query Complexity of. 36th Computational Complexity Conference

  51. [51]

    Electron

    Oded Goldreich and Shafi Goldwasser and Dana Ron , title =. Electron. Colloquium Comput. Complex. , pages =. 2012 , url =

    2012

  52. [52]

    On the possibilities and limitations of pseudodeterministic algorithms , booktitle =

    Oded Goldreich and Shafi Goldwasser and Dana Ron , editor =. On the possibilities and limitations of pseudodeterministic algorithms , booktitle =. 2013 , note =

    2013

  53. [53]

    Penghui Yao , title =. Chic. J. Theor. Comput. Sci. , volume =. 2016 , url =

    2016

  54. [54]

    Lifting Dichotomies , booktitle =

    Yaroslav Alekseev and Yuval Filmus and Alexander Smal , editor =. Lifting Dichotomies , booktitle =. 2024 , url =. doi:10.4230/LIPICS.CCC.2024.9 , timestamp =

    work page doi:10.4230/lipics.ccc.2024.9 2024

  55. [55]

    Mande and Swagato Sanyal and Suhail Sherif , editor =

    Nikhil S. Mande and Swagato Sanyal and Suhail Sherif , editor =. One-Way Communication Complexity and Non-Adaptive Decision Trees , booktitle =. 2022 , url =. doi:10.4230/LIPICS.STACS.2022.49 , timestamp =

    work page doi:10.4230/lipics.stacs.2022.49 2022

  56. [56]

    51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages =

    Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar and Ostuni, Anthony , title =. 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.ICALP.2024.82 , annote =

    work page doi:10.4230/lipics.icalp.2024.82 2024

  57. [57]

    Podolskii and Dmitrii Sluch , editor =

    Vladimir V. Podolskii and Dmitrii Sluch , editor =. One-Way Communication Complexity of Partial. 51st International Colloquium on Automata, Languages, and Programming,. 2024 , url =. doi:10.4230/LIPICS.ICALP.2024.116 , timestamp =

    work page doi:10.4230/lipics.icalp.2024.116 2024

  58. [58]

    CoRR , volume =

    Ashley Montanaro and Tobias Osborne , title =. CoRR , volume =. 2009 , url =. 0909.3392 , timestamp =

    Pith/arXiv arXiv 2009

  59. [59]

    On Query-To-Communication Lifting for Adversary Bounds , booktitle =

    Anurag Anshu and Shalev Ben. On Query-To-Communication Lifting for Adversary Bounds , booktitle =. 2021 , url =. doi:10.4230/LIPICS.CCC.2021.30 , timestamp =

    work page doi:10.4230/lipics.ccc.2021.30 2021

  60. [60]

    2021 , url =

    Arkadev Chattopadhyay and Yuval Filmus and Sajin Koroth and Or Meir and Toniann Pitassi , title =. 2021 , url =. doi:10.1137/19M1310153 , timestamp =

    work page doi:10.1137/19m1310153 2021

  61. [61]

    Query-to-Communication Lifting for

    Mika G. Query-to-Communication Lifting for. 2020 , url =. doi:10.1137/17M115339X , timestamp =

    work page doi:10.1137/17m115339x 2020

  62. [62]

    32nd Computational Complexity Conference (CCC 2017) , pages =

    G\". 32nd Computational Complexity Conference (CCC 2017) , pages =. 2017 , volume =. doi:10.4230/LIPIcs.CCC.2017.12 , annote =

    work page doi:10.4230/lipics.ccc.2017.12 2017

  63. [63]

    Electron

    Eran Gat and Shafi Goldwasser , title =. Electron. Colloquium Comput. Complex. , pages =

  64. [64]

    CoRR , volume=

    Hao Huang , title =. CoRR , volume=

  65. [65]

    Razborov , title =

    Michael Alekhnovich and Alexander A. Razborov , title =. 42nd Annual Symposium on Foundations of Computer Science

  66. [66]

    Buss and Dima Grigoriev and Russell Impagliazzo and Toniann Pitassi , title =

    Samuel R. Buss and Dima Grigoriev and Russell Impagliazzo and Toniann Pitassi , title =. J. Comput. Syst. Sci. , volume =

  67. [67]

    39th Annual Symposium on Foundations of Computer Science

    Dima Grigoriev , title =. 39th Annual Symposium on Foundations of Computer Science

  68. [68]

    SIAM Journal on Computing , volume=

    The efficiency of resolution and Davis--Putnam procedures , author=. SIAM Journal on Computing , volume=. 2002 , publisher=

    2002

  69. [69]

    Random Structures & Algorithms , volume=

    Space complexity of random formulae in resolution , author=. Random Structures & Algorithms , volume=. 2003 , publisher=

    2003

  70. [70]

    Theoretical Computer Science , volume=

    Complexity measures and decision tree complexity: a survey , author=. Theoretical Computer Science , volume=. 2002 , publisher=

    2002

  71. [71]

    International Cryptology Conference , pages =

    Bogdanov, Andrej and Ishai, Yuval and Viola, Emanuele and Williamson, Christopher , title =. International Cryptology Conference , pages =

  72. [72]

    and Thaler, Justin and Williamson, Christopher , title =

    Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher , title =. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages =

  73. [73]

    Lower Bounds by Probabilistic Arguments (Extended Abstract) , booktitle =

    Andrew Chi. Lower Bounds by Probabilistic Arguments (Extended Abstract) , booktitle =

  74. [74]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Log-rank and lifting for AND-functions , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  75. [75]

    SIAM Journal on Discrete Mathematics , volume=

    Search problems in the decision tree model , author=. SIAM Journal on Discrete Mathematics , volume=. 1995 , publisher=

    1995

  76. [76]

    Combinatorica , volume=

    Near optimal separation of tree-like and general resolution , author=. Combinatorica , volume=. 2004 , publisher=

    2004

  77. [77]

    Information Processing Letters , volume=

    A characterization of tree-like resolution size , author=. Information Processing Letters , volume=. 2013 , publisher=

    2013

  78. [78]

    Short proofs are narrow - resolution made simple , journal =

    Eli Ben. Short proofs are narrow - resolution made simple , journal =. 2001 , url =

    2001

  79. [79]

    36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) , year=

    Lifting theorems for equality , author=. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) , year=

    2019

  80. [80]

    ACM SIGACT News , volume=

    Guest Column: Models of computation between decision trees and communication , author=. ACM SIGACT News , volume=. 2021 , publisher=

    2021

Showing first 80 references.