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.

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.

Zhiyang Xun, Eric Price

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

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.

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.

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.

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.

Zhihao Zhang, Lanzheng Liu, Chen Chen et al.

Provides a high-speed IPv6 lookup solution for network packet forwarding, addressing inefficiencies in existing algorithms for long-prefix FIBs.

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.

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.

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.

Sarah Cannon, Topher Pankow, Wesley Pegden et al.

For computational redistricting and other applications requiring balanced partitions, this algorithm removes a major computational bottleneck, enabling faster sampling on large planar graphs.

Paul Dütting, Federico Fusco, Silvio Lattanzi et al.

This work addresses the problem of maintaining near-optimal solutions in fully dynamic submodular maximization, providing the first algorithms with provable guarantees for consistency in the presence of deletions.

Christian Coester, Yichen Huang

This work provides a new framework for online metric embeddings that overcomes fundamental lower bounds, benefiting algorithm designers who rely on HST embeddings for online problems.

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.

Xiaoyu Li, Andi Han, Jiaojiao Jiang et al.

This work provides foundational theoretical results for learning from relational (contrastive) supervision in the limit, which is relevant to computational learning theory and may impact practical contrastive learning methods.

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.

Mengyuan Hu, An Zhang, Yong Chen et al.

For researchers in graph algorithms and approximation, this work offers improved theoretical guarantees and hardness results for a natural vertex-covering problem with interval constraints.

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.