Pith. sign in

REVIEW 2 cited by

An XOR Lemma for Deterministic Communication Complexity

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2407.01802 v1 pith:QHDEETYB submitted 2024-07-01 cs.CC

Siddharth Iyer , Anup Rao This is my paper · ORCID
classification cs.CC
keywords communicationcomplexitydeterministicmathsfoplusproverankarbitrary
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

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 \mathsf{rk}(f)} -\log \mathsf{rk}(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the deterministic communication complexity, and $\mathsf{rk}(f)$ is the rank of $f$. Our methods involve a new way to use information theory to reason about deterministic communication complexity.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Direct Sums for Parity Decision Trees

    cs.CC 2024-12 conditional novelty 7.0 of 10

    Randomized parity decision trees satisfy direct sum theorems for lower bounds from discrepancy or product distributions, via a new skew complexity measure with perfect direct sum.

  2. Strong XOR Lemma for Information Complexity

    cs.CC 2024-11 conditional novelty 7.0 of 10

    A strong XOR lemma for information complexity: computing f^{⊕n} with constant error costs Ω(n) times the information needed to compute f with error 1/n, up to vanishing additive terms.

Pith tools