Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RANGANATH KONDAPALLY:
All reports by Author Ranganath Kondapally:

TR12-153 | 9th November 2012
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Certifying Equality With Limited Interaction

Revisions: 1

The \textsc{equality} problem is usually one's first encounter with
communication complexity and is one of the most fundamental problems in the
field. Although its deterministic and randomized communication complexity
were settled decades ago, we find several new things to say about the
problem by focusing on two subtle aspects. The ... more >>>


TR10-076 | 18th April 2010
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

Revisions: 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-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that ... more >>>




ISSN 1433-8092 | Imprint