Computing Algebraic Formulas Using a Constant Number of Registers
Abstract
It is shown that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs that use only three registers. This was previously known for Boolean formulas [D. A. Barrington, J. Comput. System Sci., 38 (1989), pp. 150–164], which are equivalent to algebraic formulas over the ring $GF(2)$. For formulas over arbitrary rings, the result is an improvement over previous methods that require the number of registers to be logarithmic in the size of the formulas in order to obtain polynomial-length straight-line programs. Moreover, the straight-line programs that arise in these constructions have the property that they consist of statements whose actions on the registers are linear and bijective. A consequence of this is that the problem of determining the iterated product of $n3 \times 3$ matrices is complete (under P-projections) for algebraic $NC^1 $. Also, when the ring is $GF(2)$, the programs that arise in the constructions are equivalent to bounded-width permutation branching programs.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
The Parallel Evaluation of General Arithmetic Expressions
Brent, R. P. (1974) · Journal of the ACM · doi:10.1145/321812.321815 · Cited by 822 · see citing works
Completeness Classes in Algebra
Valiant, L. G. (1979) · ACM eBooks · doi:10.1145/3749740.3749750 · Cited by 483 · see citing works
THE COMPUTATIONAL COMPLEXITY OF ALGEBRAIC AND NUMERIC PROBLEMS.
Borodin, A., & Munro, I. (1975) · CERN Document Server (European Organization for Nuclear Research) · Cited by 396 · see citing works
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹
Barrington, D. A. M. (1989) · Journal of computer and system sciences (Print) · doi:10.1016/0022-0000(89)90037-8 · Cited by 167 · see citing works
Generators for Certain Alternating Groups with Applications to Cryptography
Coppersmith, D., & Grossman, E. (1975) · SIAM Journal on Applied Mathematics · doi:10.1137/0129051 · Cited by 73 · see citing works
Bounds for Width Two Branching Programs
Borodin, A., Dolev, D., Fich, F. E., et al. (1986) · SIAM Journal on Computing · doi:10.1137/0215040 · Cited by 31 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · see citing works
Self-citation
- Authors
- Ben-Or, M., & Cleve, R.
- ORCID
- Ben-Or, Michael
- Venue
- SIAM Journal on Computing
- Published
- 1992-02
- Volume
- 21
- Issue
- 1
- Pages
- 54-58
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2015676876
- Cited by
- 139
- References
- 6
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 6 · 2022: 6 · 2021: 8 · 2020: 4 · 2019: 5 · 2018: 6 · 2017: 5 · 2016: 7 · 2015: 7 · 2014: 11 · 2013: 9 · 2012: 5
- FWCI
- 2.77
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Polynomial and algebraic computation
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- algebraic formulas, GF(2), Boolean formulas
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
