Name
Abstract | ||
|---|---|---|
In this paper, we give streaming algorithms for some problems which are known to be in deterministic log-space, when the number
of passes made on the input is unbounded. If the input data is massive, the conventional deterministic log-space algorithms
may not run efficiently. We study the complexity of the problems when the number of passes is bounded.
The first problem we consider is the membership testing problem for deterministic linear languages, DLIN. Extending the recent work of Magniez et al.[11](to appear in STOC 2010), we study the use of fingerprinting technique for
this problem. We give the following streaming algorithms for the membership testing of DLIN s: a randomized one pass algorithm that uses O(logn) space (one-sided error, inverse polynomial error probability), and also a p-pass O(n/p)-space deterministic algorithm. We also prove that there exists a language in DLIN, for which any p-pass deterministic algorithm for membership testing, requires Ω(n/p) space. We also study the application of fingerprinting technique to visibly pushdown languages, VPL s.
The other problem we consider is, given a degree sequence and a graph, checking whether the graph has the given degree sequence,
Deg-Seq. We prove that, any p-pass deterministic algorithm that takes as its input a degree sequence, followed by an adjacency list of a graph, requires
Ω(n/p) space to decide Deg-Seq. However, using randomness, for a more general input format: degree sequence, followed by a list of edges in any arbitrary
order, Deg-Seq can be decided in O(logn) space. We also give a p-pass, O(n/p)-space deterministic algorithm for Deg-Seq.
|
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13562-0_10 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
degree sequence,deterministic log-space,membership testing,p-pass deterministic algorithm,deterministic linear language,conventional deterministic log-space algorithm,general input format,pass algorithm,space deterministic algorithm,fingerprinting technique,error probability,streaming algorithm | Adjacency list,Inverse,Discrete mathematics,Combinatorics,Streaming algorithm,Polynomial,Computer science,Degree (graph theory),Deterministic algorithm,Randomness,Bounded function | Journal |
Volume | ISSN | ISBN |
17 | 0302-9743 | 3-642-13561-7 |
Citations | PageRank | References |
4 | 0.41 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ajesh Babu | 1 | 7 | 1.20 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Girish Varma | 3 | 45 | 9.38 |