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

DOI10.4086/toc.2018.v014a009zbMath1395.68138OpenAlexW3105381258WikidataQ55950641 ScholiaQ55950641MaRDI QIDQ4568115

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

Publication date: 15 June 2018

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a009

zbMATH Keywords

learningthreshold functionscircuit complexitycomplexity theoryrandom restrictionsSATcorrelation bounds

Mathematics Subject Classification ID

Related Items (7)

A Short List of Equalities Induces Large Sign-Rank ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ Unnamed Item ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Upper bound for torus polynomials ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bound for bounded depth circuits with few threshold gates
• Learning intersections and thresholds of halfspaces
• Pseudorandom bits for constant depth circuits
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Spectral properties of threshold functions
• The expressive power of voting polynomials
• Approximating threshold circuits by rational functions
• Hardness vs randomness
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Mining circuit lower bound proofs for meta-algorithms
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• Every linear threshold function has a low-weight approximator
• The number of trees
• Pseudorandom Generators for Polynomial Threshold Functions
• Algebrization
• The Chow Parameters Problem
• Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
• Constant depth circuits, Fourier transform, and learnability
• Nonuniform ACC Circuit Lower Bounds
• A tail bound for read-kfamilies of functions
• Parity, circuits, and the polynomial-time hierarchy
• Concentration Inequalities and Martingale Inequalities: A Survey
• Learning and Lower Bounds for AC 0 with Threshold Gates
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Rational approximation techniques for analysis of neural networks
• Size--Depth Tradeoffs for Threshold Circuits
• Large deviations for sums of partly dependent random variables
• Analysis of Boolean Functions
• Mathematical Foundations of Computer Science 2004
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Bounded Independence Fools Halfspaces
• Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
• Average-case lower bounds for formula size
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Concentration of Measure for the Analysis of Randomized Algorithms
• Natural proofs
• Hardness amplification within NP

This page was built for publication: Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits