Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is ed > 0 such that Parity has correlation at most 1/nΩ(1) with depth-d threshold circuits which have at most n1+ed wires, and the Generalized Andreev Function has correlation at most 1/2nΩ(1) with depth-d threshold circuits which have at most n1+ed wires. Previously, only worst-case lower bounds in this setting were known [22]. We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-d threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC0 circuits with no(1) general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential-time learning algorithms for AC0 with no(1) threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth. Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.

• Publication year

  2016

• Venue

  Cybersecurity and Cyberforensics Conference

• Publication date

  2016-05-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4086/toc.2018.v014a009arXiv 1806.06290
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• No references are available for this paper.

• #SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank

  2025cites this paper
• Theoretical limitations of multi-layer Transformer

  2024cites this paper
• The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

  2024cites this paper
• Trade-Offs Between Energy and Depth of Neural Networks

  2024cites this paper
• Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees

  2023influential citation
• MidBit+, Torus Polynomials and Non-classical Polynomials: Equivalences for ACC Lower Bounds

  2023cites this paper
• The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity

  2022influential citation
• Quantified Derandomization: How to Find Water in the Ocean

  2022cites this paper
• Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees

  2022cites this paper
• Improved pseudorandom generators for AC0 circuits

  2022cites this paper
• Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs

  2022cites this paper
• Fooling Constant-Depth Threshold Circuits

  2021cites this paper
• Upper Bound for Torus Polynomials

  2021cites this paper
• The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

  2021cites this paper
• How to Find Water in the Ocean: A Survey on Quantified Derandomization

  2021cites this paper
• Circuit Complexity of Visual Search

  2021cites this paper
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

  2021cites this paper
• Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy

  2021cites this paper
• A level set based topology optimization for finite unidirectional acoustic phononic structures using boundary element method

  2021cites this paper
• Profit maximization for competitive social advertising

  2021cites this paper
• Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost

  2021cites this paper
• Size, Depth and Energy of Threshold Circuits Computing Parity Function

  2020cites this paper
• Algorithms and lower bounds for de morgan formulas of low-communication leaf gates

  2020cites this paper
• Sharp threshold results for computational complexity

  2020cites this paper
• Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

  2019cites this paper
• Bootstrapping results for threshold circuits “just beyond” known lower bounds

  2019cites this paper
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials

  2018cites this paper
• A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

  2018cites this paper
• Satisfiability and Derandomization for Small Polynomial Threshold Circuits

  2018cites this paper
• The Gotsman-Linial Conjecture is False

  2018cites this paper
• Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering

  2018cites this paper
• N ov 2 01 7 Quantified Derandomization of Linear Threshold Circuits

  2018cites this paper
• A Short List of Equalities Induces Large Sign Rank

  2018cites this paper
• Fooling Intersections of Low-Weight Halfspaces

  2017cites this paper
• Weights at the Bottom Matter When the Top is Heavy

  2017cites this paper
• Circuit Complexity: New Techniques and Their Limitations

  2017cites this paper
• Quantified derandomization of linear threshold circuits

  2017influential citation
• Lower bounds over Boolean inputs for deep neural networks with ReLU gates

  2017cites this paper
• Gate elimination: Circuit size lower bounds and #SAT upper bounds

  2017cites this paper
• A polynomial restriction lemma with applications

  2017influential citation
• A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

  2016influential citation
• Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework

  2016cites this paper
• Polynomial Representations of Threshold Functions and Algorithmic Applications

  2016cites this paper
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

  2015cites this paper