Local reduction
From MaRDI portal
Publication:1641001
DOI10.1016/j.ic.2018.02.009zbMath1394.68184OpenAlexW4233048136MaRDI QIDQ1641001
Emanuele Viola, Hamidreza Jahanjou, Eric Miles
Publication date: 14 June 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2018.02.009
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Derandomizing the HSSW algorithm for 3-SAT
- A Turing machine time hierarchy
- 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 hierarchy for nondeterministic time complexity
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- 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
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- On the Power of Small-Depth Computation
- 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
- Separating Nondeterministic Time Complexity Classes
- Relations Among Complexity Measures
- Size--Depth Tradeoffs for Threshold Circuits
- 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
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- Two-Tape Simulation of Multitape Turing Machines
- On the complexity of \(k\)-SAT
- Reducing the complexity of reductions
