Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2019Published
30 April 2019Accepted
Date of first compliant deposit: 11 November 2019
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:
Project/Grant IDRIOXX Funder NameFunder ID
615075Seventh Framework Programmehttp://dx.doi.org/10.13039/100011102
P 28699Austrian Science Fundhttp://dx.doi.org/10.13039/501100002428
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:
  • Other Repository

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us