SODA A*

244 papers

YearTitle / Authors
2026#CFG and #DNNF admit FPRAS.
Kuldeep S. Meel, Alexis de Colnet
2026(Almost) Perfect Discrete Iterative Load Balancing.
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Hamed Hosseinpour, Dominik Kaaser, Peter Kling, Thomas Sauerwald
2026(α, β)-Spanners and Hybrid Spanners with Nearly Tight Bounds.
Shiri Chechik, Gur Lifshitz
2026A (2 + ε)-approximation algorithm for the general scheduling problem in quasipolynomial time.
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
2026A Better-Than-2 Approximation for the Directed Tree Augmentation Problem.
Meike Neuwohner, Olha Silina, Michael Zlatin
2026A Better-Than-5/4-Approximation for Two-Edge Connectivity.
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu
2026A Broader View on Clustering under Cluster-Aware Norm Objectives.
Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase
2026A CSP approach to Graph Sandwich Problems.
Manuel Bodirsky, Santiago Guzmán-Pro
2026A Classical Quadratic Speedup for Planted k xor.
Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer
2026A Classification of Long-Refinement Graphs for Colour Refinement.
Sandra Kiefer, T. Devini de Mel
2026A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays.
Marc Dufay, Roger Wattenhofer
2026A Few Good Choices.
Haoyu Song, Thành Nguyen, Young-San Lin
2026A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space.
Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis
2026A Near-Complete Resolution of the Exponential-Time Complexity of k-opt for the Traveling Salesman Problem.
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
2026A Post-Quantum Lower Bound for the Distributed Lovasz Local Lemma.
Sebastian Brandt, Tim Göttlicher
2026A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows.
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, Wuwei Yuan
2026A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection.
Amir Abboud, Shyan Akmal, Nick Fischer
2026A Tutte-type canonical decomposition of 3- and 4-connected graphs.
Jan Kurkofka, Tim Planken
2026A near-optimal quadratic Goldreich-Levin algorithm (extended abstract).
Jop Briët, Davi Castro-Silva
2026A parameterized linear formulation of the integer hull.
Friedrich Eisenbrand, Thomas Rothvoss
2026A quasi-polynomial bound for the minimal excluded minors for a surface.
Sarah Houdaigoui, Ken-ichi Kawarabayashi
2026A well-separated pair decomposition for low density graphs.
Joachim Gudmundsson, Sampson Wong
2026Additive Approximation Schemes for Low-Dimensional Embeddings.
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
2026Algebraic Closure of Matrix Sets Recognized by 1-VASS.
Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, James Worrell
2026Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes.
Vikrant Ashvinkumar, Mursalin Habib, Shashank Srivastava
2026Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation.
Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin, Jacobus Conradi, Ce Jin, André Nusser, Carolin Rehs
2026All-Pairs Minimum Cut using Õ(n
Yotam Kenneth-Mordoch, Robert Krauthgamer
2026An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the k-Means Problem.
Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian
2026An Optimal Density Bound for Discretized Point Patrolling.
Ahan Mishra
2026An Optimal Online Algorithm for Robust Flow Time Scheduling.
Anupam Gupta, Amit Kumar, Debmalya Panigrahi, Zhaozi Wang
2026An Unconditional Lower Bound for the Active-Set Method in Convex Quadratic Maximization.
Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis
2026An optimal algorithm for average distance in typical regular graphs.
Alexandros Eskenazis, Manor Mendel, Assaf Naor
2026Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure.
Michal Derezinski, Aaron Sidford
2026Approximate Counting of Permutation Patterns.
Omri Ben-Eliezer, Slobodan Mitrovic, Pranjal Srivastava
2026Approximate Light Spanners in Planar Graphs.
Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang
2026Approximately Dominating Sets in Elections.
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
2026Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap.
Manuel Christalla, Luise Puhlmann, Vera Traub
2026Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation.
Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior
2026Augmenting Packing Dynamic Programs to Handle (Many) Additional Budget Constraints.
Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, Andreas Wiese
2026Augmenting to 4-vertex connectivity is fixed-parameter tractable.
Johannes Carmesin, M. S. Ramanujan
2026Balanced Spanning Tree Distributions Have Separation Fairness.
Harry Chen, Kamesh Munagala, Govind S. Sankar
2026Balls and Bins and the Infinite Process with Random Deletions.
Petra Berenbrink, Tom Friedetzky, Peter Kling, Lars Nagel
2026Beating full state tomography for unentangled spectrum estimation.
Angelos Pelecanos, Xinyu Tan, Ewin Tang, John Wright
2026Better Bounds for Semi-Streaming Single-Source Shortest Paths.
Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan
2026Better Regret Rates in Bilateral Trade via Sublinear Budget Violation.
Anna Lunghi, Matteo Castiglioni, Alberto Marchesi
2026Bounding the asymptotic quantum value of all multipartite compiled non-local games.
Matilde Baroni, Dominik Leichtle, Sinisa Jankovic, Ivan Supic
2026Braiding Vineyards.
Erin W. Chambers, Christopher Fillmore, Elizabeth Stephenson, Mathijs Wintraecken
2026Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing.
Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi
2026Burling Graphs in Graphs with Large Chromatic Number.
Tara Abrishami, Marcin Brianski, James Davies, Xiying Du, Jana Masaríková, Pawel Rzazewski, Bartosz Walczak
2026Catching Rats in H-minor-free Graphs.
Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos, Sebastian Wiederrecht
2026Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case.
Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
2026Centered colorings in minor-closed graph classes.
Jedrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud
2026Circuits and Backdoors: Five Shades of the SETH.
Michael Lampis
2026Collaborative Prediction: Tractable Information Aggregation via Agreement.
Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, Mirah Shi
2026Coloring 3-Colorable Graphs with Low Threshold Rank.
Jun-Ting Hsieh
2026Coloring Graphs with Few Colors in the Streaming Model.
Sepehr Assadi, Janani Sundaresan, Helia Yazdanyar
2026Combinatorial Philosopher Inequalities.
Enze Sun, Zhihao Gavin Tang, Yifan Wang
2026Combinatorial Selection with Costly Information.
Shuchi Chawla, Dimitrios Christou, Amit Harlev, Ziv Scully
2026Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics.
Jason Gaitonde, Elchanan Mossel
2026Compatibility of Fairness and Nash Welfare under Subadditive Valuations.
Siddharth Barman, Mashbat Suzuki
2026Computational Complexity in Property Testing.
Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova
2026Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables.
Bertrand Even, Christophe Giraud, Nicolas Verzelen
2026Computing the Heaviest Disk and Related Problems.
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
2026Contextual Search in Principal-Agent Games: The Curse of Degeneracy.
Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan
2026Contract Design Beyond Hidden-Actions.
Tomer Ezra, Stefano Leonardi, Matteo Russo
2026Contract Design for Sequential Actions.
Tomer Ezra, Michal Feldman, Maya Schlesinger
2026Covering the Euclidean Plane by a Pair of Trees.
Hung Le, Lazar Milenkovic, Shay Solomon, Tianyi Zhang
2026Derandomizing Pseudopolynomial Algorithms for Subset Sum.
Timothy M. Chan
2026Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter's Threshold Barrier.
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
2026Deterministic Dynamic Edge Colouring.
Aleksander B. G. Christiansen
2026Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.
Antoine El-Hayek, Monika Henzinger, Jason Li
2026Determinization of Min-Plus Weighted Automata is Decidable.
Shaull Almagor, Guy Arbel, Sarai Sheinvald
2026Dichotomy for orderings?
Gábor Kun, Jaroslav Nesetril
2026Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More.
Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou
2026Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems.
Kobbi Nissim, Eliad Tsfadia, Chao Yan
2026Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching.
Matija Bucic, Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
2026Distributed Interactive Proofs for Planarity with Log-Star Communication.
Yuval Gil, Merav Parter
2026Distributed Quantum Advantage in Locally Checkable Labeling Problems.
Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela
2026Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries.
Hadley Black, Christopher Ye
2026Does block size matter in randomized block Krylov low-rank approximation?
Tyler Chen, Ethan N. Epperly, Raphael A. Meyer, Christopher Musco, Akash Rao
2026Downward self-reducibility in the total function polynomial hierarchy.
Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi
2026Dynamic 3D Convex Hulls Revisited and Applications.
Haitao Wang
2026Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time.
Simon Meierhans, Maximilian Probst Gutenberg
2026Dynamic Hierarchical j-Tree Decomposition and Its Applications.
Gramoz Goranci, Monika Henzinger, Peter Kiss, Ali Momeni, Gernot Zöcklein
2026Efficient Online Random Sampling via Randomness Recycling.
Thomas L. Draper, Feras A. Saad
2026Efficiently Constructing Sparse Navigable Graphs.
Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen
2026Entrywise Approximation for Matrix Inversion and Linear Systems.
Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang
2026Evasive sets, twisted varieties, and container-clique trees.
Jeck Lim, Jiaxi Nie, Ji Zeng
2026Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure.
Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi, Thomas Rothvoss, Neta Singer
2026Existence of Fair and Efficient Allocation of Indivisible Chores.
Ryoga Mahara
2026Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time.
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2026Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries.
Dominik Kempa, Tomasz Kociumaka
2026Explicit Min-wise Hash Families with Optimal Size.
Xue Chen, Shengtang Huang, Xin Li
2026Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets.
Noga Alon, Shakhar Smorodinsky
2026Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning.
Siddharth Barman, Paritosh Verma
2026Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs.
Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi
2026Faster Distributed Δ-Coloring via a Reduction to MIS.
Yann Bourreau, Sebastian Brandt, Alexandre Nolin
2026Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries.
Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri
2026Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions.
Jason Li, Connor Mowry, Satish Rao
2026Faster algorithms for packing forests in graphs and related problems.
Pavel A. Arkhipov, Vladimir Kolmogorov
2026Faster negative length shortest paths by bootstrapping hop reducers.
Yufan Huang, Peter Jin, Kent Quanrud
2026Feature Selection and Junta Testing are Statistically Equivalent.
Lorenzo Beretta, Nathaniel Harms, Caleb Koch
2026Finding sparse induced subgraphs on graphs of bounded induced matching treewidth.
Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen
2026Finite Pinwheel Scheduling: the k-Visits Problem.
Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, Euripides Markou, Aris Pagourtzis
2026From Incremental Transitive Cover to Strongly Polynomial Maximum Flow.
Daniel Dadush, James B. Orlin, Aaron Sidford, László A. Végh
2026From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction.
Aaron Bernstein, Jiale Chen
2026Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time.
Bowie Liu, Dennis Wong, Chan-Tong Lam, Sio-Kei Im
2026Halfspaces are hard to test with relative error.
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2026Hallucinating Flows for Optimal Mechanisms.
Marios Mertzanidis, Athina Terzoglou
2026Hardness of Approximation for Shortest Path with Vector Costs.
Charlie Carlson, Yury Makarychev, Ron Mosenzon
2026Helly-Type Theorems for Splitting Point Sets.
Lidor Portal, Natan Rubin
2026History-Independent Load Balancing.
Michael A. Bender, William Kuszmaul, Elaine Shi, Rose Silver
2026History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees.
Rathish Das, William Kuszmaul
2026Improved Additive Approximation Algorithms for APSP.
Ce Jin, Yael Kirkpatrick, Michal Stawarz, Virginia Vassilevska Williams
2026Improved Approximation for Ranking on General Graphs.
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu
2026Improved Maximin Share Guarantee for Additive Valuations.
Ehsan Heidari, Alireza Kaviani, Masoud Seddighin, AmirMohammad Shahrezaei
2026Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General.
David B. Shmoys, Varun Suriyanarayana, Seeun William Umboh
2026Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications.
Vinod Vaikuntanathan, Or Zamir
2026Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank Inequalities.
Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Carles Padró, Tamás Schwarcz
2026Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio
2026L
Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
2026Language Generation in the Limit: Noise, Loss, and Feedback.
Yannan Bai, Debmalya Panigrahi, Ian Zhang
2026Learning Packing and Covering from Samples.
Anupam Gupta, Marco Molinaro
2026Learning in an Echo Chamber: Online Learning with Replay Adversary.
Daniil Dmitriev, Harald Eskelund Franck, Carolin Heinzler, Amartya Sanyal
2026Likelihood of the Existence of Average Justified Representation.
Qishen Han, Biaoshuai Tao, Lirong Xia, Chengkai Zhang, Houyu Zhou
2026Listing faces of polytopes.
Nastaran Behrooznia, Sofia Brenner, Arturo Merino, Torsten Mütze, Christian Rieck, Francesco Verciani
2026Local Gibbs sampling beyond local uniformity.
Hongyang Liu, Chunyang Wang, Yitong Yin
2026Local Search for Clustering in Almost-linear Time.
Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, Pinyan Lu
2026Long Arithmetic Progressions in Sparse Subset Sums: A Computational Perspective.
Lin Chen, Yuchen Mao, Guochuan Zhang
2026Low-Sensitivity Matching via Sampling from Gibbs Distributions.
Yuichi Yoshida, Zihan Zhang
2026Lower Bounds for CSP Hierarchies Through Ideal Reduction.
Jonas Conneryd, Yassine Ghannane, Shuo Pang
2026Lower bounds for the universal TSP on the plane.
Cosmas Kravaris
2026MAX BISECTION might be harder to approximate than MAX CUT.
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2026Matroids are Equitable.
Hannaneh Akrami, Roshan Raj, László A. Végh
2026Minimum
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
2026Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension.
Kunal Dutta, Karol Pisula
2026Near-Optimal Four-Cycle Counting in Graph Streams.
Sebastian Lüderssen, Stefan Neumann, Pan Peng
2026Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment.
Pankaj K. Agarwal, Benjamin Holmgren, Alex Steiger
2026Near-linear time subhypergraph counting in bounded degeneracy hypergraphs.
Daniel Paul-Pena, C. Seshadhri
2026Nearly Optimal Bounds for Stochastic Online Sorting.
Yang Hu
2026Nearly Tight Bounds for the Online Sorting Problem.
Yossi Azar, Debmalya Panigrahi, Or Vardi
2026Nearly Tight Sample Complexity for Matroid Online Contention Resolution.
Moran Feldman, Ola Svensson, Rico Zenklusen
2026Networked Information Aggregation via Machine Learning.
Michael Kearns, Aaron Roth, Emily Ryu
2026New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs.
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2026New Oracles and Labeling Schemes for Vertex Cut Queries.
Yonggang Jiang, Merav Parter, Asaf Petruschka
2026Numerical Linear Algebra in Linear Space.
Yiping Liu, Hoai-An Nguyen, Junzhao Yang
2026On Deterministically Finding an Element of High Order Modulo a Composite.
Ziv Oznovich, Ben Lee Volk
2026On Distributed Colouring of Hyperbolic Random Graphs.
Yannic Maus, Janosch Ruff
2026On Independent Spanning Trees in Random Graphs.
Nemanja Draganic, Keith Frankston, Michael Krivelevich, Alexey Pokrovskiy, Liana Yepremyan
2026On Lines Crossing Pairwise Intersecting Convex Sets in Three Dimensions.
Natan Rubin
2026On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs.
Seth Pettie, Gábor Tardos, Bartosz Walczak
2026On sampling two spin models using the local connective constant.
Charilaos Efthymiou
2026On the Complexity of the Skolem Problem at Low Orders.
Piotr Bacik, Joël Ouaknine, James Worrell
2026On the Computation of Schrijver's Kernels.
Vincent Delecroix, Oscar Fontaine, Francis Lazarus
2026On the Quantum Chromatic Gap.
Lorenzo Ciardo
2026On the Structure of Replicable Hypothesis Testers.
Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, Sandeep Silwal
2026On the Universality of Round Elimination Fixed Points.
Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela
2026On the Usefulness of Promises.
Per Austrin, Johan Håstad, Björn Martinsson
2026On the edge expansion of random polytopes.
Asaf Ferber, Michael Krivelevich, Marcelo Sales, Wojciech Samotij
2026One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches.
Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer
2026Online 3-Taxi on General Metrics.
Christian Coester, Tze-Yang Poon
2026Online Conformal Prediction with Efficiency Guarantees.
Vaidehi Srinivas
2026Online Connectivity Augmentation.
Mohit Garg, Aditya Subramanian
2026Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs.
Yossi Azar, Shahar Lewkowicz
2026Online Learning with Limited Information in the Sliding Window Model.
Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
2026Online Orthogonal Vectors Revisited.
Karthik Gajulapalli, Alexander Golovnev, Samuel King, Sidhant Saraogi
2026Online Proportional Apportionment.
Javier Cembrano, José Correa, Svenja M. Griesbach, Victor Verdugo
2026Online Resource Allocation with Concave, Diminishing-Returns Objectives.
Kalen Patton
2026Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings.
Rajat De, Dominik Kempa
2026Optimal Rounding for Two-Stage Bipartite Matching.
Tristan Pollner, Amin Saberi, Anders Wikum
2026Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors.
Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong
2026Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets.
Riccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schäfer, Artem Tsikiridis
2026Optimal mass estimation in the conditional sampling model.
Tomer Adar, Eldar Fischer, Amit Levi
2026Optimal randomized clustering for subsets of L
Assaf Naor, Kevin Ren
2026Optimization Modulo Integer Linear-Exponential Programs.
S. Hitarth, Alessio Mansutti, Guruprerana Shabadi
2026PageRank Centrality in Directed Graphs with Bounded In-Degree.
Mikkel Thorup, Hanzhi Wang, Zhewei Wei, Mingji Yang
2026Peeling Rotten Potatoes for a Faster Approximation of Convex Cover.
Omrit Filtser, Tzalik Maimon, Ofir Yomtovyan
2026Perfect Matchings in Random Sparsifications of Dense Hypergraphs.
Jie Han, Jingwen Zhao
2026Persuasive Calibration.
Yiding Feng, Wei Tang
2026Phase transition of the Sinkhorn-Knopp algorithm.
Kun He
2026Planar Disjoint Shortest Paths is Fixed-Parameter Tractable.
Michal Pilipczuk, Giannos Stamoulis, Michal Wlodarczyk
2026Plane vs. Plane Low Degree Test.
Amey Bhangale, Silas Richelson
2026Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates.
Jon Nelson, Joel Rajakumar, Dominik Hangleiter, Michael J. Gullans
2026Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz.
Markus Bläser, Sagnik Dutta, Gorav Jindal
2026Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026
Kasper Green Larsen, Barna Saha
2026Prophet Inequality from Samples: Is the More the Merrier?
Tomer Ezra
2026Quantum Advantage via Solving Multivariate Polynomials.
Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai
2026Quantum Hamiltonian Certification.
Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, Qi Zhao
2026Quantum State Preparation with Optimal T-Count.
David Gosset, Robin Kothari, Kewen Wu
2026RETRACTED: Constructive ℓ
2026Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence.
Weiming Feng, Minji Yang
2026Rapid mixing for Gibbs states within a logical sector: a dynamical view of self-correcting quantum memories.
Thiago Bergamaschi, Reza Gheissari, Yunchao Liu
2026Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete.
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
2026Robust Equilibria in Shared Resource Allocation via Strengthening Border's Theorem.
David X. Lin, Siddhartha Banerjee, Giannis Fikioris, Éva Tardos
2026Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models.
Marc Kaufmann, Kostas Lakis, Johannes Lengler, Raghu Raman Ravi, Ulysse Schaller, Konstantin Sturm
2026Sample-efficient Replicable Median in Polynomial Time.
Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari, Samira Goudarzi, MohammadTaghi Hajiaghayi
2026Selfish, Local and Online Scheduling via Vector Fitting.
Danish Kashaev
2026Sensitivity Lower Bounds for Approximation Algorithms.
Noah Fleming, Yuichi Yoshida
2026Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems.
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
2026Short circuit walks in fixed dimension.
Alexander E. Black, Christian Nöbel, Raphael Steiner
2026Shortcuts and Transitive-Closure Spanners Approximation.
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
2026Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices.
Pravesh K. Kothari, Jeff Xu
2026Space-Efficient k-Mismatch Text Indexes.
Tomasz Kociumaka, Jakub Radoszewski
2026Space-efficient population protocols for exact majority on general graphs.
Joel Rybicki, Jakob Solnerzik, Olivier Stietel, Robin Vacus
2026Spanning Tree Embeddings Are Not Much Harder than Hierarchical Partitions.
Willem Fletcher, D. Ellis Hershkowitz
2026Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness.
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
2026Sparsifying Cayley Graphs on Every Group.
Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, Rachel Yun Zhang
2026Sparsifying Sums of Positive Semidefinite Matrices.
Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka
2026Spectral Clustering with Side Information.
Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, Weronika Wrzos-Kaminska
2026Spectral clustering in birthday paradox time.
Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska
2026Stochastic Embedding of Digraphs into DAGs.
Arnold Filtser
2026Streaming and Massively Parallel Algorithms for Euclidean Max-Cut.
Nicolas Menand, Erik Waingarten
2026Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP.
Adam Karczmarz, Wojciech Nadara, Marek Sokolowski
2026Sublinear Metric Steiner Forest via Maximal Independent Set.
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
2026Sublinear Time Low-Rank Approximation of Hankel Matrices.
Michael Kapralov, Cameron Musco, Kshiteej Sheth
2026Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries.
Vihan Shah
2026Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck.
William Kuszmaul, Jingxun Liang, Renfei Zhou
2026Temporal Exploration of Random Spanning Tree Models.
Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, Viktor Zamaraev
2026Testing forbidden order-pattern properties on hypergrids.
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma
2026The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders.
Frederick V. Qiu, S. Matthew Weinberg, Qianfan Zhang
2026The Complexity of Dynamic LZ77 is ?Θ(n
Itai Boneh, Shay Golan, Matan Kraus
2026The Directed Disjoint Paths Problem with Congestion.
Matthias Bentert, Dario Cavallaro, Amelie Heindl, Ken-ichi Kawarabayashi, Stephan Kreutzer, Johannes Schröder
2026The Division Barrier: Optimal Bounds and Structural Limits in Toom-Cook Interpolation.
Roy Nissim, Oded Schwartz, Yuval Spiizer
2026The Erdős-Pósa property for circle graphs as vertex-minors.
Rutger Campbell, Jochen Pascal Gollin, Meike Hatzel, O-joung Kwon, Rose McCarty, Sang-il Oum, Sebastian Wiederrecht
2026The Parameterised Complexity of Counting Small Sub-Hypergraphs.
Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, Philip Wellnitz
2026The Power of Matching for Online Fractional Hedonic Games.
Martin Bullinger, René Romen, Alexander Schlenga
2026Three-edge-coloring (Tait coloring) cubic graphs and nowhere-zero 4-flow for graphs on the torus.
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe
2026Tight Differentially Private PCA via Matrix Coherence.
Tommaso d'Orsi, Gleb Novikov
2026Tight Lower Bounds for Central String Queries in Compressed Space.
Dominik Kempa, Tomasz Kociumaka
2026Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization.
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi
2026Time-Biased Random Walks and Robustness of Expanders.
Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
2026Traversing regions of supersolvable hyperplane arrangements and their lattice quotients.
Sofia Brenner, Jean Cardinal, Thomas McConville, Arturo Merino, Torsten Mütze
2026Tree Embedding in High Dimensions: Dynamic and Massively Parallel.
Gramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Qihao Kong, Yi Qian, Eva Szilagyi
2026Tree covers of size 2 for the Euclidean plane.
Artur Bikeev, Andrey Kupavskii, Maxim Turevskii
2026Unbounded Error Correcting Codes.
Klim Efremenko, Or Zamir
2026Universal Connection Schedules for Reconfigurable Networking.
Shaleen Baral, Robert Kleinberg, Sylvan Martin, Henry Rogers, Tegan Wilson, Ruogu Zhang
2026Unsplittable Flow Cut Gap in Undirected Graphs.
David Alemán Espinosa, Nikhil Kumar, Joseph Poremba, F. Bruce Shepherd
2026Vizing's Theorem in Deterministic Almost-Linear Time.
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2026Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions.
Kuan Cheng, Ruiyang Wu
2026Weighted k-Server Admits an Exponentially Competitive Algorithm.
Adithya Bijoy, Ankit Mondal, Ashish Chiplunkar
2026When Contracts Get Complex: Information-Theoretic Barriers.
Paul Dütting, Michal Feldman, Yoav Gal Tzur, Aviad Rubinstein
2026You (Almost) Can't Beat Brute Force for 3-Matroid Intersection.
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
2026k-SUM Hardness Implies Treewidth-SETH.
Michael Lampis
2026ℋ-Planarity and Parametric Extensions: when Modulators Act Globally.
Fedor V. Fomin, Petr A. Golovach, Laure Morelle, Dimitrios M. Thilikos