Subquadratic simulations of circuits by branching programs

1 January 1989

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 568-573
https://doi.org/10.1109/sfcs.1989.63536

Abstract

Boolean circuits and their simulations by bounded-width branching programs are considered. It is shown that every NC/sup 1/ circuit of size s can be simulated by a constant-width branching program of length s/sup 1.811. . ./. Some related group-theoretic results are presented.

Keywords

This publication has 7 references indexed in Scilit:

Computing Algebraic Formulas Using a Constant Number of Registers
SIAM Journal on Computing, 1992
Non-uniform automata over groups
Lecture Notes in Computer Science, 1987
Two lower bounds for branching programs
Published by Association for Computing Machinery (ACM) ,1986
A taxonomy of problems with fast parallel algorithms
Information and Control, 1985
Lower bounds by probabilistic arguments
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1983
Multi-party protocols
Published by Association for Computing Machinery (ACM) ,1983
On simultaneous resource bounds
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1979

Cited by 9 articles