Amplifying circuit lower bounds against polynomial time, with applications

DOI10.1007/s00037-013-0069-5zbMath1286.68170MaRDI QIDQ354644

Richard J. Lipton, R. Ryan Williams

Publication date: 19 July 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-013-0069-5

zbMATH Keywords

lower bounds; quantified Boolean formulas; circuit evaluation; NC; size-depth trade-offs

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Hardness magnification near state-of-the-art lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• On quasilinear-time complexity theory
• Interactive proof systems and alternating time-space complexity
• On alternation
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• Time-space tradeoffs for satisfiability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Lower Bounds against Weakly Uniform Circuits
• On TC0 Lower Bounds for the Permanent
• Circuit-size lower bounds and non-reducibility to sparse sets
• Time-space lower bounds for satisfiability
• P-uniform circuit complexity
• Amplifying lower bounds by means of self-reducibility
• A Survey of Lower Bounds for Satisfiability and Related Problems
• On Time Versus Space
• Satisfiability Is Quasilinear Complete in NQL
• On Relating Time and Space to Size and Depth
• Relations Among Complexity Measures
• Two-Tape Simulation of Multitape Turing Machines
• Fundamentals of Computation Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Time-space tradeoffs for SAT on nonuniform machines