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

DOI10.1007/s00453-021-00915-7OpenAlexW2952971107MaRDI QIDQ2118395

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

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/10101/

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Majority gates vs. general weighted threshold gates
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Polynomial threshold functions and Boolean threshold circuits
• Improving exhaustive search implies superpolynomial lower bounds
• On Improved Degree Lower Bounds for Polynomial Approximation.
• The Chow Parameters Problem
• Number-theoretic constructions of efficient pseudo-random functions
• Nonuniform ACC Circuit Lower Bounds
• Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
• An improved exponential-time algorithm for k -SAT
• Log Depth Circuits for Division and Related Problems
• Size--Depth Tradeoffs for Threshold Circuits
• Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
• Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
• New algorithms and lower bounds for circuits with linear threshold gates
• A polynomial restriction lemma with applications
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Analysis of Boolean Functions
• Near-optimal linear decision trees for k-SUM and related problems
• Faster all-pairs shortest paths via circuit complexity
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Automata, Languages and Programming
• Natural proofs

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