Data Structures & Algorithms

Shenghu Jiang, Ruihao Gong

This work addresses the problem of inefficient tokenization in streaming settings for large language model pipelines, offering practical latency benefits for developers and users.

Amatya Sharma, Santhoshini Velusamy

For CSP theorists, this provides a near-complete classification of a structural parameter governing kernelization and sparsification for a natural class of constraints.

Amatya Sharma, Santhoshini Velusamy

For theoretical computer scientists studying streaming algorithms and CSPs, this provides a complete characterization of streaming complexity for a broad class of problems, resolving an open question.

Jon Kleinberg, Anay Mehrotra, Amin Saberi et al.

For theoretical computer science and learning theory, this work extends classical results on memory-constrained learning to language generation, revealing fundamental differences between generation, density, and identification tasks.

Steve Hanneke, Anay Mehrotra, Grigoris Velegkas et al.

Provides a theoretical characterization and first algorithm for a classic but understudied learning model, clarifying the role of membership queries.

Jon Kleinberg, Charlotte Peale, Omer Reingold

This work addresses the problem of cumulative errors in language generation for learning theorists, offering a formal framework and trade-off analysis that advances the theoretical understanding of mistake-bounded generation.

Yunbum Kook, Santosh S. Vempala

This is an incremental survey that reviews an existing method with broad applications in areas like isoperimetric inequalities, optimization, and Markov chains, but does not introduce new results.

Mingda Qiao

This work addresses fundamental computational and statistical challenges in evaluating calibration for machine learning models, with implications for reliability assessment in AI systems.

Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju et al.

This solves the central open question for stochastic vertex cover, providing an optimal algorithm that matches the lower bound for any constant-factor approximation.

Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy

Provides tight streaming lower bounds for a broad class of constraint satisfaction problems, resolving a key question in streaming complexity.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan et al.

This work provides foundational streaming lower bounds for CSPs, extending prior results to general parameters and addressing a gap in linear space bounds for approximation factors less than 1/2.

Santhoshini Velusamy

This work makes progress on a fundamental open problem in streaming algorithms for constraint satisfaction problems, offering a near-optimal approximation with fewer passes.

Alexander Zlokapa, Bobak T. Kiani

This work addresses the challenge of quantum advantage in thermal expectation estimation, revealing classical tractability in regimes previously thought to require quantum computation, though it is incremental in extending known high-temperature results.

Amir Azarmehr, Soheil Behnezhad, Shane Ferrante

This resolves a key open problem in streaming algorithms for constraint satisfaction, with implications for applications like Max-DiCut.

Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi

This resolves the computational bottleneck of finding warm starts for HMC, which is crucial for practitioners in statistics, engineering, and sciences who rely on HMC for high-dimensional sampling, though it is incremental as it builds on prior theoretical work.

Jason Li

This solves a fundamental graph algorithm problem for computer scientists and practitioners, with potential applications in network routing and optimization.

Fabio Massimo Zanzotto, Federico Ranaldi, Giorgio Satta

This work offers a new approach to neuro-symbolic methodologies by directly embedding algorithms into neural networks, which could benefit researchers working on interpretable and efficient parsing for specific grammar types.

Zhiyang Xun, Eric Price

Provides fundamental limits for diffusion sampling acceleration, relevant to researchers designing faster sampling algorithms.

Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar et al. · harvard

This work addresses calibration and prediction robustness for machine learning practitioners, offering incremental theoretical extensions to prior results.

Allan Borodin, Christodoulos Karavasilis, David Zhang

This work addresses the fundamental question of whether randomized algorithms can outperform deterministic ones in the random-order model, with implications for online algorithm design in domains like scheduling and resource allocation, though it appears incremental in its approach.