Zohar Karnin

For any $00$, we give an efficient

deterministic construction of a linear subspace $V \subseteq

\R^n$, of dimension $(1-\epsilon)n$ in which the $\ell_p$ and

$\ell_r$ norms are the same up to a multiplicative factor of

$\poly(\epsilon^{-1})$ (after the correct normalization). As a

corollary we get a deterministic compressed sensing algorithm

more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>