Average-case lower bounds and satisfiability algorithms for small threshold circuits

DOI10.4086/TOC.2018.V014A009zbMATH Open1395.68138DBLPjournals/toc/ChenS018OpenAlexW3105381258WikidataQ55950641 ScholiaQ55950641MaRDI QIDQ4568115FDOQ4568115

Authors: 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

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

zbMATH Keywords

learningcomplexity theorySATcircuit complexitythreshold functionsrandom restrictionscorrelation bounds

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Hardness vs randomness
• Size--Depth Tradeoffs for Threshold Circuits
• Analysis of Boolean Functions
• Concentration Inequalities and Martingale Inequalities: A Survey
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Spectral properties of threshold functions
• The expressive power of voting polynomials
• The number of trees
• Constant depth circuits, Fourier transform, and learnability
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• Parity, circuits, and the polynomial-time hierarchy
• Concentration of Measure for the Analysis of Randomized Algorithms
• Pseudorandom bits for constant depth circuits
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Title not available (Why is that?)
• Natural proofs
• Bounded Independence Fools Halfspaces
• Large deviations for sums of partly dependent random variables
• Mining circuit lower bound proofs for meta-algorithms
• Average-case lower bounds for formula size
• Algebrization: a new barrier in complexity theory
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Approximating threshold circuits by rational functions
• Every linear threshold function has a low-weight approximator
• The Chow parameters problem
• Rational approximation techniques for analysis of neural networks
• Learning intersections and thresholds of halfspaces
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Learning and lower bounds for AC\(^{0}\) with threshold gates
• Exponential lower bound for bounded depth circuits with few threshold gates
• Hardness amplification within NP
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• A tail bound for read-\(k\) families of functions
• Mathematical Foundations of Computer Science 2004
• Title not available (Why is that?)
• Nonuniform ACC circuit lower bounds
• 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
• Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates

Cited In (17)

• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Size, Depth and Energy of Threshold Circuits Computing Parity Function.
• Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
• 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\)
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• A short list of equalities induces large sign-rank
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• An average-case depth hierarchy theorem for Boolean circuits
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

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)