Pith. sign in

REVIEW 2 major objections 4 minor 52 references

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis

T0 review · 2 major / 4 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 exact and approximate sparsity of total Boolean functions are polynomially related on the logarithmic scale in the De Morgan basis, up to a log n factor.

desk verdict Confirms the Knop–Lovett–McGuire–Yuan conjecture with a genuinely new adaptive restriction scheme; the central proof holds up, and the remaining issues are small and fixable. read the letter →

arxiv 2507.13963 v1 pith:QINGIMOY submitted 2025-07-18 cs.CC

Arkadev Chattopadhyay , Yogesh Dahiya , Shachar Lovett This is my paper · ORCID
classification cs.CC MSC 68Q1706E30
keywords DeMorganbasisBooleanfunctionspolynomialsparsityapproximaterandomrestrictionsℓ1normgeneralizedmonomialsmonotone
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

Boolean functions have two natural real-polynomial descriptions: an exact one and a pointwise-approximating one. A classic result [44] shows the degrees of the two descriptions are never far apart; this paper proves the same phenomenon for sparsity in the De Morgan basis. For every total Boolean function $f$, it establishes $\log(\mathrm{spar}(f)) = O(\log^2(\widetilde{\mathrm{spar}}(f)) \cdot \log n)$, and the same restriction argument yields $\log(\mathrm{wt}(f)) = O((\log \widetilde{\mathrm{wt}}(f))^2 \log n)$. This confirms the conjecture of [39] that approximation cannot exponentially reduce De Morgan sparsity, in sharp contrast with the Fourier basis, where And is exponentially sparse only approximately. For monotone functions, the paper extends the phenomenon to generalized monomials, with the consequence that deterministic and randomized decision-tree size are polynomially related on the log scale.

What carries the argument

The key object is an adaptive random restriction process, Algorithm 1 (`MaxDegreeRestriction`). It reads the current multilinear polynomial; if some variable can be fixed while retaining almost all $\ell_1$ weight, it fixes it in a passive step, otherwise it takes a random active step: with probability $1/2$ it fixes the chosen variable to 0, and with probability $1/2$ it leaves it free while replacing the polynomial by its discrete derivative. The output distribution leaves $\Omega(\log \mathrm{wt}(f)/\log n)$ free variables, keeps the restricted polynomial at full degree on free variables, and gives monomial degrees an exponential tail $\Pr[\deg(M|_\rho) \ge t] \le 2^{-t}$. The generalized-monomial version replaces full degree by full sensitivity and is driven by Algorithm 2 (`MaxSensitivityRestriction`), which uses a separating set of inputs; both processes are the engine that converts a large exact measure into a large approximate lower bound.

What would settle it

Build or search an explicit family of total Boolean functions and compute $\mathrm{spar}(f)$ and $\widetilde{\mathrm{spar}}_{1/3}(f)$; a single family with $\log \mathrm{spar}(f) / ((\log \widetilde{\mathrm{spar}}_{1/3}(f))^2 \log n) \to \infty$ would falsify Theorem 1.1, and the analogous ratio against $(\log n)^3$ would falsify Theorem 1.8.

Watch

Extended reading notes

Core claim

The central claim is that De Morgan sparsity is polynomially related under approximation: for every total $f$, $\log \mathrm{spar}(f) = O(\log^2 \widetilde{\mathrm{spar}}(f) \cdot \log n)$, and the same proof yields $\log \mathrm{wt}(f) = O((\log \widetilde{\mathrm{wt}}(f))^2 \log n)$. The argument starts from a large exact $\ell_1$ norm and forces any $1/3$-approximating polynomial to have sparsity at least $2^{\Omega(\sqrt{\log \mathrm{wt}(f)/\log n})}$. For monotone functions generalized to monomials built from $x_i$ and $1-x_i$, the paper proves $\log g\mathrm{spar}(f) = O((\log \widetilde{g\mathrm{spar}}(f))^4 (\log n)^3)$ and the analogous weight bound, using separating sets of minterms or maxterms. These results confirm the conjecture of [39] and place deterministic and randomized query complexity, sparsity, and $\ell_1$ norm in one polynomial equivalence class on the log scale in the De Morgan world.

