marina@ai.toronto.edu (Marina Haloulos) (12/13/89)
FLASH ANNOUNCEMENT
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB119, at 3:00 p.m., Monday 18 December 1989
Richard Cleve
International Computer Science Institute
"Towards Optimal Simulations of Formulae by Bounded-Width Programs"
Barrington showed how to compute any Boolean formula of size s by a
bounded-width branching program of size polynomial in s. In particular, if
the formula is expressible as balanced tree of size s, Barrington's
construction yields a bounded-width branching program of length s^2.
Without the width restriction, one can easily construct a branching program
of length s that computes the formula. Thus it may appear that, in
exchange for the bounded-width restriction, the length of the programs must
increase. Recently, Cai and Lipton showed that this length increase need
not be quadratic, by exhibiting a construction that simulates balanced
formulae of size s by bounded-width branching programs of length
O(s^{1.811}). We shall improve this by showing that, for any fixed e>0,
the length of the bounded-width branching programs can be O(s^{1+e}).
Our results are actually in the more general setting of an arbitrary ring.
It will be shown that, over an arbitrary ring, for any fixed e>0, all
balanced arithmetic formulae of size s are computed by straight-line
programs that employ a constant number of read/write registers and have
length O(s^{1+e}). Also, it is of interest that these straight-line
programs can be translated into P-projections of iterated products of
invertible constant-size matrices.