Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SIDDHARTH IYER:
All reports by Author Siddharth Iyer:

TR24-111 | 1st July 2024
Siddharth Iyer, Anup Rao

An XOR Lemma for Deterministic Communication Complexity

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


TR23-194 | 5th December 2023
Siddharth Iyer, Anup Rao

XOR Lemmas for Communication via Marginal Information

Revisions: 2

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


TR22-109 | 27th July 2022
Siddharth Iyer, Michael Whitmeyer

Searching for Regularity in Bounded Functions

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




ISSN 1433-8092 | Imprint