Computing Algebraic Formulas Using a Constant Number of Registers

DOI10.1137/0221006zbMath0743.68062OpenAlexW2015676876MaRDI QIDQ3990101

Michael Ben-Or, Richard Cleve

Publication date: 28 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221006

zbMATH Keywords

polynomial-length algebraic straight-line programs

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (43)

A note on VNP-completeness and border complexity ⋮ Efficient information-theoretic multi-party computation over non-commutative rings ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Geometric aspects of iterated matrix multiplication ⋮ A note on logspace optimization ⋮ An infinite pebble game and applications ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Uniform derandomization from pathetic lower bounds ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ Dimension of tensor network varieties ⋮ Complexity of regular functions ⋮ Interleaved Group Products ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ On the Power of Algebraic Branching Programs of Width Two ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ Towards optimal simulations of formulas by bounded-width programs ⋮ Better complexity bounds for cost register automata ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols ⋮ Functions computable in polynomial space ⋮ On measures of space over real and complex numbers ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ⋮ Unnamed Item ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ Algebraic Complexity Classes ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ Nondeterministic \(NC^1\) computation ⋮ Secure Protocol Transformations ⋮ Rational subsets of unitriangular groups ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ Unnamed Item ⋮ Better complexity bounds for cost register automata ⋮ Geometric complexity theory: an introduction for geometers ⋮ Limitations of sums of bounded read formulas and ABPs ⋮ On the power of algebraic branching programs of width two

This page was built for publication: Computing Algebraic Formulas Using a Constant Number of Registers