Local Reductions
From MaRDI portal
Publication:3448833
DOI10.1007/978-3-662-47672-7_61zbMath1394.68183arXiv1311.3171MaRDI QIDQ3448833
Hamid Jahanjou, Eric Miles, Emanuele Viola
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.3171
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Unnamed Item, Unnamed Item, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity, On uniformity and circuit lower bounds, Local expanders, Gate elimination: circuit size lower bounds and \#SAT upper bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of small-depth threshold circuits
- On O(Tlog T) reduction from RAM computations to satisfiability
- A Boolean function requiring 3n network size
- Short propositional formulas represent nondeterministic computations
- On uniform circuit complexity
- Majority gates vs. general weighted threshold gates
- On ACC
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Threshold circuits of bounded depth
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Natural Proofs versus Derandomization
- Nearly-linear size holographic proofs
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function
- An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Time-space lower bounds for satisfiability
- An improved exponential-time algorithm for k -SAT
- Amplifying lower bounds by means of self-reducibility
- A Survey of Lower Bounds for Satisfiability and Related Problems
- Towards a Study of Low-Complexity Graphs
- Searching for Primitive Roots in Finite Fields
- Satisfiability Is Quasilinear Complete in NQL
- Relations Among Complexity Measures
- New algorithms and lower bounds for circuits with linear threshold gates
- Short PCPs with Projection Queries
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- On the concrete efficiency of probabilistically-checkable proofs
- Two-Tape Simulation of Multitape Turing Machines
- On the complexity of \(k\)-SAT
- Reducing the complexity of reductions
