2009/11/17 by Frédéric Magniez, F. Magniez, Claire Mathieu +6 · 2 citations
Computer Science · Mathematics · #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational complexity theory #Computer science #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Matching (statistics) #Mathematical analysis #Mathematics #Reduction (mathematics) #Space (punctuation) #Statistics #Streaming algorithm #Streaming data #Upper and lower bounds #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0911.3291
published in arXiv (Cornell University) 16, 119 (Cornell University) · 20 pages, 5 figures
arxiv created 2009/11/17 · openalex publication_date 2009/11/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with s different types of parenthesis. We present a one-pass randomized streaming algorithm for Dyck(2) with space \Order(√(n)log n), time per letter \polylog (n), and one-sided error. We prove that this one-pass algorithm is optimal, up to a \polylog n factor, even when two-sided error is allowed. For the lower bound, we prove a direct sum result on hard instances by following the "information cost" approach, but with a few twists. Indeed, we play a subtle game between public and private coins. This mixture between public and private coins results from a balancing act between the direct sum result and a combinatorial lower bound for the base case. Surprisingly, the space requirement shrinks drastically if we have access to the input stream in reverse. We present a two-pass randomized streaming algorithm for Dyck(2) with space \Order((log n)2), time \polylog (n) and one-sided error, where the second pass is in the reverse direction. Both algorithms can be extended to Dyck(s) since this problem is reducible to Dyck(2) for a suitable notion of reduction in the streaming model.