Simons Institute for the Theory of Computing

Matrix multiplication underpins scientific computing and artificial intelligence, yet practical numerical libraries and hardware accelerators commonly retain the classical cubic-time algorithm despite decades of subcubic theoretical advances. This talk reviews the effort to make faster multiplication algorithms useful in practice. It examines why arithmetic complexity alone does not determine performance: some algorithms require enormous matrices or incur large hidden constants, while communication costs, numerical stability and the match between software and hardware create additional obstacles. The historical perspective connects asymptotic algorithm design to actual performance and power consumption.

Nearest-neighbor indexes usually rely on a single distance function, but accurate comparisons can be expensive. This talk proposes a bi-metric framework: a cheap proxy metric builds the index, while the query procedure uses a limited number of evaluations of both the proxy and an expensive ground-truth metric. The theory applies to DiskANN and Cover Tree. When the proxy approximates the ground-truth metric within a bounded factor, the resulting structure can achieve arbitrarily good approximation guarantees under the accurate metric. Experiments on text retrieval using models with very different computational costs show improved accuracy-efficiency tradeoffs on almost all MTEB datasets compared with alternatives such as reranking. Joint work with Haike Xu and Sandeep Silwal.

Finding similar item pairs is a core task in recommendation systems. It can be expressed as finding large inner products in a collection of vectors, or large entries in a matrix product. This talk describes how randomized sampling ideas became a distributed algorithm used in Twitter’s production recommendation system. Existing approaches struggled with industrial-scale inputs containing hundreds of billions of nonzero entries. The algorithm combines low-dimensional projections, called hashes, with path-sampling techniques, called wedges. The presentation explains the mathematical ideas behind this combination and its application at production scale. Joint work with Aneesh Sharma of Twitter and Ashish Goel of Stanford.

Theory for high-dimensional nearest-neighbor search often assumes a known search radius, a specified approximation ratio, and a request for one nearby point. Practical applications instead ask for the exact k nearest points without knowing the relevant radius; an appropriate approximation parameter also depends on the data distribution. Existing reductions between these formulations introduce polylogarithmic time or space overhead that can make them unattractive in practice. This talk presents simple, more efficient reductions that solve k-nearest-neighbor search using locality-sensitive hashing and address this gap between theoretical guarantees and practical queries. Joint work with Tobias Christiani and Mikkel Thorup.

This talk establishes a general reduction from nonlinear spectral gaps of metric spaces to data-dependent space partitions in the form of locality-sensitive hashing. The reduction yields an approach to high-dimensional approximate near-neighbor search and a data structure for any d-dimensional norm whose query algorithm makes a sublinear number of probes. Its approximation factor is O(log d), improving on the square-root-of-d factor available from the generic approach based on John’s ellipsoid. The presentation connects spectral properties, geometric partitions, and efficient approximate search. Joint work with Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.

Fast computation often trades statistical accuracy for speed. In nearest-neighbor prediction, achieving optimal accuracy generally requires the number of neighbors to grow as a root of the sample size, creating a corresponding computational burden even with fast search. This talk shows how bias or variance corrections after data quantization or subsampling, together with black-box fast-search techniques, can retain accuracy while reducing prediction-time computation to O(log n). The analysis explains how much quantization or subsampling is compatible with optimal accuracy. Extensive experiments on large datasets from several domains test these theoretical insights. The talk draws on work with N. Verma and L. Xue.

Locality-sensitive hashing is widely used for high-dimensional nearest-neighbor search. This talk develops another view of hashing as a biased sampling method for density-estimation queries. Given a point set and a query, one may estimate kernel density by summing distance-dependent influence functions, or count points within a chosen radius. A linear scan is costly for large datasets and many queries. The presentation surveys recent methods that preprocess the data and use locality-sensitive hashing to construct unbiased estimators for these problems and their extensions. It covers joint work with Arturs Backurs, Piotr Indyk, Vishnu Natchu, Paris Syminelakis, and Xian (Carrie) Wu.

At extreme scale, even conventional sampling and projection methods can become too expensive. This talk treats locality-sensitive hashing as an amortized constant-time adaptive sampler, connecting probabilistic hash tables with efficient unbiased statistical estimators. A few hash lookups can support adaptive estimation at a cost close to uniform sampling. Applications include partition-function estimation for large natural-language models such as word2vec, adaptive gradient estimation for stochastic gradient descent, and sublinear deep learning with very large parameter spaces. The talk also considers memory reduction through a hashing method related to count-min sketches. An example trains a classifier with 100,000 classes and 400,000 features on a single Titan X while using at most five percent of the memory needed to store all weights; a conventional logistic-regression model for that dataset requires 320 GB.

