Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!marina
From: marina@ai.toronto.edu (Marina Haloulos)
Newsgroups: ont.events
Subject: Richard Cleve, Monday 18 December 1989: THEORY SEMINAR
Message-ID: <89Dec13.102345est.2248@neat.cs.toronto.edu>
Date: 13 Dec 89 15:24:25 GMT
Lines: 34


                            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.