Noisy Boolean Hidden Matching with Applications
summary
Defines p-noisy Boolean hidden matching where each matching edge flips independently with probability p and proves the plaintext protocol is optimal, giving communication complexity Θ(√n / p) (and Θ(n^{1-1/T}/p) for hypermatching). Uses an information-theoretic reduction that decomposes the noisy instance into ~1/p ordinary BHM instances, and a four-vertex gadget plus short cycles construction that makes incorrect labels produce odd cycles. Yields streaming lower bounds like Ω(√n / ε) space for 1±ε MaxCut/MaxMatching/Max-acyclic approximations.
AI-written summary · about