We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and
property testing problems such as estimating the size of maximum matchings and maximum …

Correlation clustering is a fundamental optimization problem at the intersection of machine
learning and theoretical computer science. Motivated by applications to big data processing …

Consider the following gap cycle counting problem in the streaming model: The edges of a 2-
regular n-vertex graph G are arriving one-by-one in a stream and we are promised that G is …

We continue the study of the communication complexity of gap cycle counting problems.
These problems have been introduced by Verbin and Yu [SODA 2011] and have found …

Abstract The Hierarchical Clustering (HC) problem consists of building a hierarchy of
clusters to represent a given dataset. Motivated by the modern large-scale applications, we …

We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP
problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give …

We consider the Max-Cut problem, asking how much space is needed by a streaming
algorithm in order to estimate the value of the maximum cut in a graph. This problem has …

We consider the approximability of constraint satisfaction problems in the streaming setting.
For every constraint satisfaction problem (CSP) on n variables taking values in {0,…, q− 1} …

Motivated by recent works on streaming algorithms for constraint satisfaction problems
(CSPs), we define and analyze oblivious algorithms for the Max-$ k $ AND problem. This …

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs)
when the constraints arrive in a random order. We show that there exists a CSP, namely Max …