Pseudodeterministic constructions in subexponential time
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12480
- Type
- E - Conference contribution
- DOI
-
10.1145/3055399.3055500
- Title of conference / published proceedings
- 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC)
- First page
- 665
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- -
- Year of publication
- 2017
- 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
- 3
- 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 gives the first sub-exponential time algorithm to generate canonical prime numbers. This problem has been described as "the most compelling challenge" in the field of pseudodeterministic algorithms (Gat and Goldwasser, 2011), and the results in this work ("a recent breakthrough", according to Josh Alman, MIT 2019) have been discussed in several distinguished talks (e.g., Pitassi, IAS-Princeton, 2020, and Goldwasser (Turing Award), Oxford, 2018). Novel techniques introduced here have been applied in areas ranging from learning (Oliveira and Santhanam, 2018) to interactive proofs (Goldwasser, Grossman, and Holden, 2018).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -