Hardness magnification near state-of-the-art lower bounds
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...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Conference item |
| Foilsithe / Cruthaithe: |
Schloss Dagstuhl
2019
|
| _version_ | 1826259530764255232 |
|---|---|
| author | Oliveira, I Pich, J Santhanam, R |
| author_facet | Oliveira, I Pich, J Santhanam, R |
| author_sort | Oliveira, I |
| collection | OXFORD |
| description | 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 |
| first_indexed | 2024-03-06T18:51:21Z |
| format | Conference item |
| id | oxford-uuid:105842c2-e7c9-4d77-8005-d0dc60a6842c |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:51:21Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:105842c2-e7c9-4d77-8005-d0dc60a6842c2022-03-26T09:55:57ZHardness magnification near state-of-the-art lower boundsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:105842c2-e7c9-4d77-8005-d0dc60a6842cSymplectic Elements at OxfordSchloss Dagstuhl2019Oliveira, IPich, JSanthanam, RThis 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 |
| spellingShingle | Oliveira, I Pich, J Santhanam, R Hardness magnification near state-of-the-art lower bounds |
| title | Hardness magnification near state-of-the-art lower bounds |
| title_full | Hardness magnification near state-of-the-art lower bounds |
| title_fullStr | Hardness magnification near state-of-the-art lower bounds |
| title_full_unstemmed | Hardness magnification near state-of-the-art lower bounds |
| title_short | Hardness magnification near state-of-the-art lower bounds |
| title_sort | hardness magnification near state of the art lower bounds |
| work_keys_str_mv | AT oliveirai hardnessmagnificationnearstateoftheartlowerbounds AT pichj hardnessmagnificationnearstateoftheartlowerbounds AT santhanamr hardnessmagnificationnearstateoftheartlowerbounds |