A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**X**

__
TR18-085
| 26th April 2018
__

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan#### XOR Codes and Sparse Random Linear Equations with Noise

__
TR23-194
| 5th December 2023
__

Siddharth Iyer, Anup Rao#### XOR Lemmas for Communication via Marginal Information

Revisions: 2

__
TR19-145
| 31st October 2019
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman#### XOR Lemmas for Resilient Functions Against Polynomials

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

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 >>>

Siddharth Iyer, Anup Rao

We define the marginal information of a communication protocol, and use it to prove XOR lemmas for communication complexity. We show that if every $C$-bit protocol has bounded advantage for computing a Boolean function $f$, then every $\tilde \Omega(C \sqrt{n})$-bit protocol has advantage $\exp(-\Omega(n))$ for computing the $n$-fold xor $f^{\oplus ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman

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 >>>