Low-Degree Polynomials Are Good Extractors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908327295844352 |
|---|---|
| author | Alrabiah, Omar Goodman, Jesse Mosheiff, Jonathan Ribeiro, João |
| author_facet | Alrabiah, Omar Goodman, Jesse Mosheiff, Jonathan Ribeiro, João |
| contents | We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following.
1. Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial and variety sources via a single unified approach.
2. Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). Formally, for any even $d$, we show that a random degree $d$ polynomial is an $\varepsilon$-error extractor for $n$-bit sumset sources with min-entropy $k=O(d(n/\varepsilon^2)^{2/d})$. This is nearly tight in the polynomial error regime.
Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof may be of independent interest. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between extractors. Using the new structural result, we obtain new limits on the power of sumset extractors, strengthening and generalizing the impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10297 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-Degree Polynomials Are Good Extractors Alrabiah, Omar Goodman, Jesse Mosheiff, Jonathan Ribeiro, João Computational Complexity Combinatorics We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following. 1. Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial and variety sources via a single unified approach. 2. Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). Formally, for any even $d$, we show that a random degree $d$ polynomial is an $\varepsilon$-error extractor for $n$-bit sumset sources with min-entropy $k=O(d(n/\varepsilon^2)^{2/d})$. This is nearly tight in the polynomial error regime. Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof may be of independent interest. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between extractors. Using the new structural result, we obtain new limits on the power of sumset extractors, strengthening and generalizing the impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024). |
| title | Low-Degree Polynomials Are Good Extractors |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2405.10297 |