A \#SAT algorithm for small constant-depth circuits with PTF gates
type: Item
instance of: scholarly article
title: A \#SAT algorithm for small constant-depth circuits with PTF gates
author: Swapnam Bajpai
author: V. Krishan
author: Deepanshu Kush
author: Nutan Limaye
author: Srikanth Srinivasan
published in: Algorithmica
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/10101/
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7495637
MaRDI profile type: Publication
OpenAlex ID: W2952971107
cites work: Q5002674
cites work: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
cites work: Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
cites work: Log Depth Circuits for Division and Related Problems
cites work: Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
cites work: Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
cites work: Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
cites work: Majority gates vs. general weighted threshold gates
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: Polynomial threshold functions and Boolean threshold circuits
cites work: Size--Depth Tradeoffs for Threshold Circuits
cites work: A polynomial restriction lemma with applications
cites work: Q5009542
cites work: Near-optimal linear decision trees for k-SUM and related problems
cites work: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
cites work: Q5655273
cites work: Number-theoretic constructions of efficient pseudo-random functions
cites work: Analysis of Boolean Functions
cites work: The Chow Parameters Problem
cites work: An improved exponential-time algorithm for k -SAT
cites work: Q4484662
cites work: Natural proofs
cites work: On Improved Degree Lower Bounds for Polynomial Approximation.
cites work: Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
cites work: Automata, Languages and Programming
cites work: Improving exhaustive search implies superpolynomial lower bounds
cites work: Faster all-pairs shortest paths via circuit complexity
cites work: New algorithms and lower bounds for circuits with linear threshold gates
cites work: Nonuniform ACC Circuit Lower Bounds
cites work: Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
DOI: 10.1007/S00453-021-00915-7
description: scientific article; zbMATH DE number 7495637