## Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation

##### Abstract

The subject of computational complexity theory is to analyze the difficulty of solving
computational problems within different models of
computation. Proving lower
bounds is easier in less powerful models and proving upper bounds is easier in the more
powerful models. This dissertation studies techniques for analyzing the power of models
of computation which are at the frontier of
currently existing methods.
First, we study the power of certain
classes of depth-three circuits. The power
of such circuits is largely not understood and studying them under further restrictions
has received a lot of attention. We prove exponential lower bounds on the size of
certain depth-three circuits computing parity. Our approach is based on relating the lower bounds
to correlation between parity and modular polynomials, and expressing the correlation
with exponential sums. We show a new expression for the exponential sum which involves
a certain affine space corresponding to the polynomial. This technique gives a unified
treatment and generalization of bounds which include the results of Goldmann on linear
polynomials and Cai, Green, and Thierauf on symmetric
polynomials. We obtain bounds
on the exponential sums for
lasses of polynomials of large degree and with a large number
of terms, which previous techniques did not apply to.
Second, we study the space
complexity of undirected st-
connectivity. We prove
an O(log n log log n) upper bound on the space
complexity of undirected st-connectivity.
This improves the previous O(log4=3
n) bound due to Armoni et al. and is a big step
towards the
conjectured optimal O(log n) bound. Independently of our work and using
different techniques recently Reingold proved the optimal bound. Interest in this question
comes from the fact that undirected st-connectivity is
complete for SL, a class of
problems between L and NL. It has been noticed that questions in the space
context
tend to be easier to answer than the
corresponding questions in the time
context. Since
understanding the power of non-determinism over determinism presents a major
challenge
to
complexity theory, studying
complexity
lasses between L and NL, which are
the smallest natural
classes
capturing deterministic
and non-deterministic
space-bounded
computation, is important.

##### Department

##### Description

text