Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > STREAMING ALGORITHMS, MEMBERSHIP TESTING, CONTEXT-FREE LANGUAGES, FINGER PRINTING:
Reports tagged with Streaming algorithms, membership testing, context-free languages, finger printing:
TR10-094 | 17th May 2010
Ajesh Babu, Nutan Limaye, Girish Varma

Streaming algorithms for some problems in log-space.

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 ... more >>>




ISSN 1433-8092 | Imprint