Amplifying circuit lower bounds against polynomial time, with applications

DOI10.1007/s00037-013-0069-5zbMath1286.68170OpenAlexW2121154086MaRDI 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 boundsquantified Boolean formulascircuit evaluationNCsize-depth trade-offs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

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

This page was built for publication: Amplifying circuit lower bounds against polynomial time, with applications