Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Deterministic Construction:
TR10-162 | 30th October 2010
Zohar Karnin

Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$

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

TR11-081 | 15th May 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

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

ISSN 1433-8092 | Imprint