Exponential correlation bounds limit polynomial approximations of xor majority functions
Exponential Correlation Bounds for Polynomials
Computational Complexity
Summary
The paper shows that combining multiple majority votes on groups of bits using XOR produces a function that low-degree polynomials cannot closely mimic. The authors prove a strong upper bound on how similar these polynomials can be to such combined majority functions. This means the combined majority functions are very different from simple polynomial functions, making them useful to create sequences that look random to certain kinds of computations. The results help design tools that generate pseudorandom numbers with short starting information for use in complex circuit models and polynomial computations.
What this means in practice
- •For cryptography engineers: Create pseudorandom generators with short seeds that resist attacks modeled by low-degree polynomials over binary fields.
- •For hardware circuit designers: Design alternating logic circuits with parity gates that avoid certain polynomial approximations, improving fault detection and complexity management.
A theory result. No direct application yet.
Authors
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola
Abstract
We prove that the XOR of $k$ 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 $\mathbb F_2$ and for alternating circuits with parity gates.