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 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 …

Many convex problems in machine learning and computer science share the same
form:\begin {align*}\min_ {x}\sum_ {i} f_i (A_i x+ b_i),\end {align*} where $ f_i $ are convex …

We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is
specified by k nonnegative mixing weights p 1,…, pk summing to 1, and k unknown …

In the long-studied problem of combinatorial group testing, one is asked to detect a set of k
defective items out of a population of size n, using m≪ n disjunctive measurements. In the …

This paper attempts to answer the question whether neural network pruning can be used as
a tool to achieve differential privacy without losing much data utility. As a first step towards …

In a traditional time-domain ghost imaging system, it is necessary to employ a Fourier
transformation to obtain the spectral information of a signal when the time-domain signal is …

Computing the convolution A⋆ B of two length-n vectors A, B is an ubiquitous computational
primitive, with applications in a variety of disciplines. Within theoretical computer science …

The ability to resolve detail in the object that is being imaged, named by resolution, is the
core parameter of an imaging system. Super-resolution is a class of techniques that can …

This monograph discusses the emerging theory of deep learning. It originated from notes by
the lecturers at a graduate seminar taught at Princeton University in Fall 2019 in conjunction …