The Complexity of Satisfiability of Small Depth Circuits
From MaRDI portal
Publication:3656852
DOI10.1007/978-3-642-11269-0_6zbMath1273.68159OpenAlexW1576180980MaRDI QIDQ3656852
Russell Impagliazzo, Ramamohan Paturi, Chris Calabro
Publication date: 14 January 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_6
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Separating OR, SUM, and XOR circuits, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Algorithmic analysis of priority-based bin packing, A note on the complexity of computing the number of reachable vertices in a digraph, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP, What’s Next? Future Directions in Parameterized Complexity, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Computational complexity of distance edge labeling, Known Algorithms for Edge Clique Cover are Probably Optimal, Nonuniform ACC Circuit Lower Bounds, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem, Unnamed Item, Solving cut-problems in quadratic time for graphs with bounded treewidth, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, Unnamed Item, Priority-based bin packing with subset constraints, Solving sparse instances of Max SAT via width reduction and greedy restriction, On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}, New exact algorithms for the 2-constraint satisfaction problem, Counting Solutions to Polynomial Systems via Reductions, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), A multi-parameter analysis of hard problems on deterministic finite automata, On the Exact Complexity of Evaluating Quantified k-CNF, Fine-grained complexity of safety verification, Unnamed Item, Testing the Complexity of a Valued CSP Language, The Orthogonal Vectors Conjecture for Branching Programs and Formulas, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, On the Complexity of Bounded Context Switching., On Super Strong ETH, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs, Mining circuit lower bound proofs for meta-algorithms
Cites Work
- Exponential lower bounds for depth three Boolean circuits
- Which problems have strongly exponential complexity?
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- An improved exponential-time algorithm for k -SAT
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- Theory and Applications of Satisfiability Testing
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
- Unnamed Item
