The Library
Hardness magnification near stateoftheart lower bounds
Tools
Oliveira, Igor C., Pich, Jan and Santhanam, Rahul (2019) Hardness magnification near stateoftheart lower bounds. In: 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 1820 Jul 2019. Published in: Proceedings of the 33rd Computational Complexity Conference, 137 27:127:29. ISBN 9783959771160. ISSN 18688969. doi:10.4230/LIPIcs.CCC.2019.27

PDF
WRAPhardnessmagnificationnearstateoftheartlowerboundsOliveira2019.pdf  Published Version  Requires a PDF viewer. Available under License Creative Commons Attribution. Download (784Kb)  Preview 
Official URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2019.27
Abstract
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 metacomputational problems MKtP and MCSP, where one needs to distinguish instances (strings or truthtables) 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 timebounded 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 GapMKtP[s_1,s_2] and GapMCSP[s_1,s_2], a marginal improvement over the stateoftheart in unconditional lower bounds in a variety of computational models would imply explicit superpolynomial lower bounds. Theorem. There exists a universal constant c >= 1 for which the following hold. If there exists epsilon > 0 such that for every small enough beta > 0 (1) GapMCSP[2^{beta n}/c n, 2^{beta n}] !in Circuit[N^{1 + epsilon}], then NP !subseteq Circuit[poly]. (2) GapMKtP[2^{beta n}, 2^{beta n} + cn] !in TC^0[N^{1 + epsilon}], then EXP !subseteq TC^0[poly]. (3) GapMKtP[2^{beta n}, 2^{beta n} + cn] !in B_2Formula[N^{2 + epsilon}], then EXP !subseteq Formula[poly]. (4) GapMKtP[2^{beta n}, 2^{beta n} + cn] !in U_2Formula[N^{3 + epsilon}], then EXP !subseteq Formula[poly]. (5) GapMKtP[2^{beta n}, 2^{beta n} + cn] !in BP[N^{2 + epsilon}], then EXP !subseteq BP[poly]. (6) GapMKtP[2^{beta n}, 2^{beta n} + cn] !in (AC^0[6])[N^{1 + epsilon}], then EXP !subseteq AC^0[6]. These results are complemented by lower bounds for GapMCSP and GapMKtP against different models. For instance, the lower bound assumed in (1) holds for U_2formulas of nearquadratic size, and lower bounds similar to (3)(5) hold for various regimes of parameters. We also identify a natural computational model under which the hardness magnification threshold for GapMKtP lies below existing lower bounds: U_2formulas that can compute parity functions at the leaves (instead of just literals). As a consequence, if one managed to adapt the existing lower bound techniques against such formulas to work with GapMKtP, then EXP !subseteq NC^1 would follow via hardness magnification.
Item Type:  Conference Item (Paper)  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Computational complexity, Kolmogorov complexity  
Series Name:  Leibniz International Proceedings in Informatics (LIPIcs)  
Journal or Publication Title:  Proceedings of the 33rd Computational Complexity Conference  
Publisher:  Schloss DagstuhlLeibnizZentrum fuer Informatik  
ISBN:  9783959771160  
ISSN:  18688969  
Official Date:  2019  
Dates: 


Date of first compliant deposit:  11 November 2019  
Volume:  137  
Page Range:  27:127:29  
DOI:  10.4230/LIPIcs.CCC.2019.27  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Open Access  
RIOXX Funder/Project Grant: 


Conference Paper Type:  Paper  
Title of Event:  34th Computational Complexity Conference (CCC 2019)  
Type of Event:  Conference  
Location of Event:  New Brunswick, NJ, USA  
Date(s) of Event:  1820 Jul 2019  
Related URLs: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year