Optimal XOR Lemmas for Information ComplexityResearch Paper
Information complexity measures how much two parties must reveal to each other about their inputs in order to compute a function together. It lower-bounds randomized communication complexity, equals the amortized communication cost of many independent copies (Braverman–Rao 2014; Braverman 2015), and underlies lower bounds for set disjointness, data streams…