Hardness of sparse sets and minimal circuit size problem
From MaRDI portal
Publication:2019493
DOI10.1007/978-3-030-58150-3_39MaRDI QIDQ2019493
Publication date: 21 April 2021
Full work available at URL: https://arxiv.org/abs/2003.00669
68Rxx: Discrete mathematics in relation to computer science
Related Items
Cryptographic hardness under projections for time-bounded Kolmogorov complexity, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Cites Work
- A low and a high hierarchy within NP
- The minimum oracle circuit size problem
- Hardness magnification near state-of-the-art lower bounds
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item