Hardness magnification near state-of-the-art lower bounds

Conference item

This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful. We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity <= s_1(N) from instances of complexity >= s_2(N), and N = 2^n denotes the input length. In MCSP, complexity is measured by circuit size, while in MKtP one considers Levin's notion of time-bounded Kolmogorov complexity. (In our results, the parameters s_1(N) and s_2(N) are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for Gap-MKtP[s_1,s_2] and Gap-MCSP[s_1,s_2], a marginal improvement over the state-of-the-art in unconditional lower bounds in a variety of computational models would imply explicit super-polynomial lower bounds

Authors: Oliveira, I; Pich, J; Santhanam, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: 34th Computational Complexity Conference (CCC 2019)
• Journal: Computational Complexity Conference
• Series: Leibniz International Proceedings in Informatics
• Publication date: 2019-07-16
• Acceptance date: 2019-05-01
• DOI: 10.4230/LIPIcs.CCC.2019.27
• ISSN: 1868-8969
• Keywords: Kolmogorov complexity; circuit complexity; minimum circuit size problem