activity
20102021
most citedInformation Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming

3 citations · 4 across the 2 of their papers we have counts for

collaborators
Showing 2010Show all

1 paper · 1 filter

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-…