Exponential Correlation Bounds for Polynomials
En palabras de los autores
We prove that the XOR of majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\). By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over and for alternating circuits with parity gates.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 12 pages