Promised streaming algorithms and finding pseudo-repetitions
| dc.contributor.advisor | Hajiaghayi, MohammadTaghi | en_US |
| dc.contributor.author | Tiseanu, Catalin Stefan | en_US |
| dc.contributor.department | Computer Science | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2013-10-02T05:31:50Z | |
| dc.date.available | 2013-10-02T05:31:50Z | |
| dc.date.issued | 2013 | en_US |
| dc.description.abstract | As the size of data available for processing increases, new models of computation are needed. This motivates the study of data streams, which are sequences of information for which each element can be read only after the previous one. In this work we study two particular types of streaming variants: promised graph streaming algorithms and combinatorial queries on large words. We give an &omega(n) lower bound for working memory, where n is the number of vertices of the graph, for a variety of problems for which the graphs are promised to be forests. The crux of the proofs is based on reductions from the field of communication complexity. Finally, we give an upper bound for two problems related to finding pseudo-repetitions on words via anti-/morphisms, for which we also propose streaming versions. | en_US |
| dc.identifier.uri | http://hdl.handle.net/1903/14455 | |
| dc.subject.pqcontrolled | Computer science | en_US |
| dc.subject.pquncontrolled | algorithms | en_US |
| dc.subject.pquncontrolled | combinatorial properties | en_US |
| dc.subject.pquncontrolled | data streams | en_US |
| dc.subject.pquncontrolled | graph streaming | en_US |
| dc.subject.pquncontrolled | lower bounds | en_US |
| dc.title | Promised streaming algorithms and finding pseudo-repetitions | en_US |
| dc.type | Thesis | en_US |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Tiseanu_umd_0117N_14383.pdf
- Size:
- 417.21 KB
- Format:
- Adobe Portable Document Format