We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), ... more >>>

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

We introduce a "derandomized" analogue of graph squaring. This
operation increases the connectivity of the graph (as measured by the
second eigenvalue) almost as well as squaring the graph does, yet only
increases the degree of the graph by a constant factor, instead of
squaring the degree.

One application of ... more >>>

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>>

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

A celebrated theorem of Savitch states that NSPACE(S) is contained DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitch’s theorem itself has not been improved in the last four decades, studying the space complexity of ... more >>>

The {\em hybrid argument}
allows one to relate
the {\em distinguishability} of a distribution (from
uniform) to the {\em
predictability} of individual bits given a prefix. The
argument incurs a loss of a factor $k$ equal to the
bit-length of the
distributions: $\epsilon$-distinguishability implies only
$\epsilon/k$-predictability. ... more >>>

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>>

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.
(1) A polynomial-time,
$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ... more >>>

An $m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of $m$ distinct branching programs for $f$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>>

In the world of space-bounded complexity, there is a strain of results showing that space can, somewhat paradoxically, be used for multiple purposes at once. Touchstone results include Barrington’s Theorem and the recent line of work on catalytic computing. We refer to such techniques, in contrast to the usual notion ... more >>>