Conference item icon

Conference item

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 lengt...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's Version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.CCC.2019.27

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Magdalen College
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
137
Pages:
Article: 27
Series:
Leibniz International Proceedings in Informatics
Publication date:
2019-07-16
Acceptance date:
2019-05-01
DOI:
ISSN:
1868-8969
Pubs id:
pubs:1022697
URN:
uri:105842c2-e7c9-4d77-8005-d0dc60a6842c
UUID:
uuid:105842c2-e7c9-4d77-8005-d0dc60a6842c
Local pid:
pubs:1022697

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP