Conference item icon

Conference item

Hardness magnification for natural problems

Abstract:

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include: 1. Let MCSP be the decision problem whose YES instances are truth tables of functions with circuit complexity at most s(n). We show that if MCSP[2^√n] cannot be solved on average with zero error by formul...

Expand abstract
Publication status:
Published
Peer review status:
Reviewed (other)
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1109/FOCS.2018.00016

Authors


More by this author
Institution:
University of Oxford
Division:
Maths, Physical and Life Sciences
Department:
Computer Science
Oxford college:
Magdalen College
More by this author
Institution:
University of Oxford
Division:
Maths, Physical and Life Sciences
Department:
Computer Science
Publisher:
Institute of Electrical and Electronics Engineers Publisher's website
Publication date:
2018-12-03
Acceptance date:
2018-06-30
DOI:
EISSN:
2575-8454
ISSN:
1523-8288
Pubs id:
pubs:908931
URN:
uri:f3140a7a-0eb1-44cb-8fda-4942a593847c
UUID:
uuid:f3140a7a-0eb1-44cb-8fda-4942a593847c
Local pid:
pubs:908931
ISBN:
9781538642306

Terms of use


Metrics



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

TO TOP