Relations and equivalences between circuit lower bounds and karp-lipton theorems
From MaRDI portal
Publication:5091782
DOI10.4230/LIPIcs.CCC.2019.30OpenAlexW2964773335MaRDI QIDQ5091782
Dylan M. McKay, Cody D. Murray, Lijie Chen, R. Ryan Williams
Publication date: 27 July 2022
Full work available at URL: https://doi.org/10.4230/lipics.ccc.2019.30
Related Items (2)
Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Cites Work
- Unnamed Item
- Turing machines that take advice
- Some consequences of non-uniform conditions on uniform classes
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Robust simulations and significant separations
- Pseudorandomness and average-case complexity via uniform reductions
- A note on the circuit complexity of PP
- Circuit-size lower bounds and non-reducibility to sparse sets
- PP is as Hard as the Polynomial-Time Hierarchy
- Circuit Lower Bounds for Merlin–Arthur Classes
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- New Collapse Consequences of NP Having Small Circuits
- Algebraic methods for interactive proof systems
- Hardness magnification near state-of-the-art lower bounds
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Computational Complexity
- Pseudo-random generators for all hardnesses
This page was built for publication: Relations and equivalences between circuit lower bounds and karp-lipton theorems
