pith. sign in

arxiv: 2606.12631 · v1 · pith:RWWIXXOXnew · submitted 2026-06-10 · 💻 cs.CC

The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier

Bruno Loff , Suhail Sherif , Navid Talebanfard , Francesca Ugazio This is my paper

Pith reviewed 2026-06-27 07:22 UTC · model grok-4.3

classification 💻 cs.CC
keywords natural proofsAC0 circuitsswitching lemmacircuit lower boundspseudorandom generatorsunconditional barriersconstant-depth circuits
0
0 comments X

The pith

No AC0-natural proof can establish AC0 lower bounds stronger than 2 to the power n to the 7 over d minus 5.

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

The paper proves an unconditional barrier showing that any lower-bound argument whose distinguisher is itself an AC0 circuit cannot prove that depth-d circuits require size larger than 2^{n^{7/(d-5)}}. The argument proceeds by localizing the Trevisan-Xue pseudorandom generator so that its security against AC0 distinguishers follows from the Switching Lemma. Because the Switching Lemma itself supplies an AC0 distinguisher, the same lemma is used to show that proofs relying on it cannot cross this quantitative threshold. The result places the best known unconditional AC0 lower bounds and the natural-proofs barrier in the same exponent regime, differing only in the precise constant inside the power of n.

Core claim

By localizing the Trevisan-Xue pseudorandom generator, the authors show that no AC0-natural proof can prove a lower bound greater than 2^{n^{7/(d-5)}} against depth-d circuits. The localization ensures that the generator's security against AC0 distinguishers can be established directly from the Switching Lemma, which is itself an AC0-natural technique. This creates a self-referential limit: the Switching Lemma demonstrates that Switching-Lemma-based proofs cannot improve upon the Switching-Lemma frontier.

What carries the argument

Localization of the Trevisan-Xue pseudorandom generator, whose AC0 security is proven via the Switching Lemma.

If this is right

  • AC0-natural proofs cannot improve the exponent in the Switching-Lemma lower bound from 1/(d-1) to anything larger than 7/(d-5).
  • Lower-bound proofs that rely on the Switching Lemma, or on most other known AC0 techniques, are subject to this unconditional quantitative ceiling.
  • Any attempt to prove stronger AC0 lower bounds via a natural proof must employ a distinguisher outside AC0.

Where Pith is reading between the lines

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

  • Improving the Switching-Lemma exponent may require lower-bound arguments whose distinguishers lie outside AC0.
  • The same localization technique could be applied to other pseudorandom generators to obtain barriers with different exponents or against other circuit classes.
  • The self-referential character suggests that similar barriers may exist for other proof techniques whose security proofs rely on the same machinery they are trying to surpass.

Load-bearing premise

The Trevisan-Xue pseudorandom generator admits a localization whose security against AC0 distinguishers follows from the Switching Lemma.

What would settle it

An explicit AC0 circuit that distinguishes the localized Trevisan-Xue generator from uniform random strings with advantage exceeding the bound implied by the Switching Lemma would falsify the barrier.

Figures

Figures reproduced from arXiv: 2606.12631 by Bruno Loff, Francesca Ugazio, Navid Talebanfard, Suhail Sherif.

