The Complexity of Satisfiability of Small Depth Circuits
From MaRDI portal
Publication:3656852
DOI10.1007/978-3-642-11269-0_6zbMath1273.68159MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68W20: Randomized algorithms
68Q12: Quantum algorithms and complexity in the theory of computing
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Unnamed Item, Unnamed Item, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), 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, On the Complexity of Bounded Context Switching., Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs, Counting Solutions to Polynomial Systems via Reductions, Unnamed Item, Unnamed Item, Fine-grained complexity of safety verification, On Super Strong ETH, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Solving cut-problems in quadratic time for graphs with bounded treewidth, Separating OR, SUM, and XOR circuits, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Algorithmic analysis of priority-based bin packing, Solving sparse instances of Max SAT via width reduction and greedy restriction, Computational complexity of distance edge labeling, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}, 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, A multi-parameter analysis of hard problems on deterministic finite automata, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Mining circuit lower bound proofs for meta-algorithms, New exact algorithms for the 2-constraint satisfaction problem, A note on the complexity of computing the number of reachable vertices in a digraph, What’s Next? Future Directions in Parameterized Complexity, Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem, On the Exact Complexity of Evaluating Quantified k-CNF, Nonuniform ACC Circuit Lower Bounds, Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP, Known Algorithms for Edge Clique Cover are Probably Optimal
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
