Boosting uniformity in quasirandom groups: fast and simple
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910599116488704 |
|---|---|
| author | Derksen, Harm Lee, Chin Ho Viola, Emanuele |
| author_facet | Derksen, Harm Lee, Chin Ho Viola, Emanuele |
| contents | We study the communication complexity of multiplying $k\times t$ elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area.
Relatedly, we show that the convolution of $k^{c}$ independent copies of a 3-uniform distribution over $H^{m}$ is close to a $k$-uniform distribution. This is again an exponential improvement over previous work which needed $c^{k}$ copies. The proofs are remarkably simple; the results extend to other quasirandom groups.
We also show that for any group $H$, any distribution over $H^{m}$ whose weight-$k$ Fourier coefficients are small is close to a $k$-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06932 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Boosting uniformity in quasirandom groups: fast and simple Derksen, Harm Lee, Chin Ho Viola, Emanuele Computational Complexity Combinatorics We study the communication complexity of multiplying $k\times t$ elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area. Relatedly, we show that the convolution of $k^{c}$ independent copies of a 3-uniform distribution over $H^{m}$ is close to a $k$-uniform distribution. This is again an exponential improvement over previous work which needed $c^{k}$ copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group $H$, any distribution over $H^{m}$ whose weight-$k$ Fourier coefficients are small is close to a $k$-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler. |
| title | Boosting uniformity in quasirandom groups: fast and simple |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2409.06932 |