A satisfiability algorithm for AC^0

Recommendations

Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
The complexity of satisfiability of small depth circuits
Correlation bounds and \#SAT algorithms for small linear-size circuits
scientific article; zbMATH DE number 1452705
Average-case lower bounds and satisfiability algorithms for small threshold circuits

Cites work

3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
An algorithm for the satisfiability problem of formulas in conjunctive normal form
An improved exponential-time algorithm for k -SAT
scientific article; zbMATH DE number 1452705 (Why is no real title available?)
scientific article; zbMATH DE number 2090309 (Why is no real title available?)
scientific article; zbMATH DE number 806753 (Why is no real title available?)
scientific article; zbMATH DE number 5937218 (Why is no real title available?)
Improving exhaustive search implies superpolynomial lower bounds
Solving satisfiability in less than \(2^ n\) steps
The complexity of satisfiability of small depth circuits
Top-down lower bounds for depth-three circuits

Cited in

(46)

Local reduction
Gate elimination: circuit size lower bounds and \#SAT upper bounds
Fourier concentration from shrinkage
Satisfiability algorithm for syntactic read-\(k\)-times branching programs
CNF satisfiability in a subspace and related problems
A \#SAT algorithm for small constant-depth circuits with PTF gates
Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
Mining circuit lower bound proofs for meta-algorithms
Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
Circuit lower bounds from learning-theoretic approaches
The relative exponential time complexity of approximate counting satisfying assignments
The relative exponential time complexity of approximate counting satisfying assignments
Correlation bounds and \#SAT algorithms for small linear-size circuits
An improved deterministic \#SAT algorithm for small De Morgan formulas
Correlation bounds and \#SAT algorithms for small linear-size circuits
A moderately exponential time algorithm for \(k\)-IBDD satisfiability
Approximating Boolean functions with depth-2 circuits
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
The complexity of satisfiability of small depth circuits
On polynomial approximations to \(\mathrm{AC}^0\)
What circuit classes can be learned with non-trivial savings?
Bounded independence plus noise fools products
Agnostic Learning from Tolerant Natural Proofs
Tighter connections between Formula-SAT and shaving logs
Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
AC complement problems: Satisfiability and negation elimination
A \#SAT algorithm for small constant-depth circuits with PTF gates
Criticality of regular formulas
Satisfiability algorithm for syntactic read-\(k\)-times branching programs
Sampling lower bounds: Boolean average-case and permutations
Improved pseudorandom generators from pseudorandom multi-switching lemmas
scientific article; zbMATH DE number 7650382 (Why is no real title available?)
Algorithms and lower bounds for comparator circuits from shrinkage
Unconditionally secure NIZK in the fine-grained setting
Paradigms for Unconditional Pseudorandom Generators
On small-depth frege proofs for \textsf{PHP}
Local enumeration and majority lower bounds
A technique for hardness amplification against AC^0
Towards stronger depth lower bounds
On bounded depth proofs for Tseitin formulas on the grid; revisited
Agnostic membership query learning with nontrivial savings: new results and techniques
A moderately exponential time algorithm for k-IBDD satisfiability
Comparing computational entropies below majority (or: when is the dense model theorem false?)
\#SAT-algorithms for classes of threshold circuits based on probabilistic rank
Solving sparse instances of Max SAT via width reduction and greedy restriction

This page was built for publication: A satisfiability algorithm for \(\mathrm{AC}^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743451)