@article{doi:10.1137/0221006,
    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.},
    Author = {Ben-Or, Michael and Cleve, Richard},
    EPrint = {https://doi.org/10.1137/0221006},
    File = {Computing Algebraic Formulas Using a Constant Number of Registers - ben-or1992.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {1},
    Pages = {54-58},
    Title = {Computing Algebraic Formulas Using a Constant Number of Registers},
    URL = {https://doi.org/10.1137/0221006},
    Volume = {21},
    Year = {1992},
    bdsk-url-1 = {https://doi.org/10.1137/0221006},
    date-added = {2023-10-03 10:53:01 +0200},
    date-modified = {2023-10-03 10:53:01 +0200},
    doi = {10.1137/0221006}
}

@article{doi:10.1137/0221006, 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.}, Author = {Ben-Or, Michael and Cleve, Richard}, EPrint = {https://doi.org/10.1137/0221006}, File = {Computing Algebraic Formulas Using a Constant Number of Registers - ben-or1992.pdf}, Journal = {SIAM Journal on Computing}, Number = {1}, Pages = {54-58}, Title = {Computing Algebraic Formulas Using a Constant Number of Registers}, URL = {https://doi.org/10.1137/0221006}, Volume = {21}, Year = {1992}, bdsk-url-1 = {https://doi.org/10.1137/0221006}, date-added = {2023-10-03 10:53:01 +0200}, date-modified = {2023-10-03 10:53:01 +0200}, doi = {10.1137/0221006} }