The complexity of satisfiability of small depth circuits
From MaRDI portal
Recommendations
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- An improved exponential-time algorithm for k -SAT
- Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- On the complexity of circuit satisfiability
Cites work
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1452705 (Why is no real title available?)
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- An improved exponential-time algorithm for k -SAT
- Exponential lower bounds for depth three Boolean circuits
- On the complexity of \(k\)-SAT
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- Theory and Applications of Satisfiability Testing
- Which problems have strongly exponential complexity?
Cited in
(63)- Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Mining circuit lower bound proofs for meta-algorithms
- Algorithmic analysis of priority-based bin packing
- Fine-grained complexity of safety verification
- Induced tree covering and the generalized Yutsis property
- Faster algorithm for unique (k,2)-CSP
- Separating OR, SUM, and XOR circuits
- New Collapse Consequences of NP Having Small Circuits
- Tighter connections between Formula-SAT and shaving logs
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- What's next? Future directions in parameterized complexity
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Elastic-degenerate string comparison
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- New exact algorithms for the 2-constraint satisfaction problem
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Elastic-Degenerate String Matching via Fast Matrix Multiplication
- Testing the Complexity of a Valued CSP Language
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Priority-based bin packing with subset constraints
- Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
- Algorithms and complexity of difference logic
- Approximation algorithms for min-distance problems in DAGs
- Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
- Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
- On super strong ETH
- Nonuniform ACC circuit lower bounds
- A note on the complexity of computing the number of reachable vertices in a digraph
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Maximum minimal vertex cover parameterized by vertex cover
- Towards hardness of approximation for polynomial time problems
- New perspectives on semiring applications to dynamic programming
- Low-complexity cryptographic hash functions
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- A multi-parameter analysis of hard problems on deterministic finite automata
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Precise upper and lower bounds for the monotone constraint satisfaction problem
- Reconstructing sets of strings from their k-way projections: algorithms \& complexity (extended abstract)
- Certified Core-Guided MaxSAT Solving
- Towards permissionless consensus in the standard model via fine-grained complexity
- Complexity of modular circuits
- On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Hairpin completion distance lower bound
- On the exact complexity of evaluating quantified \(k\)-CNF
- Parameterized inapproximability hypothesis under ETH
- Detecting communities is hard (and counting them is even harder)
- Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search
- Exponential-time approximation schemes via compression
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Counting solutions to polynomial systems via reductions
- On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
- On the Complexity of Bounded Context Switching.
- On the complexity of unique circuit SAT
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Pattern masking for dictionary matching: theory and practice
This page was built for publication: The complexity of satisfiability of small depth circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3656852)
