Abstract | ||
---|---|---|
We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string x′ ∈ 1-turn-Dyck2 such that x is obtained by flipping at most k locations of x′ using: - O(k log n) space, O(k log n) randomness, and poly(k log n) time per item and with error at most 1/nΩ(1). - O(k1+ε + log n) space for every 0 ≤ ε ≤ 1, O(log n) randomness, O((logO(1) n + kO(1))) time per item, with error at most 1/8. Here, we also prove that any randomized one-pass algorithm that makes error at most k/n requires at least Ω(k log(n/k)) space to accept strings which are exactly k-away from strings in 1-turn-Dyck2 and to reject strings which are exactly k + 2-away from strings in 1-turn-Dyck2. Since 1-turn-Dyck2 and the Hamming Distance problem are closely related we also obtain new upper and lower bounds for this problem. Dyck2 with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string x′ ∈ Dyck2 such that x is obtained from x′ by changing (in some restricted manner) at most k positions using: - O(k log n + √n log n) space, O(k log n) randomness, poly(k log n) time per element and with error at most 1/nΩ(1). - O(k1+ε + √n log n) space for every 0 O(log n) randomness, O((logO(1) n + kO(1))) time per element, with error at most 1/8. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-22993-0_38 | MFCS'11 Proceedings of the 36th international conference on Mathematical foundations of computer science |
Keywords | DocType | Volume |
k position,k location,well-parenthesized expression,input string,n log n,k log n,k log,randomized one-pass algorithm,membership problem,hamming distance problem,log n | Conference | abs/1206.0206 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.38 |
References | Authors | |
18 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andreas Krebs | 1 | 17 | 2.86 |
Nutan Limaye | 2 | 134 | 20.59 |
Srikanth Srinivasan | 3 | 132 | 21.31 |