Hardness magnification for natural problems
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12481
- Type
- E - Conference contribution
- DOI
-
10.1109/FOCS.2018.00016
- Title of conference / published proceedings
- 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
- First page
- 65
- Volume
- -
- Issue
- -
- ISSN
- 2575-8454
- Open access status
- Technical exception
- Month of publication
- -
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 7
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in one of the two top conferences in theoretical CS, this paper offers a new path (hardness magnification) to the longstanding problem of establishing the intractability of computations. Shortly after publication, several works have extended the results. A STOC'20 workshop was dedicated to "MCSP and Hardness Magnification". According to the survey "The New Complexity Landscape around Circuit Minimization'' by Allender (Rutgers), "Some of the most important and exciting developments relating to MCSP and related problems deal with the emerging study of hardness magnification.” A successful Royal Society University Research Fellowship application (£770k) included magnification as a main research direction.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -