A \#SAT algorithm for small constant-depth circuits with PTF gates

DOI10.4230/LIPICS.ITCS.2019.8MaRDI QIDQ5090378zbMATH OpenFDO

Authors Swapnam Bajpai, V. Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1809.05932

zbMATH Keywords

SATpolynomial threshold functionslinear decision treesconstant-depth Boolean circuitszero-error randomized algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Satisfiability and derandomization for small polynomial threshold circuits
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• The complexity of satisfiability of small depth circuits
• Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds

Cites work

• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• A polynomial restriction lemma with applications
• An improved exponential-time algorithm for k -SAT
• Analysis of Boolean Functions
• Automata, Languages and Programming
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Faster all-pairs shortest paths via circuit complexity
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP
• Improving exhaustive search implies superpolynomial lower bounds
• Log Depth Circuits for Division and Related Problems
• On Improved Degree Lower Bounds for Polynomial Approximation.
• Satisfiability and derandomization for small polynomial threshold circuits
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Size--Depth Tradeoffs for Threshold Circuits
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• The Chow parameters problem
• Tighter connections between Formula-SAT and shaving logs
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(3)

• A PSPACE construction of a hitting set for the closure of small algebraic circuits
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates

This page was built for publication: A \#SAT algorithm for small constant-depth circuits with PTF gates

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