License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2019.27
URN: urn:nbn:de:0030-drops-108494
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10849/
Oliveira, Igor Carboni ;
Pich, Ján ;
Santhanam, Rahul
Hardness Magnification near State-Of-The-Art 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 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.
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) Gap-MCSP[2^{beta n}/c n, 2^{beta n}] !in Circuit[N^{1 + epsilon}], then NP !subseteq Circuit[poly].
(2) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in TC^0[N^{1 + epsilon}], then EXP !subseteq TC^0[poly].
(3) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in B_2-Formula[N^{2 + epsilon}], then EXP !subseteq Formula[poly].
(4) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in U_2-Formula[N^{3 + epsilon}], then EXP !subseteq Formula[poly].
(5) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in BP[N^{2 + epsilon}], then EXP !subseteq BP[poly].
(6) Gap-MKtP[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 Gap-MCSP and Gap-MKtP against different models. For instance, the lower bound assumed in (1) holds for U_2-formulas of near-quadratic 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 Gap-MKtP lies below existing lower bounds: U_2-formulas 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 Gap-MKtP, 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 State-Of-The-Art Lower Bounds}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {27:1--27:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-116-0},
ISSN = {1868-8969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10849},
URN = {urn:nbn:de:0030-drops-108494},
doi = {10.4230/LIPIcs.CCC.2019.27},
annote = {Keywords: Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity}
}
|
Keywords: |
|
Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity |
|
Collection: |
|
34th Computational Complexity Conference (CCC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
16.07.2019 |
