Home Research Teaching Contact
Research on Analyzing Space Complexity Using Switching Networks

Overview:
A switching network is an undirected graph where each edge is switched on or off based on one bit of the input. A switching network accepts if the start node is connected to the accept node and rejects otherwise.

Switching networks are an interesting model of computation to study because they are closely connected to space complexity. If we could prove size lower bounds on general switching networks, this would give us space lower bounds which would be a major breakthrough. In my research on switching networks, I developed techniques for proving size lower bounds on monotone switching networks.

Switching Network Illustration:
Switching Network Example
This figure shows a switching network G' solving the directed connectivity problem on input graphs G with vertices V(G) = {s,a,b,t}. In this switching network, each edge is switched on if and only if its label is contained in the input graph G. For example, for the given input graph G, the green edges in the switching network G' are switched on as their labels are edges in G while the red edges are switched off. Here there is a path in G' from the start node s' to the accept node t', so G' correctly accepts the given input graph G. More generally, there is a path from s' to t' in the switching network G' if and only if there is a path from s to t in the input graph G.

Determining the minimum size of a switching network solving directed connectivity on n vertices is a fundamental open problem. Resolving this open problem would resolve the notorious L (Logarithmic space) versus NL (Non-deterministic logarithmic space) problem.


Papers: