Amplifying lower bounds by means of self-reducibility
From MaRDI portal
Publication:3578198
DOI10.1145/1706591.1706594zbMath1327.68112MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications, Unnamed Item, Unnamed Item, Unnamed Item, Parallel Computation Using Active Self-assembly, On Expressing Majority as a Majority of Majorities, 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, Amplifying circuit lower bounds against polynomial time, with applications, On uniformity and circuit lower bounds, Binary pattern tile set synthesis is NP-hard, Local reduction, Parallel computation using active self-assembly, Lower bounds and hardness magnification for sublinear-time shrinking cellular automata, Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case, Computing majority by constant depth majority circuits with low fan-in gates, Dual VP classes, Computing the best-case energy complexity of satisfying assignments in monotone circuits, Uniform derandomization from pathetic lower bounds, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization, Local Reductions, Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications., Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG], Regular Languages Definable by Majority Quantifiers with Two Variables