Load-bearing premise

The proof hangs on the theorem that every total Boolean function's exact degree is at most a constant times the square of its approximate degree, with one universal constant serving both in the fixed-constant choice and in the contradiction; the generalized-monomial half additionally assumes the cube-cover bound that turns large exact generalized sparsity into many minterms or maxterms.

Editorial extensions

If this is right

  • Randomized And-decision-tree complexity is characterized by $\log \widetilde{\mathrm{spar}}(f)$ on the log scale: $R^{\wedge}_{\mathrm{dt}}(f) \le D^{\wedge}_{\mathrm{dt}}(f) \le O((\log \widetilde{\mathrm{spar}}(f))^6 \log n)$.
  • Exact and approximate $\ell_1$ norms are quadratically related on the log scale, so a small-weight approximating polynomial forces the exact representation to have weight at most $2^{O((\log \widetilde{\mathrm{wt}}(f))^2 \log n)}$.
  • For monotone functions, generalized sparsity and weight control ordinary decision-tree size, yielding $\log D_{\mathrm{dt}}(f) = O((\log \widetilde{g\mathrm{spar}}(f))^4 (\log n)^3)$, and similarly for weight.
  • Every shifted De Morgan basis inherits the main relation, so approximation cannot exponentially reduce sparsity or weight in any of the $2^n$ shifted bases.
  • Combined with the And-function log-rank result [40], a positive answer to the paper's approximate-rank question would bound deterministic zero-error communication by a polynomial of quantum bounded-error communication for every $f \circ \mathrm{And}_2$.

Reading between the lines

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

  • The same adaptive restriction template could apply to other representation families in Question 1.6, not just De Morgan and generalized monomials; the paper leaves open which families admit the separating structure that makes the argument go through.
  • The threshold function example shows the $\log n$ factor cannot be avoided; a natural search is for families of functions interpolating between Or and thresholds to test whether the quadratic exponent in Theorem 1.1 is also unavoidable.
  • If a matching approximate-rank bound for $f \circ \mathrm{And}_2$ were found, the main theorem would immediately give a polynomial upper bound on zero-error deterministic communication in terms of quantum bounded-error communication; the paper's Question 1.11 is precisely the missing piece.
  • Since the generalized-monomial proof passes through minterms and maxterms, non-monotone functions with few separating sets are the natural candidates for a counterexample to the monotone-style statement; this could be checked by exhaustive search on small cubes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the gap between exact and approximate polynomial representations of total Boolean functions in the De Morgan basis. The main result, Theorem 1.1, states that for every total Boolean function f, log(spar(f)) = O(log^2(~spar(f)) · log n), confirming a conjecture of Knop et al. The proof introduces an adaptive random restriction process, Algorithm 1 (MaxDegreeRestriction), which produces a max-degree distribution for any function with large exact l1-norm: with high probability many variables remain free, the restricted function has full degree, and every monomial's degree under the restriction has an exponential tail bound. The same machinery yields Theorem 1.5, the analogous statement for exact and approximate l1-norm, and Section 4 extends the approach to generalized monomials, proving Theorem 1.8 for monotone functions via separating sets and max-sensitivity distributions. Applications to AND-decision-tree complexity and decision-tree size are derived in Theorem 1.4 and Corollary 1.9.

Significance. If the results are correct, the paper settles an open conjecture and shows that, on a logarithmic scale, approximation does not significantly reduce sparsity or coefficient mass in the De Morgan basis, in sharp contrast to the Fourier basis. The adaptive restriction method is a genuine technical novelty: it applies to arbitrary functions with large algebraic weight rather than to functions with explicit combinatorial structure, and it is developed carefully enough that the main probabilistic claims are verifiable. The derived consequences for AND-query complexity and for decision-tree size of monotone functions are concrete and nontrivial. The paper also gives matching or near-matching examples, including the Or function and the threshold function Thrn_{n-1}, which usefully calibrate the bounds. Overall, this is a strong contribution if the two issues identified below are fixed.

