|
Streaming algorithms access the input sequentially, one symbol at a time, a small
number of times, while attempting to solve some information processing task. The
goal is to process massive data using as little space and time as
possible. Streaming algorithms that use constant space and time per input symbol
recognize precisely the class of regular languages.
Following Magniez, Mathieu, and Nayak, we study the streaming complexity of Dyck
languages, prototypical languages in the next level of the Chomsky hierarchy. We
show an Omega(sqrt(n)/T) lower bound for the space required by any constant-error
randomized streaming algorithm for Dyck(2) that make T passes over the input, all
in the same direction. This proves a conjecture due to Magniez et al. and
rigorously establishes the peculiar power of bi-directional streams over
unidirectional ones reflected in their algorithms.
The space lower bound is obtained by reducing the problem to one in communication
complexity, involving the so-called Index function. It rests on the information
necessarily revealed by each party about her input in a two-party communication
protocol for a variant of the Index function. We show that either one party
reveals Omega(n) information about her n-bit input, or the other party reveals
Omega(1) information about a (log n)-bit input.
We show similar results in the quantum analogues of the streaming and
communication models.
Joint work with Rahul Jain (CQT and NUS, Singapore).
|