| 2025 | A Fast Coloring Oracle for Average Case Hypergraphs. Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber |
| 2025 | A Polynomial-Time Approximation Algorithm for Complete Interval Minors. Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé |
| 2025 | A Randomized Rounding Approach for DAG Edge Deletion. Sina Kalantarzadeh, Nathan Klein, Victor Reis |
| 2025 | A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms. Igor Shinkar, Harsimran Singh |
| 2025 | Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs. Zhangsong Li |
| 2025 | Approximating Maximum Cut on Interval Graphs and Split Graphs Beyond Goemans-Williamson. Jungho Ahn, Ian DeHaan, Eun Jung Kim, Euiwoong Lee |
| 2025 | Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics. Kinter Ren, Mohammad R. Salavatipour |
| 2025 | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2025, Berkeley, CA, USA, August 11-13, 2025 Alina Ene, Eshan Chattopadhyay |
| 2025 | Avoiding Range via Turan-Type Bounds. Neha Kuntewar, Jayalal Sarma |
| 2025 | Bit-Fixing Extractors for Almost-Logarithmic Entropy. Dean Doron, Ori Fridman |
| 2025 | Budget and Profit Approximations for Spanning Tree Interdiction. Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov |
| 2025 | Consumable Data via Quantum Communication. Dar Gilboa, Siddhartha Jain, Jarrod R. McClean |
| 2025 | Covering Simple Orthogonal Polygons with Rectangles. Aniket Basu Roy |
| 2025 | Covering a Few Submodular Constraints and Applications. Tanvi Bajpai, Chandra Chekuri, Pooja Kulkarni |
| 2025 | Density Frankl-Rödl on the Sphere. Venkatesan Guruswami, Shilun Li |
| 2025 | Directed Buy-At-Bulk Spanners. Elena Grigorescu, Nithish Kumar, Young-San Lin |
| 2025 | Dual Charging for Half-Integral TSP. Nathan Klein, Mehrshad Taziki |
| 2025 | Efficient Parallel Ising Samplers via Localization Schemes. Xiaoyu Chen, Hongyang Liu, Yitong Yin, Xinyuan Zhang |
| 2025 | Efficient Polynomial Identity Testing over Nonassociative Algebras. Partha Mukhopadhyay, C. Ramya, Pratik Shastri |
| 2025 | Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications. Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan |
| 2025 | Equality Is Far Weaker Than Constant-Cost Communication. Mika Göös, Nathaniel Harms, Artur Riazanov |
| 2025 | Fooling Near-Maximal Decision Trees. William M. Hoza, Zelin Lv |
| 2025 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2025 | Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio. Zeyu Guo, Chaoping Xing, Chen Yuan, Zihan Zhang |
| 2025 | Implications of Better PRGs for Permutation Branching Programs. Dean Doron, William M. Hoza |
| 2025 | Improved Approximation Algorithms for the EPR Hamiltonian. Nathan Ju, Ansh Nagda |
| 2025 | Improved Approximation Guarantees for Advertisement Placement. Waldo Gálvez, Roberto Oliva, Victor Verdugo |
| 2025 | Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints. Sayan Bandyapadhyay, Tianzhi Chen |
| 2025 | Improved Lower Bounds on Multiflow-Multicut Gaps. Sina Kalantarzadeh, Nikhil Kumar |
| 2025 | Improved Mixing of Critical Hardcore Model. Zongchen Chen, Tianhui Jiang |
| 2025 | Lifting to Randomized Parity Decision Trees. Farzan Byramji, Russell Impagliazzo |
| 2025 | List-Recovery of Random Linear Codes over Small Fields. Dean Doron, Jonathan Mosheiff, Nicolas Resch, João Ribeiro |
| 2025 | Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them. Clément L. Canonne, Yun Li, Seeun William Umboh |
| 2025 | Low-Degree Polynomials Are Good Extractors. Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, João Ribeiro |
| 2025 | Max-Cut with Multiple Cardinality Constraints. Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian |
| 2025 | Maximum And- vs. Even-SAT. Tamio-Vesa Nakajima, Stanislav Zivný |
| 2025 | Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT. Aditya Anand, Euiwoong Lee, Davide Mazzali, Amatya Sharma |
| 2025 | Multipass Linear Sketches for Geometric LP-Type Problems. N. Efe Çekirge, William Gay, David P. Woodruff |
| 2025 | Near-Optimal List-Recovery of Linear Code Families. Ray Li, Nikhil Shagrithaya |
| 2025 | New Constructions of Pseudorandom Codes. Surendra Ghentiyala, Venkatesan Guruswami |
| 2025 | New Statistical and Computational Results for Learning Junta Distributions. Lorenzo Beretta |
| 2025 | Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS. Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior |
| 2025 | On Finding Randomly Planted Cliques in Arbitrary Graphs. Francesco Agrimonti, Marco Bressan, Tommaso d'Orsi |
| 2025 | On Sums of INW Pseudorandom Generators. William M. Hoza, Zelin Lv |
| 2025 | On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems. Ian DeHaan, Neng Huang, Euiwoong Lee |
| 2025 | On the Spectral Expansion of Monotone Subsets of the Hypercube. Yumou Fei, Renato Ferreira Pinto Jr. |
| 2025 | Optimal Competitive Ratio for Optimization Problems with Congestion Effects. Miriam Fischer, Dario Paccagnan, Cosimo Vinci |
| 2025 | Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields. Fatemeh Ghasemi, Gal Gross, Swastik Kopparty |
| 2025 | Pseudorandomness of Expander Walks via Fourier Analysis on Groups. Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy |
| 2025 | QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More. Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman |
| 2025 | Quantum Property Testing in Sparse Directed Graphs. Simon Apers, Frédéric Magniez, Sayantan Sen, Dániel Szabó |
| 2025 | Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree. Xiaoyu Chen, Weiming Feng |
| 2025 | Relational Approximations for Subspace Primitives. Xiang Liu, Kasturi R. Varadarajan |
| 2025 | Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication. Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan |
| 2025 | Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions. Adar Hadad, Moni Naor |
| 2025 | Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT. Eren C. Kizildag |
| 2025 | Simplifying Armoni's PRG. Ben Chen, Amnon Ta-Shma |
| 2025 | Sink-Free Orientations: A Local Sampler with Applications. Konrad Anand, Graham Freifeld, Heng Guo, Chunyang Wang, Jiaheng Wang |
| 2025 | Solving Linear Programs with Differential Privacy. Alina Ene, Huy Le Nguyen, Ta Duy Nguyen, Adrian Vladu |
| 2025 | Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs. Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil P. Vadhan, Jiyu Zhang |
| 2025 | Spectral Refutations of Semirandom k-LIN over Larger Fields. Nicholas Kocurek, Peter Manohar |
| 2025 | Streaming Algorithms for Network Design. Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, Ali Vakilian |
| 2025 | Structured-Seed Local Pseudorandom Generators and Their Applications. Benny Applebaum, Dung Bui, Geoffroy Couteau, Nikolas Melissaris |
| 2025 | Sublinear Space Graph Algorithms in the Continual Release Model. Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, Felix Zhou |
| 2025 | Tarski Lower Bounds from Multi-Dimensional Herringbones. Simina Brânzei, Reed C. Phillips, Nicholas J. Recker |
| 2025 | Testing Isomorphism of Boolean Functions over Finite Abelian Groups. Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, Manmatha Roy |
| 2025 | Testing Tensor Products of Algebraic Codes. Sumegha Garg, Madhu Sudan, Gabriel Wu |
| 2025 | Time Lower Bounds for the Metropolis Process and Simulated Annealing. Zongchen Chen, Dan Mikulincer, Daniel Reichman, Alexander S. Wein |
| 2025 | Triangles Improve 0.878 Approximation for Maxcut. Fredie George, Anand Louis, Rameesh Paul |
| 2025 | What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks? Dariusz R. Kowalski, Piotr Krysta, Shay Kutten |