Oded Goldreich, Dana Ron

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

Dean Doron, Amir Sarid, Amnon Ta-Shma

Approximating the eigenvalues of a Hermitian operator can be solved

by a quantum logspace algorithm. We introduce the problem of

approximating the eigenvalues of a given matrix in the context of

classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a

certain range of ...
more >>>