Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR14-073 | 23rd May 2014 17:06

#### Group representations that resist random sampling

Revision #1
Authors: Shachar Lovett, Cris Moore, Alexander Russell
Accepted on: 23rd May 2014 17:06
Downloads: 644
Keywords:

Abstract:

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 show that there exist families of finite groups for which $\Omega(\log \log |G|)$ random elements are required to bound the norm of a typical representation below $1$. This settles a conjecture of A. Wigderson.

Changes to previous version:

Fixed typos

### Paper:

TR14-073 | 14th May 2014 21:17

#### Group representations that resist random sampling

TR14-073
Authors: Shachar Lovett, Cris Moore, Alexander Russell
Publication: 16th May 2014 23:34
Downloads: 1977
Keywords:

Abstract:

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 show that there exist families of finite groups for which $\Omega(\log \log |G|)$ random elements are required to bound the norm of a typical representation below $1$. This settles a conjecture of A. Wigderson.

ISSN 1433-8092 | Imprint