This talk examines randomized sampling methods for approximating positive semidefinite matrices. Fast leverage-score approximation combined with the Nystrom method yields provably accurate, linear-time algorithms for kernel ridge regression and kernel principal-component analysis, avoiding the usual quadratic-time cost. Related sampling techniques give relative-error low-rank approximations of positive semidefinite matrices in sublinear time without assumptions about incoherence or condition number. The results illustrate how randomized algorithms can exploit positive semidefinite structure beyond the capabilities of traditional methods. The talk concludes with open questions, particularly about oblivious sketches of kernel matrices.

This two-part tutorial considers the problem of indexing points in a metric space so that a query can efficiently retrieve an approximately closest stored point. It surveys established and newer data structures for high-dimensional nearest-neighbor search. The first part examines search under the l1 and Euclidean l2 distances, including locality-sensitive hashing and data-dependent hashing. The second part turns to non-Euclidean geometries and recent approaches such as spectral partitioning for metric spaces.

Building on the preceding linear-algebra tutorials, this lecture presents two further approaches to matrix sketching: leverage-score sampling and the Subsampled Randomized Hadamard Transform. It examines how these methods produce effective compressed matrix representations for a variety of applications.

This tutorial surveys nearly optimal algorithms for regression, low-rank approximation and related numerical problems. The central approach is sketch and solve: compress a large problem into a smaller representation, then apply an algorithm to that reduced problem. These techniques provide fast methods for fundamental machine-learning and numerical-linear-algebra tasks, with running times proportional to the number of nonzero entries in the input.

Worst-case bounds described as optimal can remain loose for the data encountered in practice. This talk develops distribution-specific analyses for local, nonparametric methods, focusing on nearest neighbors. The statistical results give closely matching upper and lower bounds for classification convergence for each data distribution, characterize metric measure spaces supporting universal consistency, and motivate a smoothness concept adapted to nearest-neighbor methods. The algorithmic results characterize the performance of tree-based nearest-neighbor search through the configuration of the data, with specializations to common forms of structure. The talk concludes with open statistical and algorithmic questions.

This talk develops optimal hashing methods for approximate nearest-neighbor search by reducing worst-case high-dimensional point sets to random instances. The approach connects the structure of arbitrary datasets with hashing constructions designed for random data. The work is joint with Ilya Razenshteyn.

Spectral methods for high-dimensional nearest-neighbor search can perform well in practice even when random projections appear preferable under worst-case theory. This talk studies that difference in a semi-random model: points lie in an unknown low-dimensional subspace and are then perturbed by Gaussian noise in the full ambient space. The algorithms repeatedly compute a leading principal component or subspace and achieve query times polynomial in the ambient dimension and logarithm of the number of points over substantial parameter ranges. They can remain effective when noise is much larger than the distances among the original points. The work is joint with Amirali Abdullah, Ravi Kannan and Robi Krauthgamer.

The success of deep neural networks raises questions about the scalability of kernel methods and the roles of large datasets, depth and training algorithms. This talk examines techniques that make kernel learning practical for large datasets in both scalar and multivariate prediction. The methods combine randomized data embeddings, Quasi-Monte Carlo acceleration, distributed convex optimization and input-output kernel learning. Experiments on speech-recognition and computer-vision datasets compare randomized kernel methods with deep neural networks and report essentially matching performance. The talk explores how randomized kernel constructions can resemble neural-network architectures, and how invariant kernel learning and matrix-valued kernels might support deeper architectures. It discusses research results and connections between these approaches.

Randomization offers an alternative approach to large matrix computations arising in scientific data analysis. This talk explains how randomized algorithms approximate matrix multiplication and singular-value decomposition, solve least-squares problems and linear systems, and support data-analysis applications. The accompanying presentation develops matrix sketches through row and column sampling, compares length-squared sampling with leverage-score sampling, and describes their use in low-rank approximation and matrix factorizations. It also explains how leverage scores can be approximated efficiently and how sampling guarantees support least-squares and feature-selection procedures.