How can multiple distributed entities train a shared deep net on their private data while
protecting data privacy? This paper introduces InstaHide, a simple encryption of training …

This survey highlights the recent advances in algorithms for numerical linear algebra that
have come from the technique of linear sketching, whereby given a matrix, one first …

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 …

Motivated by recent Linear Programming solvers, we design dynamic data structures for
maintaining the inverse of an $ n\times n $ real matrix under $\textit {low-rank} $ updates …

We consider the problem of computing the k-sparse approximation to the discrete Fourier
transform of an n-dimensional signal. We show: An O (k log n)-time randomized algorithm for …

In this paper, we survey algorithms for sparse recovery problems that are based on sparse
random matrices. Such matrices has several attractive properties: they support algorithms …

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 …

This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of
the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013 …

The fastest known LP solver for general (dense) linear programs is due to [Cohen, Lee and
Song'19] and runs in O*(n ω+ n 2.5− α/2+ n 2+ 1/6) time. A number of follow-up works [Lee …

We present the first single pass algorithm for computing spectral sparsifiers for graphs in the
dynamic semi-streaming model. Given a single pass over a stream containing insertions and …