Publication:5743451
From MaRDI portal
zbMath1423.68583arXiv1107.3127MaRDI QIDQ5743451
Ramamohan Paturi, Russell Impagliazzo, William Matthews
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1107.3127
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68W20: Randomized algorithms
Related Items
On polynomial approximations to AC, Bounded Independence Plus Noise Fools Products, What Circuit Classes Can Be Learned with Non-Trivial Savings?, Unnamed Item, Unnamed Item, Unnamed Item, Agnostic Learning from Tolerant Natural Proofs, Sampling Lower Bounds: Boolean Average-Case and Permutations, Criticality of regular formulas, Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs, Unnamed Item, Algorithms and lower bounds for comparator circuits from shrinkage, Unconditionally secure NIZK in the fine-grained setting, The relative exponential time complexity of approximate counting satisfying assignments, An improved deterministic \#SAT algorithm for small De Morgan formulas, Correlation bounds and \#SAT algorithms for small linear-size circuits, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, A moderately exponential time algorithm for \(k\)-IBDD satisfiability, Solving sparse instances of Max SAT via width reduction and greedy restriction, Local reduction, Gate elimination: circuit size lower bounds and \#SAT upper bounds, Fourier concentration from shrinkage, Satisfiability algorithm for syntactic read-\(k\)-times branching programs, CNF satisfiability in a subspace and related problems, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Mining circuit lower bound proofs for meta-algorithms, Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT, Circuit lower bounds from learning-theoretic approaches, The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments, Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits, A Moderately Exponential Time Algorithm for k-IBDD Satisfiability, Approximating Boolean Functions with Depth-2 Circuits
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving satisfiability in less than \(2^ n\) steps
- Top-down lower bounds for depth-three circuits
- Improving exhaustive search implies superpolynomial lower bounds
- An improved exponential-time algorithm for k -SAT
- The Complexity of Satisfiability of Small Depth Circuits
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- A full derandomization of schöning's k-SAT algorithm
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
