[Colloquium] THEORY SEMINAR TODAY: Aaron Potechin

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, January 11, 2011
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Aaron Potechin

From:		MIT

Web page:	http://www-math.mit.edu/people/profile.php?pid=1272

Title: 		Fourier Analysis and Invariants on Switching Networks for Directed
Connectivity	

Abstract:  	L versus NL, the problem of whether non-determinism helps in logarithmic
space bounded computation, is a longstanding open question in computational
complexity. At present, only a few results are known. It is known that the
problem is equivalent to the question of whether there is a log-space
algorithm for the directed connectivity problem, namely given an N vertex
directed graph G and pair of vertices s,t, find out if there is a directed
path from s to t in G. In 1970, Savitch gave an O(log2N)-space
deterministic algorithm for directed connectivity. In 1987 and 1988,
Immerman and Szelepcsenyi independently gave an O(log N)-space
non-deterministic algorithm for directed non-connectivity, thus proving
that NL = co-NL. For the problem of undirected connectivity (i.e. where the
input graph G is undirected), a probabilistic algorithm was shown in 1979
using random walks by Aleliunas, Karp, Lipton, Lovász, and Rackoff, and in
2005, Reingold gave a deterministic O(log N)-space algorithm for the same
problem, showing that undirected connectivity is in L. Trifonov
independently gave an O(log(N)log(log(N))) algorithm for undirected
connectivity.

The switching network model is a model for proving space lower bounds
which has the advantage of reversibility. In the paper, 
“Bounds on Monotone Switching Networks for Directed Connectivity”, we
separate monotone analogues of L and NL by showing that any monotone
switching network solving directed connectivity must have size NΩ(lgN), and
this is tight. Fourier analysis is a key technique in proving this result.
We use invariants to obtain lower bounds on Fourier coefficients, and this
gives a lower bound on the size of the switching network. To the best of
our knowledge, these ideas are novel. In this talk, we explain the
switching network model, demonstrate how to use Fourier analysis on
switching networks, show what these invariants are, and give a method for
finding them.	

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.