Hardness of sparse sets and minimal circuit size problem

DOI10.1007/978-3-030-58150-3_39OpenAlexW3082776702MaRDI QIDQ2019493

Bin Fu

Publication date: 21 April 2021

Full work available at URL: https://arxiv.org/abs/2003.00669

zbMATH Keywords

reductionssparse setsmagnificationMCSP

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (2)

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

This page was built for publication: Hardness of sparse sets and minimal circuit size problem