Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DATA STREAMING:
Reports tagged with data streaming:
TR07-088 | 7th September 2007
Elad Hazan, C. Seshadhri

Adaptive Algorithms for Online Decision Problems

Revisions: 1

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>


TR15-113 | 9th July 2015
Amit Chakrabarti, Tony Wirth

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Set cover, over a universe of size $n$, may be modelled as a
data-streaming problem, where the $m$ sets that comprise the instance
are to be read one by one. A semi-streaming algorithm is allowed only
$O(n \text{ poly}\{\log n, \log m\})$ space to process this ... more >>>




ISSN 1433-8092 | Imprint