Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DATA STREAMS:
Reports tagged with data streams:
TR08-024 | 26th February 2008
Paul Beame, Trinh Huynh

#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

TR09-015 | 19th February 2009
Joshua Brody, Amit Chakrabarti

#### A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

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

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

TR10-100 | 25th June 2010
Amit Chakrabarti

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

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

TR10-140 | 17th September 2010
Amit Chakrabarti, Oded Regev

#### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

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

TR11-062 | 18th April 2011
Amit Chakrabarti, Graham Cormode, Andrew McGregor

#### Robust Lower Bounds for Communication and Stream Computation

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

TR11-105 | 22nd July 2011
Graham Cormode, Michael Mitzenmacher, Justin Thaler

Revisions: 1

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a ... more >>>

TR12-022 | 14th March 2012
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

#### Annotations in Data Streams

Revisions: 1

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

TR12-183 | 25th December 2012
András Salamon

#### Streaming bounds from difference ramification

In graph streaming a graph with $n$ vertices and $m$ edges is presented as a read-once stream of edges. We obtain an $\Omega(n \log n)$ lower bound on the space required to decide graph connectivity. This improves the known bounds of $\Omega(n)$ for undirected and $\Omega(m)$ for sparse directed graphs. ... more >>>

TR13-020 | 2nd February 2013
Tom Gur, Ran Raz

#### Arthur-Merlin Streaming Complexity

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

... more >>>

TR16-111 | 20th July 2016
Amit Chakrabarti, Sagar Kale

#### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

We develop a paradigm for studying multi-player deterministic communication,
based on a novel combinatorial concept that we call a {\em strong fooling
communication required for solving multi-player $\textsc{equality}$