An XOR Lemma for Deterministic Communication Complexity

Siddharth Iyer; Anup Rao

doi:10.1109/FOCS61266.2024.00034

2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)

An XOR Lemma for Deterministic Communication Complexity

Year: 2024, Pages: 429-432

DOI Bookmark: 10.1109/FOCS61266.2024.00034

Authors

Siddharth Iyer, University of Washington,School of Computer Science,Seattle,USA
Anup Rao, University of Washington,School of Computer Science,Seattle,USA

Abstract

We prove a lower bound on the communication complexity of computing the

n

$n$ -fold xor of an arbitrary function

f

$f$ , in terms of the communication complexity and rank of

f

$f$ . We prove that

D (f^{\oplus n}) \geq n \cdot (\frac{Ω (D (f))}{\log r k (t)} - \log rk (f))

$D(f^{\oplus n}) \geq n\cdot(\frac{\Omega(D(f))}{\log \mathrm{r}\mathrm{k}(t)}-\log \text{rk}(f))$ , where here

D (f), D (f^{\oplus n})

$D(f), D(f^{\oplus n})$ represent the deterministic communication complexity, and

rk (f)

$\text{rk}(f)$ is the rank of

f

$f$ . Our methods involve a new way to use information theory to reason about deterministic communication complexity.

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!

Non-deterministic communication complexity with few witnesses
1992 Seventh Annual Structure in Complexity Theory Conference
Optimality of the Johnson-Lindenstrauss Lemma
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
Lower bounds for quantum communication complexity
Third IEEE International Conference on Cluster Computing (CLUSTER'01)
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract)
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
The Communication Complexity of Approximating Matrix Rank
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
A Dense Model Theorem for the Boolean Slice
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)

An XOR Lemma for Deterministic Communication Complexity

Authors

Abstract

Related Articles