Local reduction
type: Item
instance of: scholarly article
title: Local reduction
zbMATH Open document ID: 1394.68184
author: Hamidreza Jahanjou
author: Eric Miles
author: Emanuele Viola
published in: Information and Computation
publication date: 2018-06-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6889858
zbMATH Keywords: computational complexity
zbMATH Keywords: Cook-Levin
zbMATH Keywords: reductions
zbMATH Keywords: ACC0
MaRDI profile type: Publication
full work available at URL: j.ic.2018.02.009
OpenAlex ID: W4233048136
cites work: Two-Tape Simulation of Multitape Turing Machines
cites work: Satisfiability Is Quasilinear Complete in NQL
cites work: Relations Among Complexity Measures
cites work: Short propositional formulas represent nondeterministic computations
cites work: Q3826533
cites work: On O(Tlog T) reduction from RAM computations to satisfiability
cites work: Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
cites work: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
cites work: Reducing the complexity of reductions
cites work: Towards a Study of Low-Complexity Graphs
cites work: Time-space lower bounds for satisfiability
cites work: A Survey of Lower Bounds for Satisfiability and Related Problems
cites work: Improving exhaustive search implies superpolynomial lower bounds
cites work: Natural proofs versus derandomization
cites work: Amplifying lower bounds by means of self-reducibility
cites work: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
cites work: Q5743451
cites work: A Boolean function requiring 3n network size
cites work: Explicit lower bound of 4.5n - o(n) for boolena circuits
cites work: Q4708583
cites work: Q4164821
cites work: On ACC
cites work: On the power of small-depth threshold circuits
cites work: On the complexity of \(k\)-SAT
cites work: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
cites work: An improved exponential-time algorithm for k -SAT
cites work: Threshold circuits of bounded depth
cites work: Majority gates vs. general weighted threshold gates
cites work: On uniform circuit complexity
cites work: New algorithms and lower bounds for circuits with linear threshold gates
cites work: Short PCPs with Projection Queries
cites work: Derandomizing the HSSW algorithm for 3-SAT
cites work: A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function
cites work: Size--Depth Tradeoffs for Threshold Circuits
cites work: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
cites work: Nearly-linear size holographic proofs
cites work: Searching for Primitive Roots in Finite Fields
cites work: A hierarchy for nondeterministic time complexity
cites work: Separating Nondeterministic Time Complexity Classes
cites work: A Turing machine time hierarchy
cites work: On the Power of Small-Depth Computation
DOI: 10.1016/J.IC.2018.02.009
description: scientific article; zbMATH DE number 6889858