major comments (2)
  1. [§4.3, Claim 4.21] Claim 4.21 is stated without proof and is load-bearing for Theorem 1.8(b) and Corollary 1.9(b), since those results require a lower bound on the approximate generalized weight. The text says only that the proof is omitted because it involves no new ideas. For a journal submission, this is not sufficient: please provide the full argument, adapting the reasoning of Claim 3.9 to max-sensitivity distributions, including the tail-weight Markov step and the constant-error to 1/3-error reduction, or explicitly state and prove a lemma that fills this gap.
  2. [§3.4, Theorem 1.4 and its proof] The stated upper bound in Theorem 1.4 is not justified by the cited ingredients. Combining Claim 3.17, Claim 3.18, and Theorem 1.1 gives D_AND(f) = O((log MBS(f))^2 · log spar(f) · log n) = O((log^2 ~spar(f))^2 · (log^2 ~spar(f) · log n) · log n) = O(log^6 ~spar(f) · log^2 n), not O(log^6 ~spar(f) · log n) as stated. Either restate Theorem 1.4 with log^2 n, or prove an improved version of Claim 3.17 or Claim 3.18 that removes one log n factor; the displayed equality in the proof is currently incorrect.
minor comments (4)
  1. [§3.2, Claim 3.9] The proof invokes Theorem 2.6 to amplify an approximation with error 0.44 to error 1/3, but Theorem 2.6 as stated converts 1/3-error into smaller error. The intended step is a standard constant-degree composition; please add a sentence explaining the direction and the constant-degree error reduction.
  2. [§4.1, Remark 4.8] The remark asserts Cover(f) = M(f) for monotone functions without proof. The derivation of Theorem 4.7 only needs the direction Cover(f) ≤ M(f), which follows from covering each input by a minterm or maxterm subcube. Please either prove the asserted equality or state and use only the needed inequality.
  3. [§4.3, Claim 4.16 proof] The proof says the algorithm halts when |V| = 1, 'which corresponds to |F| ≤ 2', but the base case in Algorithm 2 is |F| ≤ 2 and can occur while |V| is still large. The bound t ≤ n still holds because every recursive call removes one variable from V, but the parenthetical is confusing and should be reworded.
  4. [§4.3] There are minor typographical errors: 'max-sesitivity' appears instead of 'max-sensitivity' in the paragraph after Algorithm 2, and 'sensitvity' appears in Claim 4.20. Please proofread these terms.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem follows from an explicitly constructed adaptive restriction and external degree-approximate degree results, not from its own conclusion or from fitted parameters.

full rationale

The central derivation chain is independent of the result it proves. Theorem 3.7 constructs an ℓ-variable max-degree distribution for any Boolean f with large exact ℓ1-norm using Algorithm 1, and Claim 3.6 proves the three distribution properties (many free variables, full degree, exponential monomial tail) by induction. Claim 3.8 then converts this distribution into a lower bound log Āspar(f)=Ω(√ℓ) by contradiction against the external, previously published degree-approximate-degree relation deg(g)≤c·Ādeg(g)^2 (Aaronson et al., Theorem 2.7); no approximate sparsity value is fitted, renamed, or defined in terms of the conclusion. The same holds for Claim 3.9 for the ℓ1 norm, which additionally uses standard error reduction. Section 4's generalized-monomial results are also not circular: Theorem 4.7 is an external Ehrenfeucht–Haussler bound, the separation properties of minterms/maxterms are proved directly, and Claims 4.20/4.21 reduce a max-sensitivity distribution to the external Nisan–Szegedy sensitivity-approximate-degree theorem. Author self-citations appear only as context or as prior conjectures/equivalences (e.g., [39], [40], [20]) and are not load-bearing in the derivation of Theorem 1.1 or Theorem 1.5. Minor presentational gaps—Claim 4.21 stated without proof, the 0.44-error amplification citing Theorem 2.6 as stated for the opposite direction, and Remark 4.8's Cover(f)=M(f) assertion—are correctness risks, not instances of circular reasoning, and do not change the verdict.

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

The paper's central results are derived from published external theorems (degree versus approximate degree [1], sensitivity versus approximate degree [44], Ehrenfeucht-Haussler decision tree size [26], Grolmusz sparsity-weight conversion [29, 52]) plus standard concentration bounds. No free parameters are fitted to data and no new objects beyond the proof's own definitions are posited.

