Proof complexity lower bounds from algebraic circuit complexity
- Submitting institution
-
Royal Holloway and Bedford New College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 26753743
- Type
- E - Conference contribution
- DOI
-
10.4230/LIPIcs.CCC.2016.32
- Title of conference / published proceedings
- 31st Conference on Computational Complexity (CCC 2016)
- First page
- 1
- Volume
- 50
- Issue
- -
- ISSN
- 1868-8969
- Open access status
- Out of scope for open access requirements
- Month of publication
- May
- Year of publication
- 2016
- 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
-
3
- Research group(s)
-
-
- Citation count
- 6
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in the flagship conference of computational complexity, this work was the first to utilise purely algebraic circuit complexity methods to demonstrate provable limitations against efficiently refuting unsatisfiable instances. The novel technique reduces a proof to an algebraic computational device that we know how to analyse. Further connection between proof complexity and the ability to turn random algorithms to deterministic algorithms were established. Invited to a special journal issue (meaning top 3-4 paper), our techniques attracted the attention of the community and led to the Flagship ACM SIGLOG Newsletter 3 (3), 2016 survey by Pitassi and Tzameret.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -