Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Group representations that resist random sampling

RSS-Feed




Revision #1
Authors: Shachar Lovett, Cris Moore, Alexander Russell
Accepted on: 23rd May 2014 17:06
Downloads: 346
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: 972
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