The space complexity of recognizing well-parenthesized expressions
Rahul Jain, Ashwin Nayak · arXiv (Cornell University) · 2010
We show an ( p n=T 3 ) lower bound for the space required by any unidirectional constanterror randomized T -pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak (2009) and rigorously establishes the peculiar power of bi-directional streams over unidirectional ones observed in the algorithms they present.