Oliveira, Igor Carboni ;
Pich, Ján ;
Santhanam, Rahul
Hardness Magnification near StateOfTheArt Lower Bounds
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.
BibTeX  Entry
@InProceedings{oliveira_et_al:LIPIcs:2019:10849,
author = {Igor Carboni Oliveira and J{\'a}n Pich and Rahul Santhanam},
title = {{Hardness Magnification near StateOfTheArt Lower Bounds}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {27:127:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10849},
URN = {urn:nbn:de:0030drops108494},
doi = {10.4230/LIPIcs.CCC.2019.27},
annote = {Keywords: Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity}
}
16.07.2019
Keywords: 

Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

16.07.2019 