Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Gap-Majority Lemmas in Communication Complexity
Pachara Sawettamalya, Huacheng Yu
We prove an information-theoretically optimal \emph{gap-majority lemma} in the two-player randomized communication model. For a base function , its $n…
cs.CC2024
Strong XOR Lemma for Information Complexity
Pachara Sawettamalya, Huacheng Yu
For any -valued function , its \emph{-folded XOR} is the function where . Given a…