A $k$-LIN instance is a system of $m$ equations over $n$ variables of the form $s_{i[1]} + \dots + s_{i[k]} =$ 0 or 1 modulo 2 (each involving $k$ variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are ... more >>>

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $F_2$. We introduce a new technique to prove such correlation bounds with $F_2$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>>