PhD Defense: Jing-Tang Keith Jang, GDC 4.516

Contact Name: 
Lydia Griffith
Aug 6, 2013 2:00pm - 4:00pm

PhD Defense: Jing-Tang Keith Jang

Date:  August 6, 2013
Time: 2pm
Location: GDC 4.516
Advisor: Anna Gal

Title: The Size and Depth of Boolean Circuits
We study the relationship between size and depth for Boolean circuits.
Over four decades, very few results were obtained for either special
or general Boolean circuits.  Spira showed in 1971 that any Boolean
formula of size s can be simulated in depth O(log s).  Spira's result
means that an arbitrary Boolean expression can be replaced by an
equivalent "balanced" expression, that can be evaluated very
efficiently in parallel.  For general Boolean circuits, the strongest
known result is that Boolean circuits of size s can be simulated in
depth O(s / log s).

We obtain significant improvements over the general bounds for the
size versus depth problem for special classes of Boolean circuits.  We
show that every layered Boolean circuit of size s can be simulated by
a layered Boolean circuit of depth O(sqrt{s log s}).  For planar
circuits and synchronous circuits of size s, we obtain simulations of
depth O(sqrt{s}).  Improving any of the above results by polylog
factors would immediately improve the bounds for general circuits.

We generalize Spira's theorem and show that any Boolean circuit of
size s with segregators of size f(s) can be simulated in depth O(f(s)
log s).  This improves and generalizes a simulation of polynomial-size
Boolean circuits of constant treewidth k in depth O(k^2 log n)  by
Jansen and Sarma.  Since the existence of small balanced separators in
a directed acyclic graph implies that the graph also has small
segregators, our results also apply to circuits with small separators.
Our results imply that the class of languages computed by non-uniform
families of polynomial size circuits that have constant size
segregators equals non-uniform NC^1.

As an application of our simulation of circuits in small depth, we
show that the Boolean Circuit Value problem for circuits with constant
size segregators (or separators) is in deterministic SPACE (log^2 n).
Our results also imply that the Planar Circuit Value problem, which is
known to be P-Complete, is in SPACE (sqrt{n} log n).  We also show
that the Layered Circuit Value and Synchronous Circuit Value problems,
which are both P-complete, are in SPACE(sqrt{n}).

Our study of circuits with small separators and segregators led us to
obtain space efficient algorithms for computing balanced graph
separators.  We extend this approach to obtain space efficient
approximation algorithms
for the search and optimization versions of the SUBSET SUM problem,
which is one of the most studied NP-complete problems.

Finally we study the relationship between simultaneous time and space
bounds on Turing machines and Boolean circuit depth.  We observe a new
connection between planar circuit size and simultaneous time and space
products on Turing machines.  We use this to obtain a small
improvement over the classical simulations of simultaneous time and
space bounds by circuit depth.  We also prove quadratic lower bounds
on the product of time and space for several explicit functions.