All reports by Author Siddharth Iyer:

__
TR24-111
| 1st July 2024
__

Siddharth Iyer, Anup Rao#### An XOR Lemma for Deterministic Communication Complexity

__
TR23-194
| 5th December 2023
__

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

Revisions: 2

__
TR22-109
| 27th July 2022
__

Siddharth Iyer, Michael Whitmeyer#### Searching for Regularity in Bounded Functions

Siddharth Iyer, Anup Rao

We prove a lower bound on the communication complexity of computing the $n$-fold xor of an arbitrary function $f$, in terms of the communication complexity and rank of $f$. We prove that $D(f^{\oplus n}) \geq n \cdot \Big(\frac{\Omega(D(f))}{\log rk(f)} -\log rk(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the ... 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 >>>

Siddharth Iyer, Michael Whitmeyer

Given a function $f:\mathbb F_2^n \to [-1,1]$, this work seeks to find a large affine subspace $\mathcal U$ such that $f$, when restricted to $\mathcal U$, has small nontrivial Fourier coefficients.

We show that for any function $f:\mathbb F_2^n \to [-1,1]$ with Fourier degree $d$, there exists an affine subspace ... more >>>