Eric Allender, Klaus Reinhardt

We show that the perfect matching problem is in the

complexity class SPL (in the nonuniform setting).

This provides a better upper bound on the complexity of the

matching problem, as well as providing motivation for studying

the complexity class SPL.

Using similar ...
more >>>

Eric Allender, Shiyu Zhou

We show that the complexity class LogFew is contained

in NL $\cap$ SPL. Previously, this was known only to

hold in the nonuniform setting.

Eric Allender, Samir Datta, Sambuddha Roy

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Joshua Cook, Ron D. Rothblum

The celebrated $\mathbf{IP}=\mathbf{PSPACE}$ Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch's Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols ... more >>>