Information Complexity and Data Stream Algorithms for Basic Problems
Loading...
Date
2010-12-09
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Data stream algorithms obtain their input as a stream of data elements that have to be processed
immediately as they arrive using only a very limited amount of memory. They solve a
new class of algorithmic problems that emerged recently with the growing importance of computer
networks and the ever-increasing size of the data sets that are processed algorithmically.
In this thesis data stream algorithms for basic problems under extreme space restrictions are
developed, namely counting and random sampling. Then we apply these algorithms to improve
the space complexity of the celebrated data stream algorithm for the computation of
frequency moments by Alon, Matias, and Szegedy for very long data streams.
Lower bounds on the space complexity of data stream algorithms are usually proved
by using communication complexity arguments. Information complexity is a related field
that applies Shannon's information theory to obtain lower bounds on the communication
complexity of functions. The development of information complexity is closely linked to the
recent interest in data stream algorithms since important parts of this theory have been
developed to prove a lower bound on the space complexity of data stream algorithms for
the frequency moments. In this thesis we prove an optimal lower bound on the multi-party
information complexity of the disjointness function, the underlying communication problem
in the proof of the lower bound on the space complexity of data stream algorithms for the
frequency moments. Additionally, we generalize and simplify known lower bounds on the
one-way communication complexity of the index function by using information complexity
and we present the first attempt to apply information complexity to multi-party one-way
protocols in the number on the forehead model by Chandra, Furst, and Lipton.
Description
Table of contents
Keywords
Kommunikationskomplexität, Informationstheorie, Datenstromalgorithmen