Over the last few years, graph-based approaches to nearest neighbor search have attracted renewed interest. Algorithms such as HNSW, NSG, and DiskANN have become popular tools in practice. These algorithms are highly versatile and come with efficient implementations. At the same time, their correctness, performance guarantees, and functionality are not fully understood. In this talk, I will discuss the challenges and opportunities presented by this class of algorithms, as well as some connections to older methods.

The talk will be based on the following papers:

• Indyk, Piotr, and Haike Xu. “Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations.” Advances in Neural Information Processing Systems, 2023.
• Xu, Haike, Sandeep Silwal, and Piotr Indyk. “A bi-metric framework for fast similarity search.” International Conference on Machine Learning, 2026.
• Feng, Ying, Piotr Indyk, Michael Kapralov, Dmitry Krachun, and Boris Prokhorov. “Provable quantization with randomized Hadamard transform.” arXiv preprint arXiv:2605.13810, 2026.

Motivated by research in big data computing, we study (parameterized) algorithms that run in linear or quasi-linear time with limited space complexity. By a multivariate nature, this model offers mechanisms for formal analysis of both efficiency and effectiveness of big data computing, measuring the complexity of accessing input data of very large size n and analyzing the additional computational costs (time and space) that are bounded by polynomials of the parameter k and needed in the limited local computing resources. We develop such algorithms for well-known computational problems, such as the (polynomial-time solvable) Maximum Weighted Matching problem and the (NP-hard) Line-Cover problem.

A probabilistic forecaster is calibrated if it is unbiased conditioned on each predicted value, e.g., among the events to which it assigns probability 70%, roughly 70% actually occur. Calibration is a classical criterion for evaluating probabilistic predictions, but a basic question remains surprisingly unsettled: how should we quantify the amount of miscalibration?

In the first part of the talk, I will approach this question from an incentive perspective. Ideally, a calibration measure should encourage a forecaster to report its true beliefs. However, many existing measures fail this property: a forecaster can sometimes obtain a much smaller calibration error by deliberately misreporting. We then introduce new calibration measures that are approximately truthful.

In the second part, I will focus on the distance from calibration: the minimum distance between a predictor and a perfectly calibrated one. This measure has several appealing conceptual properties, but raises basic algorithmic and statistical questions: How efficiently can it be computed? How many samples are needed to estimate it? I will describe algorithms and hardness results that give an almost complete picture of these questions.

This talk is based on joint work with Nika Haghtalab, Kunhe Yang, Eric Zhao, and Letian Zheng.

Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sophisticated sampling procedures from LLMs have been proposed to solve challenging reasoning problems. The efficacy of such sampling algorithms is limited, however, by the relationship between the LLM and the particular sampling task at hand, which has motivated the framework of test-time training (TTT). TTT works by updating a model's weights in response to partial generations and reward feedback received at inference time, thus adapting to the particular problem. In this work, we propose a formalization for TTT as the problem of producing a sample from a given probability measure μ⋆ belonging to a known class F of distributions, given an oracle μ̂ which yields approximate density estimates for μ⋆. This is closely related to the problem of reducing sampling to approximate counting studied in seminal works of Jerrum, Valiant and Vazirani (1986) and Sinclair and Jerrum (1989): namely, when F is the class of all distributions, it coincides exactly with the aforementioned counting-to-sampling reduction.

In this paper, we first show a quadratic lower bound on the query complexity of sampling from μ⋆ given query access to μ̂ (for sufficiently large classes F), thus showing that the random walk approach proposed by Sinclair and Jerrum (1989) and refined by Hayes and Sinclair (2010) is optimal. This answers an open question posed by Hayes and Sinclair. We then show that this lower bound can be circumvented if the size of F is bounded appropriately. As we discuss, this latter result can be viewed as an abstraction of TTT, and thus represents a starting point for the development of a principled theoretical framework for TTT. Joint work with Ankur Moitra and Dhruv Rohatgi.

Human feedback is often reduced to binary choices: one option is preferred to another, one answer is ranked above another, or one policy is selected over a competing alternative. This talk argues that such choice-only data can discard economically and statistically important information. Building on a general framework for estimating preferences from both choices and response times, I will show how response-time data can sharpen preference estimation, deliver fast convergence rates under drift-diffusion models, and improve the estimation of economically meaningful parameters in applications such as intertemporal choice. I will then connect this methodology to a central problem in AI alignment: learning a representative reward model from heterogeneous, often anonymous human labelers. In this setting, pooled binary feedback can make population-average preferences unidentifiable, leading to systematic distortions in the learned policy. I will show that response times provide a simple, low-cost additional signal that can restore identifiability and enable consistent estimation of average preferences, even when each labeler contributes only a single comparison.

The standard approach to algorithm development is to focus on a specific problem and develop for it a specific algorithm. Codd's introduction of the relational model in 1970 included two fundamental ideas: (1) Relations provide a universal data representation formalism, and (2) Relational databases can be queried using first-order logic. Realizing these ideas required the development of a meta-algorithm, which takes a declarative query and executes it with respect to a database. In this talk, I will describe this approach, which I call Logical Algorithmics, in detail, and explore its profound ramification.

Planning with geometric constraints has long been studied and sits at the intersection of multiple fields. It gives rise to interesting optimization problems. I will address two specific problems, one on finding a valid trajectory for a robotic arm subject to obstacle clearance and one on querying geometric objects (points, line segments) with various objective functions.

The area of quantum learning theory focuses on learning quantum objects such as states or unitaries with as few resources as possible. Up until recently, for many of these problems, we either did not have optimal algorithms, or we did have optimal algorithms, but these algorithms were difficult to describe and even more difficult to analyze. This has changed over the last year, however, due to a new, unifying tool known as the random purification channel, which has led to optimal algorithms for many problems in quantum learning theory which are conceptually clean and easy to analyze. In this talk, I will introduce the random purification channel and show several applications of it. No prior background in quantum computing will be assumed.

This is based on joint works with Angelos Pelecanos, Jack Spilecki, Ewin Tang, and Mark Zhandry.

In this talk, I will survey some recent results in realizing advanced cryptographic notions from lattices. I will focus on a new object called a succinct matrix commitment and then show how it enables applications to broadcast encryption, succinct arguments, and more.