Frederic Magniez, Claire Mathieu, Ashwin Nayak

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis.

We present a one-pass randomized streaming ... more >>>

Nathanaël François, Frederic Magniez

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

SUBSET SUM is a well known NP-complete problem:

given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ...
more >>>

Anup Rao, Makrand Sinha

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont

In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>>

Tim Roughgarden

This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at

Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>>

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,

the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.

This improves upon the previous work ...
more >>>

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff

A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, $\ell_2$ approximation, finding a nonzero entry in a vector (for turnstile algorithms) ... more >>>