Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

DOI10.1145/3313276.3316396zbMath1434.68160OpenAlexW2951756435MaRDI QIDQ5212860

Dylan M. McKay, Cody D. Murray, R. Ryan Williams

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/137518

zbMATH Keywords

Kolmogorov complexitystreaming algorithmshardness magnificationminimum circuit-size problem

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Online algorithms; streaming algorithms (68W27) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (12)

MCSP is hard for read-once nondeterministic branching programs ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

This page was built for publication: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes