期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show an~(nT) lower bound for the space required by
any unidirectional constant-error 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.
The lower bound is obtained by analysing the information that is
necessarily revealed by the players about their respective inputs
in a two-party communication protocol for a variant of the Index
function.
