In this paper we provide new randomized algorithms with improved runtimes for solving
linear programs with two-sided constraints. In the special case of the minimum cost flow …

We design a new distribution over m× n matrices S so that, for any fixed n× d matrix A of rank
r, with probability at least 9/10,∥ SAx∥ 2=(1±ε)∥ Ax∥ 2 simultaneously for all x∈ R d …

We present an ̃O(m+n^1.5)-time randomized algorithm for maximum cardinality bipartite
matching and related problems (eg transshipment, negative-weight shortest paths, and …

An oblivious subspace embedding (OSE) given some parameters ε, d is a distribution D over
matrices Π∈ R m× n such that for any linear subspace W⊆ R n with dim (W)= d, P Π~ D (∀ …

When processing massive data sets, a core task is to construct synopses of the data. To be
useful, a synopsis data structure should be easy to construct while also yielding good …

We give two different and simple constructions for dimensionality reduction in ℓ 2 via linear
mappings that are sparse: only an O (ε)-fraction of entries in each column of our embedding …

We present a new locally differentially private algorithm for the heavy hitters problem that
achieves optimal worst-case error as a function of all standardly considered parameters …

We give an algorithm for computing exact maximum flows on graphs with edges and integer
capacities in the range in time. We use to suppress logarithmic factors in. For sparse graphs …

In this paper we provide an O (nd+ d 3) time randomized algorithm for solving linear
programs with d variables and n constraints with high probability. To obtain this result we …

In the adversarially robust streaming model, a stream of elements is presented to an
algorithm and is allowed to depend on the output of the algorithm at earlier times during the …