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(log^22N)-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, Lova'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.