Hardness of sparse sets and minimal circuit size problem

DOI10.1007/978-3-030-58150-3_39MaRDI QIDQ2019493zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• A low and a high hierarchy within NP
• Hardness magnification near state-of-the-art lower bounds
• Limits of minimum circuit size problem as oracle
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the NP-Completeness of the Minimum Circuit Size Problem.
• On the average-case complexity of MCSP and its variants
• The minimum oracle circuit size problem
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

Cited in

(6)

• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• Sparse Boolean equations and circuit lattices
• scientific article; zbMATH DE number 1332663 (Why is no real title available?)
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• There are no sparse NP\(_{w}\)-hard sets
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019493)