Tutte seminar - Ashwin Nayak

The Index function and the space complexity of Dyck languages

Abstract:

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