Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming

Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang

Three decades of research in communication complexity have led to the invention of a number of techniques to lower bound randomized communication complexity. The majority of these…