Figure 1
Figure 1. Figure 1: The circuit construction for the PRG from Lemma 23. [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The construction of a circuit that on input [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
read the original abstract

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us with a distinguisher, namely, an efficient algorithm which can distinguish easy functions from random functions. They called such lower-bound proofs natural proofs. They then showed a natural-proofs barrier: under standard cryptographic assumptions, natural proofs cannot show superpolynomial lower-bounds against Boolean circuits. Along similar lines it can be shown that under a suitable cryptographic assumption, natural proofs cannot significantly improve the current state-of-the-art lower bound against constant depth circuits (AC0). The state of the art, using H\r{a}stad's Switching Lemma (SL), is $2^{n^{1/(d-1)}}$ for depth-$d$ circuits, and (conditionally) no natural proof can prove lower bounds of $2^{n^{c/d}}$ for some large constant $c$. In this paper we revisit the natural-proofs barrier from an $\textit{unconditional}$ perspective. We focus on AC0-natural proofs, i.e. proofs whose distinguishers are computable by AC0 circuits. Razborov and Rudich observed that lower bounds based on SL are AC0-natural. We show that this is true for most known lower-bound techniques against constant-depth circuits. We then establish an unconditional barrier for such proofs. By localizing the Trevisan--Xue pseudorandom generator, we are able to show that no AC0-natural proof can prove a lower bound greater than $2^{n^{7/(d-5)}}$ against depth-$d$ circuits. This is in the same quantitative regime as the SL frontier which instead has $1/(d-1)$ in the power of $n$. The proof has a striking self-referential aspect: the proof of security of the Trevisan--Xue generator crucially relies on SL, and so SL has been used to show that AC0-natural proofs, such as SL itself, cannot prove AC0 lower bounds better than that of SL.

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 / 1 minor

Summary. The paper claims an unconditional natural-proofs barrier for AC0-natural proofs (distinguishers in AC0) against depth-d circuits. By localizing the Trevisan-Xue PRG (whose security proof relies on Håstad's Switching Lemma), it shows that no such proof can establish a lower bound stronger than 2^{n^{7/(d-5)}}, which is quantitatively close to the SL frontier of 2^{n^{1/(d-1)}}. The argument is self-referential: SL is used both to prove the PRG security and to conclude that SL-based (hence AC0-natural) proofs cannot beat this bound by much.

Significance. If the localization step succeeds with only polynomial losses that preserve AC0 security reductions, the result supplies a strong unconditional barrier in the AC0 setting and highlights a self-referential limitation on the Switching Lemma itself. This is a notable contribution because it converts a conditional barrier into an unconditional one while remaining in the same quantitative regime as existing SL-based lower bounds.

major comments (2)
  1. [Localization of Trevisan-Xue PRG] Localization construction (abstract and the paragraph on localization of the PRG): the claim that any AC0 distinguisher for the localized generator yields (via the SL-based analysis) an AC0 distinguisher for the original generator with only polynomial losses must be verified explicitly. If the localization introduces even one extra layer or a non-AC0 query pattern, the resulting distinguisher would no longer be AC0 and the barrier would not apply to AC0-natural proofs.
  2. [Abstract] Derivation of the exponent 7/(d-5) (abstract): the quantitative bound is load-bearing for the central claim. The paper must show the precise parameter accounting—how the polynomial losses from localization combine with the SL analysis to produce exactly the numerator 7 rather than a worse constant—because even modest hidden losses would change the exponent and weaken the comparison to the 1/(d-1) SL frontier.
minor comments (1)
  1. The abstract states that 'most known lower-bound techniques against constant-depth circuits' are AC0-natural but provides no enumeration or reference list; adding a short table or subsection identifying the specific techniques would improve clarity without affecting the main argument.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments both concern clarity of the localization argument and its quantitative consequences; we address them point-by-point below and will incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Localization of Trevisan-Xue PRG] Localization construction (abstract and the paragraph on localization of the PRG): the claim that any AC0 distinguisher for the localized generator yields (via the SL-based analysis) an AC0 distinguisher for the original generator with only polynomial losses must be verified explicitly. If the localization introduces even one extra layer or a non-AC0 query pattern, the resulting distinguisher would no longer be AC0 and the barrier would not apply to AC0-natural proofs.

    Authors: Section 3 of the manuscript already contains the explicit localization construction (replacing each seed bit by a small AC0 function whose parameters are chosen so that the overall distinguisher remains depth-3) together with the reduction showing that an AC0 distinguisher for the localized generator yields, after a polynomial-size AC0 post-processing step, an AC0 distinguisher for the original Trevisan-Xue generator. The reduction itself does not invoke the switching lemma; the lemma appears only in the security proof of the base generator. We will add a single clarifying sentence in the abstract and a short remark at the end of Section 3 that explicitly states the depth and size bounds preserved by the reduction. revision: yes

  2. Referee: [Abstract] Derivation of the exponent 7/(d-5) (abstract): the quantitative bound is load-bearing for the central claim. The paper must show the precise parameter accounting—how the polynomial losses from localization combine with the SL analysis to produce exactly the numerator 7 rather than a worse constant—because even modest hidden losses would change the exponent and weaken the comparison to the 1/(d-1) SL frontier.

    Authors: The precise accounting appears in the proof of Theorem 1.1 (Section 4). The localization incurs an n^O(1) size overhead whose exponent is absorbed into the switching-lemma analysis; after substituting the concrete parameters of the Trevisan-Xue generator and simplifying the resulting expression for the maximum hardness that an AC0 distinguisher can certify, one obtains the numerator 7 in the exponent 7/(d-5). We agree that the abstract alone does not display this calculation and will add a short paragraph immediately after the statement of the main theorem that walks through the arithmetic step by step. revision: yes

Circularity Check

0 steps flagged

No circularity: barrier derived from independent prior PRG security

full rationale

The derivation localizes the Trevisan-Xue PRG (prior work by different authors) whose AC0 security is established via the standard Switching Lemma; the resulting unconditional barrier on AC0-natural proofs is then obtained from that security reduction. No equation reduces a claimed prediction to a fitted parameter by construction, no self-citation by the present authors is load-bearing for the central exponent 7/(d-5), and the self-referential remark about SL is merely an observation rather than a definitional or fitted-input step. The argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result relies on standard definitions of AC0 and natural proofs together with the security of a localized version of an existing PRG; no free parameters or new entities are introduced.

axioms (2)
  • standard math Standard definitions and closure properties of AC0 circuits and of AC0-natural proofs
    Invoked to delineate the class of proofs to which the barrier applies.
  • domain assumption Security of the (localized) Trevisan-Xue PRG against AC0 distinguishers
    Serves as the external benchmark from which the barrier is derived.

pith-pipeline@v0.9.1-grok · 5943 in / 1395 out tokens · 42635 ms · 2026-06-27T07:22:08.774143+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Syntactic Separation Implies Computational Indistinguishability: An Abstract Obstruction Theorem

    cs.LO 2026-06 unverdicted novelty 5.0

    Syntactic separation of Skolem functions in local systems implies computational indistinguishability with Omega(n) or Omega(2^n) derivation lower bounds, presented as an abstract obstruction governing Natural Proofs, ...

Reference graph

Works this paper leans on

66 extracted references · 2 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Is P versus NP formally independent?Bulletin of the EATCS, 81(109-136):70, 2003

    Scott Aaronson. Is P versus NP formally independent?Bulletin of the EATCS, 81(109-136):70, 2003

    2003

  2. [2]

    Σ1 1-formulae on finite structures.Annals of Pure and Applied Logic, 24(1):1–48, 1983

    Mikl´ os Ajtai. Σ1 1-formulae on finite structures.Annals of Pure and Applied Logic, 24(1):1–48, 1983

    1983

  3. [3]

    A theorem on probabilistic constant depth computations

    Mikl´ os Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. InProceedings of the 16th STOC, 1984

    1984

  4. [4]

    Deterministic simulation of probabilistic constant depth circuits

    Miklos Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant depth circuits. InProceedings of the 26th FOCS, 1985

    1985

  5. [5]

    Alexander E. Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity ofπ-schemes.Moscow University Mathematics Bulletin, 42(1):24–29, 1987. Vestnik Moskov. Univ. Ser. 1: Mat. Mekh. 1987(1) 70–73 (Russian original on Math-net.ru) MR 0883632

    1987

  6. [6]

    Lower bounds for recognizing small cliques on CRCW PRAM’s.Discrete applied mathematics, 29(1):3–20, 1990

    Paul Beame. Lower bounds for recognizing small cliques on CRCW PRAM’s.Discrete applied mathematics, 29(1):3–20, 1990

    1990

  7. [7]

    A switching lemma primer

    Paul Beame. A switching lemma primer. Technical report, Technical Report UW-CSE-95-07- 01, Department of Computer Science and Engineering, University of Washington, 1994

    1994

  8. [8]

    Ravi B. Boppana. The average sensitivity of bounded-depth circuits.Information Processing Letters, 63(5):257–261, 1997

    1997

  9. [9]

    Polylogarithmic independence fools AC0 circuits.Journal of the ACM, 57(5), 2008

    Mark Braverman. Polylogarithmic independence fools AC0 circuits.Journal of the ACM, 57(5), 2008

    2008

  10. [10]

    On the existence of algebraically natural proofs

    Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, and Anamay Tengse. On the existence of algebraically natural proofs. InProceedings of the 61st FOCS, 2020

    2020

  11. [11]

    Circuit lower bounds for MCSP from local pseudorandom generators.ACM Transactions on Computation Theory, 12(3):21:1–21:27, 2020

    Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit lower bounds for MCSP from local pseudorandom generators.ACM Transactions on Computation Theory, 12(3):21:1–21:27, 2020. 25

    2020

  12. [12]

    Fine-grained cryp- tography

    Akshay Degwekar, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Fine-grained cryp- tography. InAnnual International Cryptology Conference, pages 533–562, 2016

    2016

  13. [13]

    The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity

    Zhiyuan Fan, Jiatu Li, and Tianqi Yang. The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity. InProceedings of the 54th STOC, pages 962–975, 2022

    2022

  14. [14]

    Furst, James B

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

    1984

  15. [15]

    Computing approximate majority in AC0.https://www.wisdom.weizmann

    Oded Goldreich. Computing approximate majority in AC0.https://www.wisdom.weizmann. ac.il/~oded/PDF/approx-maj.pdf, 2023. Accessed: 2026-03-18

    2023

  16. [16]

    Top-down lower bounds for depth-four circuits

    Mika G¨ o¨ os, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov. Top-down lower bounds for depth-four circuits. InProceedings of the 64th FOCS, 2023

    2023

  17. [17]

    Towards an algebraic natural proofs barrier via polynomial identity testing.ArXiv preprintarXiv:1701.01717, 2017

    Joshua A Grochow, Mrinal Kumar, Michael Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing.ArXiv preprintarXiv:1701.01717, 2017

    Pith/arXiv arXiv 2017

  18. [18]

    Saks, and Navid Tale- banfard

    Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudl´ ak, Michael E. Saks, and Navid Tale- banfard. Local enumeration and majority lower bounds. InProceedings of the 39th CCC, 2024

    2024

  19. [19]

    Almost optimal lower bounds for small depth circuits

    Johan H˚ astad. Almost optimal lower bounds for small depth circuits. InProceedings of the 18th STOC, 1986

    1986

  20. [20]

    MIT Press, 1987

    Johan H˚ astad.Computational Limitations of Small-Depth Circuits. MIT Press, 1987

    1987

  21. [21]

    The shrinkage exponent of De Morgan formulas is 2.SIAM Journal on Com- puting, 27(1):48–64, 1998

    Johan H˚ astad. The shrinkage exponent of De Morgan formulas is 2.SIAM Journal on Com- puting, 27(1):48–64, 1998

    1998

  22. [22]

    A slight sharpening of LMN.Journal of Computer and System Sciences, 63(3):498–508, 2001

    Johan H˚ astad. A slight sharpening of LMN.Journal of Computer and System Sciences, 63(3):498–508, 2001

    2001

  23. [23]

    On the correlation of parity and small-depth circuits.SIAM Journal on Com- puting, 43(5):1699–1708, 2014

    Johan H˚ astad. On the correlation of parity and small-depth circuits.SIAM Journal on Com- puting, 43(5):1699–1708, 2014

    2014

  24. [24]

    Top-down lower bounds for depth 3 circuits

    Johan Hastad, Stasys Jukna, and Pavel Pudl´ ak. Top-down lower bounds for depth 3 circuits. InProceedings of the 34th FOCS, 1993

    1993

  25. [25]

    Almost optimal lower bounds for small depth circuits

    John H˚ astad. Almost optimal lower bounds for small depth circuits. InProceedings of the 18th STOC, 1986

    1986

  26. [26]

    Paradigms for unconditional pseudorandom generators

    Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024

    2024

  27. [27]

    Constant-depth circuits for arithmetic in finite fields of characteristic two

    Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. InProceedings of 23rd STACS, 2006

    2006

  28. [28]

    NP-hardness of the minimum circuit size problem from well-studied assumptions

    Shuichi Hirahara and Rahul Ilango. NP-hardness of the minimum circuit size problem from well-studied assumptions. In66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 1648–1664. IEEE, 2025. 26

    2025

  29. [29]

    Oliveira, and Rahul Santhanam

    Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. InProceedings of the 33rd CCC, 2018

    2018

  30. [30]

    On the average-case complexity of MCSP and its variants

    Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of MCSP and its variants. InProceedings of the 32nd CCC, 2017

    2017

  31. [31]

    Constant depth formula and partial function versions of MCSP are hard.SIAM Journal on Computing, 53(6):S20–317, 2024

    Rahul Ilango. Constant depth formula and partial function versions of MCSP are hard.SIAM Journal on Computing, 53(6):S20–317, 2024

    2024

  32. [32]

    A satisfiability algorithm for AC0

    Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC0. InProceedings of the 23rd SODA, 2012

    2012

  33. [33]

    The effect of random restrictions on formula size.Random Structures & Algorithms, 4(2):121–134, 1993

    Russell Impagliazzo and Noam Nisan. The effect of random restrictions on formula size.Random Structures & Algorithms, 4(2):121–134, 1993

    1993

  34. [34]

    An explicit lower bound of 5n−o(n) for boolean circuits

    Kazuo Iwama and Hiroki Morizumi. An explicit lower bound of 5n−o(n) for boolean circuits. InProceedings of the 27th MFSC, 2002

    2002

  35. [35]

    A method of obtaining lower bounds for the complexity of π-schemes.Mathematical Notes of the Academi of Sciences of the USSR, 10:474–479, 1971

    Valerii Mikhailovich Khrapchenko. A method of obtaining lower bounds for the complexity of π-schemes.Mathematical Notes of the Academi of Sciences of the USSR, 10:474–479, 1971. Matem. Zametki 10(1) 83-92, 1971 (Russian original on Math-net.ru)

    1971

  36. [36]

    Stronger cell probe lower bounds via local PRGs.Proceedings of 66th FOCS, 2025

    Oliver Korten, Toniann Pitassi, and Russell Impagliazzo. Stronger cell probe lower bounds via local PRGs.Proceedings of 66th FOCS, 2025

    2025

  37. [37]

    The natural-proofs barrier against data-structure lower-bounds.Unpublished, 2026

    Michal Kouck´ y, Bruno Loff, Tulasimohan Molli, and Mike Saks. The natural-proofs barrier against data-structure lower-bounds.Unpublished, 2026

    2026

  38. [38]

    Explicit lower bound of 4.5n−o(n) for boolean circuits

    Oded Lachish and Ran Raz. Explicit lower bound of 4.5n−o(n) for boolean circuits. In Proceedings of the 33rd STOC, 2001

    2001

  39. [39]

    Constant depth circuits, Fourier transform, and learnability.Journal of the ACM, 40(3):607–620, 1993

    Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability.Journal of the ACM, 40(3):607–620, 1993

    1993

  40. [40]

    Prediction from partial information and hindsight, with applica- tion to circuit lower bounds.Computational Complexity, 28(2):145–183, 2019

    Or Meir and Avi Wigderson. Prediction from partial information and hindsight, with applica- tion to circuit lower bounds.Computational Complexity, 28(2):145–183, 2019

    2019

  41. [41]

    Explicit proofs and the flip.ArXiv preprintarXiv:1009.0246, 2010

    Ketan Mulmuley. Explicit proofs and the flip.ArXiv preprintarXiv:1009.0246, 2010

    Pith/arXiv arXiv 2010

  42. [42]

    E. I. Neˇ ciporuk. On a Boolean function.Doklady of the Academy of Sciences of the USSR, 169(4):765–766 (in Russian), 1966. English translation in Soviet Mathematics Doklady 7:4, pages 999-1000

    1966

  43. [43]

    Hardness vs randomness.Journal of Computer and System Sciences, 49(2):149–167, 1994

    Noam Nisan and Avi Wigderson. Hardness vs randomness.Journal of Computer and System Sciences, 49(2):149–167, 1994

    1994

  44. [44]

    Shrinkage of De Morgan formulae under restriction.Random Structures & Algorithms, 4(2):135–150, 1993

    Mike Paterson and Uri Zwick. Shrinkage of De Morgan formulae under restriction.Random Structures & Algorithms, 4(2):135–150, 1993

    1993

  45. [45]

    Saks, and Francis Zane

    Ramamohan Paturi, Pavel Pudl´ ak, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm fork-SAT.Journal of the ACM, 52(3):337–364, 2005

    2005

  46. [46]

    Satisfiability coding lemma.Chicago Journal of Theoretical Computer Science, 1999

    Ramamohan Paturi, Pavel Pudl´ ak, and Francis Zane. Satisfiability coding lemma.Chicago Journal of Theoretical Computer Science, 1999. 27

    1999

  47. [47]

    Saks, and Francis Zane

    Ramamohan Paturi, Michael E. Saks, and Francis Zane. Exponential lower bounds for depth three boolean circuits.Computational Complexity, 9(1):1–15, 2000

    2000

  48. [48]

    Coding for Sunflowers.Discrete Analysis, 2020

    Anup Rao. Coding for Sunflowers.Discrete Analysis, 2020

    2020

  49. [49]

    A note on natural-proofs for super-linear lower bounds for linear functions.ECCC, 2026

    Ran Raz. A note on natural-proofs for super-linear lower bounds for linear functions.ECCC, 2026

    2026

  50. [50]

    Lower bounds for deterministic and nondeterministic branching pro- grams

    Alexander A Razborov. Lower bounds for deterministic and nondeterministic branching pro- grams. InFCT, 1991

    1991

  51. [51]

    Natural proofs.Journal of Computer and System Sciences, 55(1):24–35, 1997

    Alexander A Razborov and Steven Rudich. Natural proofs.Journal of Computer and System Sciences, 55(1):24–35, 1997

    1997

  52. [52]

    On the constant-depth complexity of k-clique

    Benjamin Rossman. On the constant-depth complexity of k-clique. InProceedings of the 40th STOC, 2008

    2008

  53. [53]

    The average sensitivity of bounded-depth formulas.Computational Com- plexity, 27(2):209–223, 2018

    Benjamin Rossman. The average sensitivity of bounded-depth formulas.Computational Com- plexity, 27(2):209–223, 2018

    2018

  54. [54]

    Prediction from partial information and hindsight, an alternative proof.Information Processing Letters, 136:102–104, 2018

    Alexander V Smal and Navid Talebanfard. Prediction from partial information and hindsight, an alternative proof.Information Processing Letters, 136:102–104, 2018

    2018

  55. [55]

    Realizations of linear functions by formulas using∨, &, −

    Bella Abramovna Subbotovskaya. Realizations of linear functions by formulas using∨, &, −. Sov. Math., Dokl., 2:110–112, 1961. Doklady Akad. Nauk SSSR 136(3), 553–555, 1961 (Russian original on Math-net.ru)

    1961

  56. [56]

    Shrinkage of De Morgan formulae by spectral techniques

    Avishay Tal. Shrinkage of De Morgan formulae by spectral techniques. InProceedings of the 55th FOCS, 2014

    2014

  57. [57]

    Tight bounds on the fourier spectrum of AC0

    Avishay Tal. Tight bounds on the fourier spectrum of AC0. InProceedings of the 32nd CCC, 2017

    2017

  58. [58]

    A derandomized switching lemma and an improved deran- domization of AC0

    Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved deran- domization of AC0. InProceedings of the 29th CCC, 2013

    2013

  59. [59]

    Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. InProceedings 6th MFCS, 1977

    1977

  60. [60]

    Separating the polynomial-time hierarchy by oracles

    Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles. InProceeding of the 26th FOCS, 1985. A Deferred Proofs A.1 From the preliminaries We stated this folklore proposition about PRFs. Proposition 5.Letµ 1 be a distribution onN 1 bit strings thatϵ 1-fools a class of algorithmsAthat is closed under restrictions and padding. Similarly def...

    1985

  61. [61]

    For anyI⊆[N 1], the marginal ofµ 1 to the indicesIwill alsoϵ-foolA. 28

  62. [62]

    The distributionµ 1 ×µ 2 will also(ϵ 1 +ϵ 2)-foolA. (In particularµ 1 ×Unif N2 continues to ϵ1-foolA.) Proof.The first item is true since if an algorithm inAcan distinguish a marginal ofµ 1 from uniform, it can be used as-is to distinguishµ 1 from uniform. The second item is a classic use case of the hybrid argument. Note that for any algorithmA∈ A, we ha...

  63. [63]

    6Consider the functionf k : ({0,1} ⌈logm⌉ )k → {0,1} ⌈logm⌉ , where the inputs are interpreted asa 1,

    (A similar argument works using∧ i∈[n] ∨j∈[n] bi,j instead.) This completes the proof. 6Consider the functionf k : ({0,1} ⌈logm⌉ )k → {0,1} ⌈logm⌉ , where the inputs are interpreted asa 1, . . . , ak ∈[m], that computes P i∈[k] ai (with the promise that the sum is always at mostm). Since there are onlyk⌈logm⌉input bits, each output bit of the function can...

  64. [64]

    [27] shows that computingy 2i is quite easy: 2i j is even for everyj̸= 0 or 2 i, so ify= P yhxh, theny 2i = P h yhxh2i

    Healy et al. [27] shows that computingy 2i is quite easy: 2i j is even for everyj̸= 0 or 2 i, so ify= P yhxh, theny 2i = P h yhxh2i . We can store, for eachh∈[n] andi∈[⌊logk⌋], the elementsx h2i . Hencey 2i is then-bit string whoserth bit is⊕ {h:(xh2i)r=1}yh. Hence the circuit computingy7→(y 1, y2, y4, . . . , y2⌊logk⌋ ) is implemented in parallel byn⌊log...

  65. [65]

    This is the multiplication oft≤ 1 +⌊logk⌋terms:α (i) and the appropriatey 2j s

    Now we want to compute an element of the formα (i)yi. This is the multiplication oft≤ 1 +⌊logk⌋terms:α (i) and the appropriatey 2j s. Following [27] we compute this with a circuit for iterated multiplication oftelementsβ (1), . . . , β(t) ∈F 2[x], only afterwards reducing it to F. The iterated multiplication is done via the Discrete Fourier Transform. Let...

  66. [66]

    negated bottom fan-in

    Usingkcopies of the circuit above we construct eachα (i)yi ∈F. We now sum up over allk terms to get Pk−1 i=0 α(i)yi. This is achieved bynparallel parities of arityk, and that is our output. Looking at the above construction we get a circuit with the following layers witht= 1 +⌊logk⌋ andm=⌈log(nt)⌉: •n⊕ k gates, •kn⊕ nt gates, •knt⊕ nt gates, •kn 2t2mCNFs ...