Name
Abstract | ||
|---|---|---|
We study the bias of random bounded-degree polynomials over odd prime fields and show that, with probability exponentially close to 1, n-variate polynomials of degree d over F-p have bias at most p(-Omega(n/d)). This also yields an exponential tail bound on the weight distribution of Reed-Muller codes over odd prime fields. These results generalize bounds of Ben-Eliezer, Hod, and Lovett [Comput. Complexity, 21 (2012), pp. 63-81] who proved similar results over F-2. Our bounds are based on an extremal property of the rank of sub-matrices of the generator matrices of Reed-Muller codes over odd prime fields that generalizes a property shown by Keevash and Sudakov [SIAM T. Discrete Math., 18 (2005), pp. 713-727] for the case of F-2. Our tail bounds on the bias can be used to derive exponential lower bounds on the time for space-bounded learning of bounded-degree polynomials from their evaluations over odd prime fields. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/18M1215104 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Reed-Muller codes,finite field,random polynomials | Journal | 34 |
Issue | ISSN | Citations |
2 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Shayan Oveis Gharan | 2 | 323 | 26.63 |
| Xin Yang | 3 | 0 | 0.34 |