| 2025 | (Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow. Ohad Trabelsi |
| 2025 | A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM. Peyman Afshani, Nodari Sitchinava |
| 2025 | A Cut-Matching Game for Constant-Hop Expanders. Bernhard Haeupler, Jonas Hübotter, Mohsen Ghaffari |
| 2025 | A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs. Daniel Paul-Pena, C. Seshadhri |
| 2025 | A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces. Éric Colin de Verdière, Vincent Despré, Loïc Dubois |
| 2025 | A Fast Algorithm for Computing Zigzag Representatives. Tamal K. Dey, Tao Hou, Dmitriy Morozov |
| 2025 | A Lower Bound for Light Spanners in General Graphs. Greg Bodwin, Jeremy Flics |
| 2025 | A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization. Shuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang, Gregory Kehne, Rojin Rezvan |
| 2025 | A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs. Chandra Chekuri, Rhea Jain |
| 2025 | A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix. Yanlin Chen, András Gilyén, Ronald de Wolf |
| 2025 | A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design. Matteo Castiglioni, Junjie Chen, Minming Li, Haifeng Xu, Song Zuo |
| 2025 | A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices. Seth Pettie, Gábor Tardos |
| 2025 | A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints. Jesper Nederlof, Céline M. F. Swennenhuis, Karol Wegrzycki |
| 2025 | A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs. Varsha Dani, Thomas P. Hayes |
| 2025 | A Tight (3/2 + Franziska Eberle, Felix Hommelsheim, Malin Rau, Stefan Walzer |
| 2025 | A Tight VC-Dimension Analysis of Clustering Coresets with Applications. Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn |
| 2025 | A coarse Erdős-Pósa theorem. Jungho Ahn, Jochen Pascal Gollin, Tony Huynh, O-joung Kwon |
| 2025 | A topological proof of the Hell-Nešetřil dichotomy. Sebastian Meyer, Jakub Oprsal |
| 2025 | All-Hops Shortest Paths. Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu, Uri Zwick |
| 2025 | Almost Tight Bounds for Differentially Private Densest Subgraph. Michael Dinitz, Satyen Kale, Silvio Lattanzi, Sergei Vassilvitskii |
| 2025 | An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs. Natan Rubin |
| 2025 | An Efficient Uniqueness Theorem for Overcomplete Tensor Decomposition. Pascal Koiran |
| 2025 | An Elementary Predictor Obtaining Distance to Calibration. Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, Mirah Shi |
| 2025 | An analogue of Reed's conjecture for digraphs. Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta |
| 2025 | Approximately Counting Knapsack Solutions in Subquadratic Time. Weiming Feng, Ce Jin |
| 2025 | Approximating Competitive Equilibrium by Nash Welfare. Jugal Garg, Yixin Tao, László A. Végh |
| 2025 | Approximating Traveling Salesman Problems Using a Bridge Lemma. Martin Böhm, Zachary Friggstad, Tobias Mömke, Joachim Spoerhase |
| 2025 | Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs. Shi Li |
| 2025 | Asynchronous 3-Majority Dynamics with Many Opinions. Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, Takeharu Shiraga |
| 2025 | Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More. Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, Virginia Vassilevska Williams |
| 2025 | Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees. Swati Gupta, Jai Moondra, Mohit Singh |
| 2025 | Beating Bellman's Algorithm for Subset Sum. Karl Bringmann, Nick Fischer, Vasileios Nakos |
| 2025 | Beyond 2-Approximation for Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein |
| 2025 | Bounding Romain Bourneuf, Marcin Pilipczuk |
| 2025 | Breaking the Two Approximation Barrier for Various Consensus Clustering Problems. Debarati Das, Amit Kumar |
| 2025 | Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs. Feodor F. Dragan, Guillaume Ducoffe, Michel Habib, Laurent Viennot |
| 2025 | Clock Auctions Augmented with Unreliable Advice. Vasilis Gkatzelis, Daniel Schoepflin, Xizhi Tan |
| 2025 | Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation. Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas |
| 2025 | Clustering to Minimize Cluster-Aware Norm Objectives. Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase |
| 2025 | Competitive strategies to use "warm start" algorithms with predictions. Avrim Blum, Vaidehi Srinivas |
| 2025 | Complexity of polytope diameters via perfect matchings. Christian Nöbel, Raphael Steiner |
| 2025 | Computing the second and third systoles of a combinatorial surface. Matthijs Ebbens, Francis Lazarus |
| 2025 | Congestion-Approximators from the Bottom Up. Jason Li, Satish Rao, Di Wang |
| 2025 | Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies. Yaowei Long, Seth Pettie, Thatchaphol Saranurak |
| 2025 | Constraint Satisfaction Problems with Advice. Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev |
| 2025 | Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds. Lingxiao Huang, Jian Li, Pinyan Lu, Xuan Wu |
| 2025 | Counting Small Induced Subgraphs: Hardness via Fourier Analysis. Radu Curticapean, Daniel Neuen |
| 2025 | Crossing Number in Slightly Superexponential Time (Extended Abstract). Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Jie Xue, Meirav Zehavi |
| 2025 | Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint. Prommy Sultana Hossain, Xintong Wang, Fang-Yi Yu |
| 2025 | Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries. Aditya Anand, Thatchaphol Saranurak, Yunfan Wang |
| 2025 | Deterministic Online Bipartite Edge Coloring. Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc |
| 2025 | Differentiable Approximations for Distance Queries. Ahmed Abdelkader, David M. Mount |
| 2025 | Dynamic Consistent Sebastian Forster, Antonis Skarlatos |
| 2025 | Efficient William Kuszmaul, Michael Mitzenmacher |
| 2025 | Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric. Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, Keegan Yao |
| 2025 | Embedding Planar Graphs into Graphs of Treewidth Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michal Pilipczuk |
| 2025 | Embedding Probability Distributions into Low Dimensional ℓ Moses Charikar, Spencer Compton, Chirag Pabbaraju |
| 2025 | Entropy Regularization and Faster Decremental Matching in General Graphs. Jiale Chen, Aaron Sidford, Ta-Wei Tu |
| 2025 | Eulerian Graph Sparsification by Effective Resistance Decomposition. Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, Yibin Zhao |
| 2025 | Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains. Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang |
| 2025 | Exact Thresholds for Noisy Non-Adaptive Group Testing. Junren Chen, Jonathan Scarlett |
| 2025 | FPTAS for Holant Problems with Log-Concave Signatures. Kun He, Zhidan Li, Guoliang Qiu, Chihao Zhang |
| 2025 | Facet-Hamiltonicity. Hugo A. Akitaya, Jean Cardinal, Stefan Felsner, Linda Kleist, Robert Lauff |
| 2025 | Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture. Andreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, Kevin Pratt |
| 2025 | Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching. Sujoy Bhore, Timothy M. Chan |
| 2025 | Fast and Simple Sorting Using Partial Information. Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhon, Robert E. Tarjan, Jakub Tetek |
| 2025 | Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs. Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz |
| 2025 | Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning. Michal Derezinski, Christopher Musco, Jiaming Yang |
| 2025 | Faster Vizing and Near-Vizing Edge Coloring Algorithms. Sepehr Assadi |
| 2025 | Faster single-source shortest paths with negative real weights via proper hop distance. Yufan Huang, Peter Jin, Kent Quanrud |
| 2025 | Faster two-dimensional pattern matching with Jonas Ellert, Pawel Gawrychowski, Adam Górkiewicz, Tatiana Starikovskaya |
| 2025 | Finding irrelevant vertices in linear time on bounded-genus graphs. Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis, Dimitrios M. Thilikos |
| 2025 | Fine-Grained Optimality of Partially Dynamic Shortest Paths and More. Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye |
| 2025 | Fixed-Parameter Tractability of Hedge Cut. Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Daniel Lokshtanov, Saket Saurabh |
| 2025 | Flip Dynamics for Sampling Colorings: Improving (11/6 - ε) Using A Simple Metric. Charlie Carlson, Eric Vigoda |
| 2025 | Flipping Non-Crossing Spanning Trees. Håvard Bakke Bjerkevik, Linda Kleist, Torsten Ueckerdt, Birgit Vogtenhuber |
| 2025 | Forall-exist statements in pseudopolynomial time. Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, Robert Weismantel |
| 2025 | From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs. Simon Döring, Dániel Marx, Philip Wellnitz |
| 2025 | Fréchet Distance in Subquadratic Time. Siu-Wing Cheng, Haoqiang Huang |
| 2025 | Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries. Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim |
| 2025 | Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition. Julia Chuzhoy, Merav Parter |
| 2025 | Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation. Antoine El-Hayek, Monika Henzinger, Jason Li |
| 2025 | Fully-Distributed Byzantine Agreement in Sparse Networks. John Augustine, Fabien Dufoulon, Gopal Pandurangan |
| 2025 | Gains-from-Trade in Bilateral Trade with a Broker. Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Gary Peng, Suho Shin |
| 2025 | Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets. Shimon Kogan, Merav Parter |
| 2025 | Hermitian Diagonalization in Linear Precision. Rikhav Shah |
| 2025 | Highway Dimension: a Metric View. Andreas Emil Feldmann, Arnold Filtser |
| 2025 | Hiring for An Uncertain Task: Joint Design of Information and Contracts. Matteo Castiglioni, Junjie Chen |
| 2025 | Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs. Sepehr Assadi, Sanjeev Khanna, Peter Kiss |
| 2025 | Improved Differentially Private Continual Observation Using Group Algebra. Monika Henzinger, Jalaj Upadhyay |
| 2025 | Improved Explicit Near-Optimal Codes in the High-Noise Regimes. Xin Li, Songtao Mao |
| 2025 | Improved List Size for Folded Reed-Solomon Codes. Shashank Srivastava |
| 2025 | Improved Online Reachability Preservers. Greg Bodwin, Tuong Le |
| 2025 | Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths. Greg Bodwin, Lily Wang |
| 2025 | Improved Spectral Density Estimation via Explicit and Implicit Deflation. Rajarshi Bhattacharjee, Rajesh Jayaram, Cameron Musco, Christopher Musco, Archan Ray |
| 2025 | Improving the Leading Constant of Matrix Multiplication. Josh Alman, Hantao Yu |
| 2025 | Inapproximability of Maximum Diameter Clustering for Few Clusters. Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov |
| 2025 | Integer programs with nearly totally unimodular matrices: the cographic case. Manuel Aprile, Samuel Fiorini, Gwenaël Joret, Stefan Kober, Miehal T. Seweryn, Stefan Weltge, Yelena Yuditsky |
| 2025 | Lift-and-Project Integrality Gaps for Santa Claus. Étienne Bamas |
| 2025 | Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups. Ruiwen Dong |
| 2025 | Lipschitz Continuous Algorithms for Covering Problems. Soh Kumabe, Yuichi Yoshida |
| 2025 | Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions. Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan |
| 2025 | Locally Testable Tree Codes. Tamer Mour, Alon Rosen, Ron Rothblum |
| 2025 | Losing Treewidth In The Presence Of Weights. Michal Wlodarczyk |
| 2025 | Low Degree Local Correction Over the Boolean Cube. Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan |
| 2025 | Lower Bounds for Convexity Testing. Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten |
| 2025 | Majorized Bayesian Persuasion and Fair Selection. Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, Kangning Wang |
| 2025 | Massively Parallel Minimum Spanning Tree in General Metric Spaces. Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, Peilin Zhong |
| 2025 | Matching Composition and Efficient Weight Reduction in Dynamic Matching. Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu |
| 2025 | Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity. Karthik C. S., Subhash Khot |
| 2025 | Mean-field Potts and random-cluster dynamics from high-entropy initializations. Antonio Blanca, Reza Gheissari, Xusheng Zhang |
| 2025 | Min-CSPs on Complete Instances. Aditya Anand, Euiwoong Lee, Amatya Sharma |
| 2025 | Minimum Convex Hull and Maximum Overlap of Two Convex Polytopes. Mook Kwon Jung, Seokyun Kang, Hee-Kap Ahn |
| 2025 | More Asymmetry Yields Faster Matrix Multiplication. Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou |
| 2025 | More Efficient Approximate Lucas Gretta, William He, Angelos Pelecanos |
| 2025 | Multi-Agent Combinatorial Contracts. Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim |
| 2025 | Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors. Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, Huacheng Yu |
| 2025 | Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching. Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz |
| 2025 | Near-optimal hierarchical matrix approximation from matrix-vector products. Tyler Chen, Feyza Duman Keles, Diana Halikias, Cameron Musco, Christopher Musco, David Persson |
| 2025 | Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in- Anton Bukov, Shay Solomon, Tianyi Zhang |
| 2025 | Nearly Tight Bounds on Testing of Metric Properties. Yiqiao Bao, Sampath Kannan, Erik Waingarten |
| 2025 | New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching. Nick Fischer, Ce Jin, Yinzhan Xu |
| 2025 | New Approximation Algorithms and Reductions for Shiri Chechik, Itay Hoch, Gur Lifshitz |
| 2025 | New Combinatorial Insights for Monotone Apportionment. Javier Cembrano, José Correa, Ulrike Schmidt-Kraepelin, Alexandros Tsigonias-Dimitriadis, Victor Verdugo |
| 2025 | New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc |
| 2025 | New Prophet Inequalities via Poissonization and Sharding. Elfarouk Harb |
| 2025 | New Separations and Reductions for Directed Hopsets and Preservers. Gary Hoppenworth, Yinzhan Xu, Zixuan Xu |
| 2025 | On Estimating the Trace of Quantum State Powers. Yupan Liu, Qisheng Wang |
| 2025 | On the Decidability of Presburger Arithmetic Expanded with Powers. Toghrul Karimov, Florian Luca, Joris Nieuwveld, Joël Ouaknine, James Worrell |
| 2025 | On the Locality of Hall's Theorem. Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, Jara Uitto |
| 2025 | On the Uniqueness of Bayesian Coarse Correlated Equilibria in Standard First-Price and All-Pay Auctions. Mete Seref Ahunbay, Martin Bichler |
| 2025 | Online Dependent Rounding Schemes for Bipartite Matchings, with. Joseph (Seffi) Naor, Aravind Srinivasan, David Wajc |
| 2025 | Online Scheduling via Gradient Descent for Weighted Flow Time Minimization. Qingyun Chen, Sungjin Im, Aditya Petety |
| 2025 | Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree. Charlie Carlson, Xiaoyu Chen, Weiming Feng, Eric Vigoda |
| 2025 | Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares. Hongjie Chen, Deepak Narayanan Sridharan, David Steurer |
| 2025 | PTASes for Euclidean TSP with Unit Disk and Unit Square Neighborhoods. Sayan Bandyapadhyay, Katie Clinch, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue |
| 2025 | Packing Short Cycles. Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, William Lochet, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Kirill Simonov |
| 2025 | Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal. Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak |
| 2025 | Parameterized Approximation for Capacitated Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Vaishali Surianarayanan, Jie Xue |
| 2025 | Parameterizing the quantification of CMSO: model checking on minor-closed graph classes. Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos |
| 2025 | Parks and Recreation: Color Fault-Tolerant Spanners Made Local. Merav Parter, Asaf Petruschka, Shay Sapir, Elad Tzalik |
| 2025 | Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement. Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira, Igor Zablotchi |
| 2025 | Partitioning a Polygon Into Small Pieces. Mikkel Abrahamsen, Nichlas Langhoff Rasmussen |
| 2025 | Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances. Yu Chen, Zihan Tan |
| 2025 | Planar Graphs in Blowups of Fans. Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, David R. Wood |
| 2025 | Platforms for Efficient and Incentive-Aware Collaboration. Nika Haghtalab, Mingda Qiao, Kunhe Yang |
| 2025 | Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth. Joel Rajakumar, James D. Watson, Yi-Kai Liu |
| 2025 | Potential Hessian Ascent: The Sherrington-Kirkpatrick Model. David Jekel, Juspreet Singh Sandhu, Jonathan Shi |
| 2025 | Private Mean Estimation with Person-Level Differential Privacy. Sushant Agarwal, Gautam Kamath, Mahbod Majid, Argyris Mouzakis, Rose Silver, Jonathan R. Ullman |
| 2025 | Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 Yossi Azar, Debmalya Panigrahi |
| 2025 | Prophet Inequalities: Competing with the Top Mathieu Molina, Nicolas Gast, Patrick Loiseau, Vianney Perchet |
| 2025 | Prophet Secretary and Matching: the Significance of the Largest Item. Ziyun Chen, Zhiyi Huang, Dongchen Li, Zhihao Gavin Tang |
| 2025 | Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs. Benjamin Moseley, Aidin Niaparast, R. Ravi |
| 2025 | Quantum Locally Recoverable Codes. Louis Golowich, Venkatesan Guruswami |
| 2025 | Quartic quantum speedups for planted inference. Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush |
| 2025 | Quasi-Monte Carlo Beyond Hardy-Krause. Nikhil Bansal, Haotian Jiang |
| 2025 | Quasilinear-time eccentricities computation, and more, on median graphs. Pierre Bergé, Guillaume Ducoffe, Michel Habib |
| 2025 | Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs. Aditi Dudeja, Rashmika Goswami, Michael Saks |
| 2025 | Recognizing Sumsets is NP-Complete. Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer |
| 2025 | Relating Interleaving and Fréchet Distances via Ordered Merge Trees. Thijs Beurskens, Tim Ophelders, Bettina Speckmann, Kevin Verbeek |
| 2025 | Relative-error monotonicity testing. Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang |
| 2025 | Rényi-infinity constrained sampling with Yunbum Kook, Matthew S. Zhang |
| 2025 | Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan |
| 2025 | Solving Polynomial Equations Over Finite Fields. Holger Dell, Anselm Haak, Melvin Kallmayer, Leo Wennmann |
| 2025 | Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers. Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii, Hung Le, Alexandre Louvet, Dömötör Pálvölgyi, Csaba D. Tóth |
| 2025 | Spectral Independence Beyond Total Influence on Trees and Related Graphs. Xiaoyu Chen, Xiongxin Yang, Yitong Yin, Xinyuan Zhang |
| 2025 | Streaming Algorithms via Local Algorithms for Maximum Directed Cut. Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy |
| 2025 | Streaming and Communication Complexity of Load-Balancing via Matching Contractors. Sepehr Assadi, Aaron Bernstein, Zachary Langley, Lap Chi Lau, Robert Wang |
| 2025 | Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile Assembly Model. Florent Becker, Daniel Hader, Matthew J. Patitz |
| 2025 | Stronger adversaries grow cheaper forests: online node-weighted Steiner problems. Sander Borst, Marek Eliás, Moritz Venzin |
| 2025 | Sublinear-Round Broadcast without Trusted Setup. Andreea B. Alexandru, Julian Loss, Charalampos Papamanthou, Giorgos Tsimos, Benedikt Wagner |
| 2025 | Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decrementai reachability, and more. Adam Karczmarz, Da Wei Zheng |
| 2025 | Sumsets, 3SUM, Subset Sum: Now for Real! Nick Fischer |
| 2025 | Testing Approximate Stationarity Concepts for Piecewise Affine Functions. Lai Tian, Anthony Man-Cho So |
| 2025 | The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms. Naren Sarayu Manoj, Max Ovsiankin |
| 2025 | The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. Moses Charikar, Erik Waingarten |
| 2025 | The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints. Sven Jäger, Alexander Lindermayr, Nicole Megow |
| 2025 | The Primal Pathwidth SETH. Michael Lampis |
| 2025 | The Submodular Santa Claus Problem. Étienne Bamas, Sarah Morell, Lars Rohwedder |
| 2025 | Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval. William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, Renfei Zhou |
| 2025 | Tight Sampling Bounds for Eigenvalue Approximation. William Swartworth, David P. Woodruff |
| 2025 | Tight Streaming Lower Bounds for Deterministic Approximate Counting. Yichuan Wang |
| 2025 | Tolls for Dynamic Equilibrium Flows. Lukas Graf, Tobias Harks, Julian Schwarz |
| 2025 | Top- Gonzalo Navarro, Yakov Nekrich |
| 2025 | Tree Independence Number IV. Even-hole-free graphs. Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl |
| 2025 | Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity. Tijn de Vos, Aleksander B. G. Christiansen |
| 2025 | Triply efficient shadow tomography. Robbie King, David Gosset, Robin Kothari, Ryan Babbush |
| 2025 | Unbreakable Decomposition in Close-to-Linear Time. Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, Thatchaphol Saranurak |
| 2025 | Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits. Yuchen He, Zichun Ye, Chihao Zhang |
| 2025 | Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets. Yeyuan Chen |
| 2025 | Universal Perfect Samplers for Incremental Streams. Seth Pettie, Dingyu Wang |
| 2025 | Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization. Xingjian Bai, Christian Coester, Romain Cosson |
| 2025 | Weak coloring numbers of minor-closed graph classes. Jedrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud |