ECCC-Report TR14-073https://eccc.weizmann.ac.il/report/2014/073Comments and Revisions published for TR14-073en-usFri, 23 May 2014 17:06:11 +0300
Revision 1
| Group representations that resist random sampling |
Shachar Lovett,
Cris Moore,
Alexander Russell
https://eccc.weizmann.ac.il/report/2014/073#revision1We 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.Fri, 23 May 2014 17:06:11 +0300https://eccc.weizmann.ac.il/report/2014/073#revision1
Paper TR14-073
| Group representations that resist random sampling |
Shachar Lovett,
Cris Moore,
Alexander Russell
https://eccc.weizmann.ac.il/report/2014/073We 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.Fri, 16 May 2014 23:34:24 +0300https://eccc.weizmann.ac.il/report/2014/073