Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates
summary
Deterministic algorithm counts satisfying assignments for AC0 circuits that have a subpolynomial number t(n) of weighted symmetric gates with maximum gate weight ≤ 2^{0.99n}, giving a superpolynomial (exponential) speedup over brute force by using concentrated shrinkage technique plus dynamic programming; a separate randomized algorithm solves SAT for depth‑2 threshold circuits with up to m = O(n^2) gates in nontrivial 2^n · 2^{-n^{Ω(1)}} time using probabilistic polynomials and circuit simulations; extensions handle degree‑k polynomial systems over GF(2) and ACC0 variants, relying on reductions and fast polynomial evaluation.
AI-written summary · about