Amplifying lower bounds by means of self-reducibility
From MaRDI portal
Publication:3578198
DOI10.1145/1706591.1706594zbMath1327.68112OpenAlexW1997643965MaRDI QIDQ3578198
Michal Koucký, Eric W. Allender
Publication date: 14 July 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1706591.1706594
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (25)
Local Reductions ⋮ Local reduction ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Amplifying circuit lower bounds against polynomial time, with applications ⋮ Uniform derandomization from pathetic lower bounds ⋮ Dual VP classes ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Unnamed Item ⋮ On uniformity and circuit lower bounds ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Binary pattern tile set synthesis is NP-hard ⋮ Parallel Computation Using Active Self-assembly ⋮ Parallel computation using active self-assembly ⋮ Unnamed Item ⋮ Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG] ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ On Expressing Majority as a Majority of Majorities ⋮ Regular Languages Definable by Majority Quantifiers with Two Variables ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits ⋮ Computing majority by constant depth majority circuits with low fan-in gates ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
This page was built for publication: Amplifying lower bounds by means of self-reducibility
