3 citations · 4 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2012★ 3 cited
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…
cs.CC2010
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally +1
This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-…