Hardness magnification for natural problems
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 10438
- Type
- E - Conference contribution
- DOI
-
10.1109/FOCS.2018.00016
- Title of conference / published proceedings
- 59th Annual IEEE Symposium on Foundations of Computer Science
- First page
- 139
- Volume
- 25
- Issue
- -
- ISSN
- 1523-8288
- Open access status
- Compliant
- Month of publication
- December
- 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)
-
-
- Citation count
- 7
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper proposes a new approach to complexity lower bounds that seems to avoid the 'natural proofs' barrier of Razborov and Rudich. The phenomenon described in this paper has been further explored by Chen and Tell in their recent paper "Bootstrapping Results for Threshold Circuits 'Just Beyond' Known Lower Bounds", which won the Best Student Paper award at STOC 2019. The paper has influenced further work by Chen, Jin and Williams (ECCC 2019: https://eccc.weizmann.ac.il/report/2019/118), and Cheraghchi et al. at ICALP 2019 (https://doi.org/10.4230/LIPIcs.ICALP.2019.39).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
