Towards optimal simulations of formulas by bounded-width programs

DOI10.1007/BF01200059zbMath0774.68042MaRDI QIDQ685723

Richard Cleve

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

algebraic straight-line programsbalanced algebraic formulasbalanced Boolean formulasbounded-width branching programs

Mathematics Subject Classification ID

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

Related Items (5)

Communication Lower Bounds via Critical Block Sensitivity ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ NIKE from affine determinant programs ⋮ Branching program size is almost linear in formula size ⋮ The rise of Paillier: homomorphic secret sharing and public-key silent OT

Cites Work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Computing Algebraic Formulas Using a Constant Number of Registers
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: Towards optimal simulations of formulas by bounded-width programs