assumptions (5)
  • standard math deg(g) ≤ c·Ądeg(g)^2 for every total Boolean function g (Aaronson, Ben-David, Kothari, Rao, Tal [1])
    Quoted as Theorem 2.7; used in Claims 3.8, 3.9, 4.20 to make a low-degree approximator contradict the full degree (or sensitivity) of the restricted function.
  • standard math Nisan-Szegedy sensitivity lower bound: Ądeg(g) ≥ sqrt(s(g)/6)
    Used in Claims 3.18 and 4.20 to lower bound approximate degree when the restricted function has full sensitivity.
  • standard math Ehrenfeucht-Haussler bound: log DSize_dt(f) = O(log^2 Cover(f) · log n), and for monotone f, Cover(f) = M(f)
    Used as Theorem 4.7 to infer large minterm/maxterm sets from large exact generalized sparsity; load-bearing for Theorem 1.8.
  • standard math Chernoff concentration bounds and probabilistic method
    Used throughout Claims 3.5, 3.18, 4.16, and the existence of 2/3-separating collections.
  • standard math Grolmusz sparsity-to-weight conversion: log Ąspar(f) = O(log Ąwt(f) + log n)
    Invoked in Remark 3.11 and after Claim 4.20 to transfer sparsity lower bounds to l1 norms; also alternative proof of Theorem 1.5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis." pith.science (2026). https://pith.science/paper/QINGIMOY

@misc{pith2026250713963,
  author       = {Pith},
  title        = {Pith review of: Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QINGIMOY}},
  note         = {Machine review of arXiv:2507.13963}
}
abstract

A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree of a real polynomial that point-wise approximates the function, are at most polynomially separated. Extending this result from degree to other complexity measures like sparsity of the polynomial representation, or total weight of the coefficients, remains poorly understood. In this work, we consider this problem in the De Morgan basis, and prove an analogous result for the sparsity of the polynomials at a logarithmic scale. Our result further implies that the exact $\ell_1$ norm and its approximate variant are also similarly related to each other at a log scale. This is in contrast to the Fourier basis, where the analog of our results are known to be false. Our proof is based on a novel random restriction method. Unlike most existing random restriction methods used in complexity theory, our random restriction process is adaptive and is based on how various complexity measures simplify during the restriction process.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 51 canonical work pages

  1. [1]

    Degree vs

    Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of huang’s sensitivity theorem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1330–1342, 2021

    work page 2021

  2. [2]

    Quantum lower bounds for the collision and the element distinctness problems

    Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004

    work page 2004

  3. [3]

    Spectral norm of symmetric functions

    Anil Ada, Omar Fawzi, and Hamed Hatami. Spectral norm of symmetric functions. In Anupam Gupta, Klaus Jansen, Jos´ e D. P. Rolim, and Rocco A. Servedio, editors,Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, US...

    work page 2012

  4. [4]

    Sparsity lower bounds for probabilistic polynomials

    Josh Alman, Arkadev Chattopadhyay, and Ryan Williams. Sparsity lower bounds for probabilistic polynomials. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA , volume 325 of LIPIcs, pages 3:1–3:25. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025

    work page 2025

  5. [5]

    Quantum lower bounds by polynomials

    Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001

    work page 2001

  6. [6]

    Multiparty communication complexity and threshold circuit size of acˆ0

    Paul Beame and Dang-Trinh Huynh-Ngoc. Multiparty communication complexity and threshold circuit size of acˆ0. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA , pages 53–62. IEEE Computer Society, 2009

    work page 2009

  7. [7]

    Bellantoni, Toniann Pitassi, and Alasdair Urquhart

    Stephen J. Bellantoni, Toniann Pitassi, and Alasdair Urquhart. Approximation and small-depth frege proofs. SIAM J. Comput. , 21(6):1161–1179, 1992

    work page 1992

  8. [8]

    Short proofs are narrow - resolution made simple

    Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow - resolution made simple. J. ACM , 48(2):149–169, 2001

    work page 2001

