Group representations that resist random sampling |
| |
| Authors: | Shachar Lovett Cristopher Moore Alexander Russell |
| |
| Affiliation: | 1. Department of Computer Science and Engineering, University of California, San Diego, CaliforniaSupported by NSF CAREER 1350481;2. Santa Fe InstituteSupported by NSF grant CCF‐1247081 |
| |
| Abstract: | We show that there exists a family of groups Gn and nontrivial irreducible representations ρn such that, for any constant t, the average of ρn over t uniformly random elements  has operator norm 1 with probability approaching 1 as  . More quantitatively, we show that there exist families of finite groups for which  random elements are required to bound the norm of a typical representation below 1. This settles a conjecture of A. Wigderson. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 605–614, 2015 |
| |
| Keywords: | expander graphs group representations random sampling |
|
|
