scientific article; zbMATH DE number 7053329
From MaRDI portal
Publication:5743451
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
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Randomized algorithms (68W20)
Related Items (33)
A Moderately Exponential Time Algorithm for k-IBDD Satisfiability ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ The relative exponential time complexity of approximate counting satisfying assignments ⋮ Local reduction ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unconditionally secure NIZK in the fine-grained setting ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ On polynomial approximations to AC ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ Bounded Independence Plus Noise Fools Products ⋮ Fourier concentration from shrinkage ⋮ A moderately exponential time algorithm for \(k\)-IBDD satisfiability ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Criticality of regular formulas ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ CNF satisfiability in a subspace and related problems ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ Mining circuit lower bound proofs for meta-algorithms
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
