Average-case lower bounds and satisfiability algorithms for small threshold circuits
From MaRDI portal
(Redirected from Publication:4568115)
Average-case lower bounds and satisfiability algorithms for small threshold circuits (scientific article; zbMATH DE number 6890210)
Average-case lower bounds and satisfiability algorithms for small threshold circuits (scientific article; zbMATH DE number 6890210)
Recommendations
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Size--Depth Tradeoffs for Threshold Circuits
- Approximating threshold circuits by rational functions
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Exponential lower bound for bounded depth circuits with few threshold gates
Cites work
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- A tail bound for read-k families of functions
- Algebrization: a new barrier in complexity theory
- Analysis of Boolean Functions
- Approximating threshold circuits by rational functions
- Average sensitivity and noise sensitivity of polynomial threshold functions
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Average-case lower bounds for formula size
- Bounded Independence Fools Halfspaces
- Concentration Inequalities and Martingale Inequalities: A Survey
- Concentration of Measure for the Analysis of Randomized Algorithms
- Constant depth circuits, Fourier transform, and learnability
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Every linear threshold function has a low-weight approximator
- Exponential lower bound for bounded depth circuits with few threshold gates
- Hardness amplification within NP
- Hardness vs randomness
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 773997 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- Large deviations for sums of partly dependent random variables
- Learning and lower bounds for AC\(^{0}\) with threshold gates
- Learning intersections and thresholds of halfspaces
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Mathematical Foundations of Computer Science 2004
- Mining circuit lower bound proofs for meta-algorithms
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Natural proofs
- Nonuniform ACC circuit lower bounds
- Parity, circuits, and the polynomial-time hierarchy
- Pseudorandom bits for constant depth circuits
- Rational approximation techniques for analysis of neural networks
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Size--Depth Tradeoffs for Threshold Circuits
- Spectral properties of threshold functions
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- The Chow parameters problem
- The expressive power of voting polynomials
- The number of trees
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
Cited in
(17)- Upper bound for torus polynomials
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Circuit size lower bounds and \#SAT upper bounds through a general framework
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- An average-case depth hierarchy theorem for Boolean circuits
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- A short list of equalities induces large sign-rank
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Size, Depth and Energy of Threshold Circuits Computing Parity Function.
- Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
This page was built for publication: Average-case lower bounds and satisfiability algorithms for small threshold circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568115)