Show all 52 references
  1. [9]

    Bipartite perfect matching as a real polynomial

    Gal Beniamini and Noam Nisan. Bipartite perfect matching as a real polynomial. In 53rd ACM Symposium on Theory of Computing (STOC) , pages 1118–1131. ACM, 2021

    2021

  2. [10]

    Bounded indistin- guishability and the complexity of recovering secrets

    Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistin- guishability and the complexity of recovering secrets. In International Cryptology Conference, vol- ume LNCS 9816, pages 593–618. Springer, 2016. 29

    2016

  3. [11]

    Mande, Justin Thaler, and Christopher Williamson

    Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate degree, secret sharing and concentration phenomena. In Approximation, Randomization and Com- binatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , volume LIPIcs, 145, pages 7...

    2019

  4. [12]

    Polyomial threshold functions, AC 0 functions, and spec- tral norms (extended abstract)

    Jehoshua Bruck and Roman Smolensky. Polyomial threshold functions, AC 0 functions, and spec- tral norms (extended abstract). In 31st Annual Symposium on Foundations of Computer Science (FOCS), volume II, pages 632–641. IEEE, 1990

    1990

  5. [13]

    Polynomial threshold functions, acˆ0 functions, and spectral norms

    Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, acˆ0 functions, and spectral norms. SIAM Journal on Computing , 21(1):33–42, 1992

    1992

  6. [14]

    Communication complexity lower bounds by polynomials

    Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001 , pages 120–130. IEEE Computer Society, 2001

    2001

  7. [15]

    Complexity measures and decision tree complexity: a survey

    Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. , 288(1):21–43, 2002

    2002

  8. [16]

    The polynomial method strikes back: Tight quantum query bounds via dual polynomials

    Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. Theory Comput., 16:1–71, 2020

    2020

  9. [17]

    Approximate degree in classical and quantum computing

    Mark Bun and Justin Thaler. Approximate degree in classical and quantum computing. Found. Trends Theor. Comput. Sci. , 15(3-4):229–423, 2022

    2022

  10. [18]

    Faster private release of marginals on small databases

    Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan. Faster private release of marginals on small databases. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 387–402, 2014

    2014

  11. [19]

    Multiparty communication complexity of disjointness

    Arkadev Chattopadhyay and Anil Ada. Multiparty communication complexity of disjointness. Elec- tron. Colloquium Comput. Complex. , TR08-002, 2008

    2008

  12. [20]

    Randomized versus deterministic decision tree size

    Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S Mande, Jaikumar Radhakrishnan, and Swagato Sanyal. Randomized versus deterministic decision tree size. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 867–880, 2023

    2023

  13. [21]

    Arkadev Chattopadhyay and Nikhil S. Mande. Dual polynomials and communication complexity of XOR functions. Electron. Colloquium Comput. Complex. , TR17-062, 2017

    2017

  14. [22]

    Arkadev Chattopadhyay and Nikhil S. Mande. A lifting theorem with applications to symmetric functions. In Satya V. Lokam and R. Ramanujam, editors, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15,...

    2017

  15. [23]

    Mande, and Suhail Sherif

    Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. J.ACM, 67(4):1–28, 2020

    2020

  16. [24]

    A lower bound on the trace norm of boolean matrices and its applications

    Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley. A lower bound on the trace norm of boolean matrices and its applications. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages 37–1. Schloss D...

    2025

  17. [25]

    Bounded independence fools halfspaces

    Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A Servedio, and Emanuele Viola. Bounded independence fools halfspaces. SIAM Journal on Computing , 39(8):3441–3462, 2010

    2010

  18. [26]

    Learning decision trees from random examples

    Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Informa- tion and Computation , 82(3):231 – 246, 1989. Earlier version in COLT’88

    1989

  19. [27]

    Furst, James B

    Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory , 17(1):13–27, 1984. 30

    1984

  20. [28]

    Boolean functions with small spectral norm

    Ben Green and Tom Sanders. Boolean functions with small spectral norm. Geometric and Functional Analysis, 18:144 – 162, 2008

    2008

  21. [29]

    On the power of circuits with gates of low l1 norms

    Vince Grolmusz. On the power of circuits with gates of low l1 norms. Theoretical computer science, 188(1-2):117–128, 1997

    1997

  22. [30]

    Almost optimal lower bounds for small depth circuits

    Johan H ˚ astad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, edi- tor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA , pages 6–20. ACM, 1986

    1986

  23. [31]

    On small-depth frege proofs for PHP

    Johan H ˚ astad. On small-depth frege proofs for PHP. In64th IEEE Annual Symposium on Founda- tions of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 37–49. IEEE, 2023

    2023

  24. [32]

    Servedio, and Li-Yang Tan

    Johan H ˚ astad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for boolean circuits. J. ACM, 64(5):35:1–35:27, 2017

    2017

  25. [33]

    Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

    Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. CoRR, abs/1907.00847, 2019

    1907 arXiv

  26. [34]

    Lower bounds for the polynomial calculus and the gr¨ obner basis algorithm.Comput

    Russell Impagliazzo, Pavel Pudl´ ak, and Jir ´ ı Sgall. Lower bounds for the polynomial calculus and the gr¨ obner basis algorithm.Comput. Complex. , 8(2):127–144, 1999

    1999

  27. [35]

    Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics

    Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012

    2012

  28. [36]

    Agnostically learning halfspaces

    Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing , 37(6):1777–1805, 2008

    2008

  29. [37]

    Lower bounds for quantum communication complexity

    Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM J. Comput. , 37(1):20–46, 2007

    2007

  30. [38]

    Learning dnf in time 2˜ o (n1/3)

    Adam R Klivans and Rocco A Servedio. Learning dnf in time 2˜ o (n1/3). Journal of Computer and System Sciences, 68(2):303–318, 2004

    2004

  31. [39]

    Guest column: Models of computation between decision trees and communication

    Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Guest column: Models of computation between decision trees and communication. ACM SIGACT News , 52(2):46–70, 2021

    2021

  32. [40]

    Log-rank and lifting for and- functions

    Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Log-rank and lifting for and- functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 197–208, 2021

    2021

  33. [41]

    Jan Kraj ´ ıcek, Pavel Pudl´ ak, and Alan R. Woods. An exponenetioal lower bound to the size of bounded depth frege proofs of the pigeonhole principle. Random Struct. Algorithms , 7(1):15–40, 1995

    1995

  34. [42]

    Disjointness is hard in the multiparty number-on-the-forehead model

    Troy Lee and Adi Shraibman. Disjointness is hard in the multiparty number-on-the-forehead model. Comput. Complex. , 18(2):309–336, 2009

    2009

  35. [43]

    The demand query model for bipartite matching

    Noam Nisan. The demand query model for bipartite matching. In Proceedings of the 2021 ACM- SIAM Symposium on Discrete Algorithms (SODA) , pages 592–599. ACM, 2021

    2021

  36. [44]

    On the degree of boolean functions as real polynomials

    Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Compu- tational complexity, 4:301–313, 1994

    1994

  37. [45]

    Exponential lower bounds for the pigeonhole principle

    Toniann Pitassi, Paul Beame, and Russell Impagliazzo. Exponential lower bounds for the pigeonhole principle. Comput. Complex. , 3:97–140, 1993

    1993

  38. [46]

    Quantum communication complexity of symmetric predicates

    Alexander Razborov. Quantum communication complexity of symmetric predicates. Izvestiya:Mathematics, 67(1):145–159, 2003

    2003

  39. [47]

    Sherstov

    Alexander A. Sherstov. On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput. , 10(5&6):435–455, 2010. 31

    2010

  40. [48]

    Sherstov

    Alexander A. Sherstov. The pattern matrix method. SIAM J. Comput. , 40(6):1969–2000, 2011

    1969

  41. [49]

    Sherstov

    Alexander A. Sherstov. Communication lower bounds using directional derivatives. J. ACM , 61(6):34:1–34:71, 2014

    2014

  42. [50]

    Quantum communication complexity of block-composed functions

    Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Inf. Comput. , 9(5&6):444–460, 2009

    2009

  43. [51]

    Faster algorithms for privately releasing marginals

    Justin Thaler, Jonathan Ullman, and Salil Vadhan. Faster algorithms for privately releasing marginals. In International Colloquium on Automata, Languages, and Programming , pages 810–

  44. [52]

    Efficient quantum protocols for xor functions

    Shengyu Zhang. Efficient quantum protocols for xor functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1878–1885. SIAM, 2014. 32

    2014

Pith tools

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