On Algebraic Branching Programs of Small Width
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12164
- Type
- D - Journal article
- DOI
-
10.1145/3209663
- Title of journal
- Journal of the ACM
- Article number
- 32
- First page
- 1
- Volume
- 65
- Issue
- 5
- ISSN
- 0004-5411
- Open access status
- Technical exception
- Month of publication
- August
- 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
-
2
- Research group(s)
-
-
- Citation count
- 4
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper with the same title was published at CCC 2017. The paper shows the first separation of an algebraic complexity class and its closure. The proof is based on a polynomial whose orbit closure contains the class of polynomials with small algebraic formulas (VF). This directly inspired Shpilka and Medini to formulate a new and adjusted approach to geometric complexity theory (FSTTCS 2020 invited talk, see video at https://youtu.be/B8ajISSp-Q0).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -