All reports by Author Amit Chakrabarti:

__
TR16-111
| 20th July 2016
__

Amit Chakrabarti, Sagar Kale#### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

__
TR15-113
| 9th July 2015
__

Amit Chakrabarti, Tony Wirth#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

__
TR14-086
| 11th July 2014
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### Verifiable Stream Computation and Arthurâ€“Merlin Communication

__
TR13-180
| 17th December 2013
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### On Interactivity in Arthur-Merlin Communication and Stream Computation

Revisions: 1

__
TR12-153
| 9th November 2012
__

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally#### Certifying Equality With Limited Interaction

Revisions: 1

__
TR12-022
| 14th March 2012
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler#### Annotations in Data Streams

Revisions: 1

__
TR11-062
| 18th April 2011
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor#### Robust Lower Bounds for Communication and Stream Computation

__
TR10-140
| 17th September 2010
__

Amit Chakrabarti, Oded Regev#### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

__
TR10-100
| 25th June 2010
__

Amit Chakrabarti#### A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem

__
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

__
TR09-015
| 19th February 2009
__

Joshua Brody, Amit Chakrabarti#### A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

__
TR07-014
| 23rd January 2007
__

Amit Chakrabarti#### Lower Bounds for Multi-Player Pointer Jumping

__
TR03-070
| 19th August 2003
__

Amit Chakrabarti, Oded Regev#### An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

Amit Chakrabarti, Sagar Kale

We develop a paradigm for studying multi-player deterministic communication,

based on a novel combinatorial concept that we call a {\em strong fooling

set}. Our paradigm leads to optimal lower bounds on the per-player

communication required for solving multi-player $\textsc{equality}$

problems in a private-message setting. This in turn gives a ...
more >>>

Amit Chakrabarti, Tony Wirth

Set cover, over a universe of size $n$, may be modelled as a

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n \text{ poly}\{\log n, \log m\})$ space to process this ...
more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>>

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

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

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>>

Amit Chakrabarti, Oded Regev

We prove an optimal $\Omega(n)$ lower bound on the randomized

communication complexity of the much-studied

Gap-Hamming-Distance problem. As a consequence, we

obtain essentially optimal multi-pass space lower bounds in the

data stream model for a number of fundamental problems, including

the estimation of frequency moments.

The Gap-Hamming-Distance problem is a ... more >>>

Amit Chakrabarti

The deterministic space complexity of approximating the length of the longest increasing subsequence of

a stream of $N$ integers is known to be $\widetilde{\Theta}(\sqrt N)$. However, the randomized

complexity is wide open. We show that the technique used in earlier work to establish the $\Omega(\sqrt

N)$ deterministic lower bound fails ...
more >>>

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

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

Joshua Brody, Amit Chakrabarti

The Gap-Hamming-Distance problem arose in the context of proving space

lower bounds for a number of key problems in the data stream model. In

this problem, Alice and Bob have to decide whether the Hamming distance

between their $n$-bit input strings is large (i.e., at least $n/2 +

\sqrt n$) ...
more >>>

Amit Chakrabarti

We consider the $k$-layer pointer jumping problem in the one-way

multi-party number-on-the-forehead communication model. In this problem,

the input is a layered directed graph with each vertex having outdegree

$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em

except} the $i$th. The players must communicate, in the order

$1,2,\ldots,k$, ...
more >>>

Amit Chakrabarti, Oded Regev

We consider the approximate nearest neighbour search problem on the

Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that

uses polynomial storage and word size $d^{O(1)}$ requires a worst case

query time of $\Omega(\log\log d/\log\log\log d)$. The approximation

factor may be as loose as $2^{\log^{1-\eta}d}$ for any ...
more >>>