Omer Reingold, Luca Trevisan, Salil Vadhan

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 >>>

Eyal Rozenman, Salil Vadhan

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 >>>

Oded Goldreich

We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs.

Such a local-characterization is defined in terms of a finite set of (marked) graphs yielding a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

We survey the work ... more >>>

Oded Goldreich

We consider the query complexity of testing local graph properties in the bounded-degree graph model.

A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.

Indeed, this formulation yields a generalized ...
more >>>