The nearest neighbor problem is defined as follows: Given a set P of n points in some metric
space (X, D), build a data structure that, given any point q, returns a point in P that is closest …

Kernel methods are fundamental tools in machine learning that allow detection of non-linear
dependencies between data without explicitly constructing feature vectors in high …

We show tight upper and lower bounds for time-space trade-offs for the c-approximate Near
Neighbor Search problem. For the d-dimensional Euclidean space and n-point datasets, we …

We give a simple, multiplicative-weight update algorithm for learning undirected graphical
models or Markov random fields (MRFs). The approach is new, and for the well-studied case …

We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs),
which are functions of the form $\mathbf {x}\mapsto\mathsf {max}(0,\mathbf {w}⋅\mathbf {x}) …

We prove conditional near-quadratic running time lower bounds for approximate
Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically …

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying
assignment x∈{0, 1} n to a CNF formula φ is shared between two parties, where Alice …

We design new polynomials for representing threshold functions in three different regimes:
probabilistic polynomials of low degree, which need far less randomness than previous …

We consider the problem of computing the best-fitting ReLU with respect to square-loss on a
training set when the examples have been drawn according to a spherical Gaussian …

We consider the problem of testing and learning quantum k-juntas: n-qubit unitary matrices
which act non-trivially on just k of the n qubits and as the identity on the rest. As our main …