Local Reductions
From MaRDI portal
Publication:3448833
DOI10.1007/978-3-662-47672-7_61zbMath1394.68183arXiv1311.3171OpenAlexW3037975911MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (10)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Local expanders ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ 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 ⋮ On uniformity and circuit lower bounds ⋮ Unnamed Item ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Unnamed Item
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
This page was built for publication: Local Reductions
