The Library
Hardness magnification near state-of-the-art lower bounds
Tools
Tools
Tools
Oliveira, Igor C., Pich, Jan and Santhanam, Rahul (2019) Hardness magnification near state-of-the-art lower bounds. In: 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019. Published in: Proceedings of the 33rd Computational Complexity Conference, 137 27:1-27:29. ISBN 9783959771160. ISSN 1868-8969. doi:10.4230/LIPIcs.CCC.2019.27
|
PDF
WRAP-hardness-magnification-near-state-of-the-art-lower-bounds-Oliveira-2019.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 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.
| 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 Dagstuhl--Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959771160 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 2019 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 137 | |||||||||
| Page Range: | 27:1-27: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: | 18-20 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
