Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ALEXANDER RUSSELL:
All reports by Author Alexander Russell:

TR14-073 | 14th May 2014
Shachar Lovett, Cris Moore, Alexander Russell

Group representations that resist random sampling

Revisions: 1

We show that there exists a family of groups $G_n$ and nontrivial irreducible representations $\rho_n$ such that, for any constant $t$, the average of $\rho_n$ over $t$ uniformly random elements $g_1, \ldots, g_t \in G_n$ has operator norm $1$ with probability approaching 1 as $n \rightarrow \infty$. More quantitatively, we ... more >>>




ISSN 1433-8092 | Imprint