default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID37th SODA 2026: Vancouver, BC, Canada
- Kasper Green Larsen, Barna Saha:
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026. SIAM 2026, ISBN 978-1-61197-897-1 - Cosmas Kravaris:
Lower bounds for the universal TSP on the plane. 1-9 - Tommaso d'Orsi, Gleb Novikov:
Tight Differentially Private PCA via Matrix Coherence. 10-51 - Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu:
Improved Approximation for Ranking on General Graphs. 52-84 - Mohit Garg, Aditya Subramanian:
Online Connectivity Augmentation. 85-104 - Arnold Filtser:
Stochastic Embedding of Digraphs into DAGs. 105-119 - Yuichi Yoshida, Zihan Zhang:
Low-Sensitivity Matching via Sampling from Gibbs Distributions. 120-149 - Daniel Dadush, James B. Orlin, Aaron Sidford, László A. Végh:
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow. 150-163 - Jedrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud:
Centered colorings in minor-closed graph classes. 164-184 - Vincent Delecroix, Oscar Fontaine, Francis Lazarus:
On the Computation of Schrijver's Kernels. 185-216 - Aaron Bernstein, Jiale Chen:
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction. 217-246 - Shaull Almagor, Guy Arbel, Sarai Sheinvald:
Determinization of Min-Plus Weighted Automata is Decidable. 247-257 - Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya:
Minimum s t Cuts with Fewer Cut Queries. 258-296 - Kunal Dutta
, Karol Pisula:
Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension. 297-313 - Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis:
An Unconditional Lower Bound for the Active-Set Method in Convex Quadratic Maximization. 314-327 - Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Carles Padró, Tamás Schwarcz:
Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank Inequalities. 328-354 - Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, Euripides Markou, Aris Pagourtzis:
Finite Pinwheel Scheduling: the k-Visits Problem. 355-371 - Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan:
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case. 372-387 - Sandra Kiefer, T. Devini de Mel:
A Classification of Long-Refinement Graphs for Colour Refinement. 388-407 - Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova:
Computational Complexity in Property Testing. 408-440 - Lorenzo Beretta, Nathaniel Harms, Caleb Koch:
Feature Selection and Junta Testing are Statistically Equivalent. 441-469 - Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang:
Halfspaces are hard to test with relative error. 470-492 - Bertrand Even, Christophe Giraud, Nicolas Verzelen:
Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables. 493-562 - Alexander E. Black, Christian Nöbel, Raphael Steiner:
Short circuit walks in fixed dimension. 563-573 - Joel Rybicki, Jakob Solnerzik, Olivier Stietel, Robin Vacus:
Space-efficient population protocols for exact majority on general graphs. 574-612 - Antoine El-Hayek, Monika Henzinger, Jason Li:
Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time. 613-663 - Shuchi Chawla, Dimitrios Christou, Amit Harlev, Ziv Scully:
Combinatorial Selection with Costly Information. 664-717 - Jun-Ting Hsieh:
Coloring 3-Colorable Graphs with Low Threshold Rank. 718-726 - Pankaj K. Agarwal, Benjamin Holmgren, Alex Steiger:
Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment. 727-741 - Alexandros Eskenazis, Manor Mendel, Assaf Naor:
An optimal algorithm for average distance in typical regular graphs. 742-757 - Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase:
A Broader View on Clustering under Cluster-Aware Norm Objectives. 758-793 - Yannan Bai, Debmalya Panigrahi, Ian Zhang:
Language Generation in the Limit: Noise, Loss, and Feedback. 794-816 - Klim Efremenko, Or Zamir:
Unbounded Error Correcting Codes. 817-832 - Bowie Liu, Dennis Wong, Chan-Tong Lam, Sio-Kei Im:
Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time. 833-870 - Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi, Thomas Rothvoss, Neta Singer:
Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure. 871-879 - Vikrant Ashvinkumar, Mursalin Habib, Shashank Srivastava:
Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes. 880-898 - Yuval Gil, Merav Parter:
Distributed Interactive Proofs for Planarity with Log-Star Communication. 899-924 - Michal Derezinski, Aaron Sidford:
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure. 925-938 - Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri:
Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries. 939-971 - Charilaos Efthymiou:
On sampling two spin models using the local connective constant. 972-983 - Assaf Naor, Kevin Ren:
Optimal randomized clustering for subsets of Lp when p > 2. 984-995 - Hongyang Liu, Chunyang Wang, Yitong Yin:
Local Gibbs sampling beyond local uniformity. 996-1025 - Tyler Chen, Ethan N. Epperly, Raphael A. Meyer, Christopher Musco, Akash Rao:
Does block size matter in randomized block Krylov low-rank approximation? 1026-1046 - Aleksander B. G. Christiansen:
Deterministic Dynamic Edge Colouring. 1047-1096 - Michael A. Bender, William Kuszmaul, Elaine Shi, Rose Silver:
History-Independent Load Balancing. 1097-1127 - Gramoz Goranci, Monika Henzinger, Peter Kiss, Ali Momeni, Gernot Zöcklein:
Dynamic Hierarchical j-Tree Decomposition and Its Applications. 1128-1180 - Gramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Qihao Kong, Yi Qian, Eva Szilagyi:
Tree Embedding in High Dimensions: Dynamic and Massively Parallel. 1181-1213 - Anupam Gupta, Amit Kumar, Debmalya Panigrahi, Zhaozi Wang:
An Optimal Online Algorithm for Robust Flow Time Scheduling. 1214-1238 - Anupam Gupta, Marco Molinaro:
Learning Packing and Covering from Samples. 1239-1267 - Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela:
Distributed Quantum Advantage in Locally Checkable Labeling Problems. 1268-1308 - Jon Nelson, Joel Rajakumar, Dominik Hangleiter, Michael J. Gullans:
Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates. 1309-1331 - Matilde Baroni, Dominik Leichtle, Sinisa Jankovic, Ivan Supic:
Bounding the asymptotic quantum value of all multipartite compiled non-local games. 1332-1382 - Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai:
Quantum Advantage via Solving Multivariate Polynomials. 1383-1423 - Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, Qi Zhao:
Quantum Hamiltonian Certification. 1424-1467 - Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu:
A Better-Than-5/4-Approximation for Two-Edge Connectivity. 1468-1520 - Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, Andreas Wiese:
Augmenting Packing Dynamic Programs to Handle (Many) Additional Budget Constraints. 1521-1535 - Meike Neuwohner, Olha Silina, Michael Zlatin:
A Better-Than-2 Approximation for the Directed Tree Augmentation Problem. 1536-1569 - David Alemán Espinosa, Nikhil Kumar, Joseph Poremba, F. Bruce Shepherd:
Unsplittable Flow Cut Gap in Undirected Graphs. 1570-1605 - Sanjeev Khanna, Ashwin Padaki, Erik Waingarten:
Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness. 1606-1630 - Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen:
Efficiently Constructing Sparse Navigable Graphs. 1631-1665 - Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan:
Contextual Search in Principal-Agent Games: The Curse of Degeneracy. 1666-1723 - Siddharth Barman, Mashbat Suzuki:
Compatibility of Fairness and Nash Welfare under Subadditive Valuations. 1724-1746 - Moses Charikar, Prasanna Ramakrishnan, Kangning Wang:
Approximately Dominating Sets in Elections. 1747-1760 - Qishen Han, Biaoshuai Tao, Lirong Xia, Chengkai Zhang, Houyu Zhou:
Likelihood of the Existence of Average Justified Representation. 1761-1794 - Riccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schäfer, Artem Tsikiridis:
Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets. 1795-1823 - Dominik Kempa, Tomasz Kociumaka:
Tight Lower Bounds for Central String Queries in Compressed Space. 1824-1840 - Dominik Kempa, Tomasz Kociumaka:
Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries. 1841-1858 - Itai Boneh, Shay Golan, Matan Kraus:
The Complexity of Dynamic LZ77 is ?Θ(n2/3). 1859-1872 - Tomasz Kociumaka, Jakub Radoszewski:
Space-Efficient k-Mismatch Text Indexes. 1873-1902 - Rajat De, Dominik Kempa:
Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings. 1903-1915 - Michael Lampis:
k-SUM Hardness Implies Treewidth-SETH. 1916-1944 - Michael Lampis:
Circuits and Backdoors: Five Shades of the SETH. 1945-2001 - Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, Philip Wellnitz:
The Parameterised Complexity of Counting Small Sub-Hypergraphs. 2002-2014 - Johannes Carmesin, M. S. Ramanujan:
Augmenting to 4-vertex connectivity is fixed-parameter tractable. 2015-2042 - Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen:
Finding sparse induced subgraphs on graphs of bounded induced matching treewidth. 2043-2068 - Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis:
A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space. 2069-2098 - Tomer Ezra:
Prophet Inequality from Samples: Is the More the Merrier? 2099-2112 - Tomer Ezra, Stefano Leonardi, Matteo Russo:
Contract Design Beyond Hidden-Actions. 2113-2133 - Frederick V. Qiu, S. Matthew Weinberg, Qianfan Zhang:
The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders. 2134-2162 - Martin Bullinger, René Romen, Alexander Schlenga:
The Power of Matching for Online Fractional Hedonic Games. 2163-2194 - Marios Mertzanidis, Athina Terzoglou:
Hallucinating Flows for Optimal Mechanisms. 2195-2238 - Ehsan Heidari, Alireza Kaviani, Masoud Seddighin, AmirMohammad Shahrezaei:
Improved Maximin Share Guarantee for Additive Valuations. 2239-2290 - Matthias Bentert, Dario Cavallaro, Amelie Heindl, Ken-ichi Kawarabayashi, Stephan Kreutzer, Johannes Schröder:
The Directed Disjoint Paths Problem with Congestion. 2291-2315 - Matija Bucic, Zhongtian He, Shang-En Huang, Thatchaphol Saranurak:
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching. 2316-2336 - Harry Chen, Kamesh Munagala, Govind S. Sankar:
Balanced Spanning Tree Distributions Have Separation Fairness. 2337-2402 - Manuel Bodirsky, Santiago Guzmán-Pro:
A CSP approach to Graph Sandwich Problems. 2403-2418 - Yufan Huang, Peter Jin, Kent Quanrud:
Faster negative length shortest paths by bootstrapping hop reducers. 2419-2429 - Jie Han, Jingwen Zhao:
Perfect Matchings in Random Sparsifications of Dense Hypergraphs. 2430-2454 - Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer:
A Classical Quadratic Speedup for Planted k xor. 2455-2472 - Thomas L. Draper, Feras A. Saad:
Efficient Online Random Sampling via Randomness Recycling. 2473-2511 - Xue Chen, Shengtang Huang, Xin Li:
Explicit Min-wise Hash Families with Optimal Size. 2512-2539 - Yannic Maus, Janosch Ruff:
On Distributed Colouring of Hyperbolic Random Graphs. 2540-2553 - Vinod Vaikuntanathan, Or Zamir:
Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications. 2554-2574 - Jason Gaitonde, Elchanan Mossel:
Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics. 2575-2587 - Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior:
Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation. 2588-2616 - Pravesh K. Kothari, Jeff Xu:
Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices. 2617-2632 - Omrit Filtser, Tzalik Maimon, Ofir Yomtovyan:
Peeling Rotten Potatoes for a Faster Approximation of Convex Cover. 2633-2643 - Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi:
Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing. 2644-2668 - Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang:
Approximate Light Spanners in Planar Graphs. 2669-2701 - Yossi Azar, Shahar Lewkowicz:
Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs. 2702-2725 - David B. Shmoys, Varun Suriyanarayana, Seeun William Umboh:
Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General. 2726-2742 - Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li:
Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter's Threshold Barrier. 2743-2759 - Yonggang Jiang, Merav Parter, Asaf Petruschka:
New Oracles and Labeling Schemes for Vertex Cut Queries. 2760-2791 - Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak:
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time. 2792-2823 - Jason Li, Connor Mowry, Satish Rao:
Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions. 2824-2845 - Ahan Mishra:
An Optimal Density Bound for Discretized Point Patrolling. 2846-2875 - Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, Viktor Zamaraev:
Temporal Exploration of Random Spanning Tree Models. 2876-2887 - Lidor Portal, Natan Rubin:
Helly-Type Theorems for Splitting Point Sets. 2888-2902 - Seth Pettie, Gábor Tardos, Bartosz Walczak:
On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs. 2903-2927 - Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester:
Time-Biased Random Walks and Robustness of Expanders. 2928-2941 - Jan Kurkofka, Tim Planken:
A Tutte-type canonical decomposition of 3- and 4-connected graphs. 2942-3021 - Asaf Ferber, Michael Krivelevich, Marcelo Sales, Wojciech Samotij:
On the edge expansion of random polytopes. 3022-3035 - (Withdrawn) RETRACTED: Constructive ℓ2-Discrepancy Minimization with Additive Deviations. 3036-3056
- Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska:
Spectral clustering in birthday paradox time. 3057-3071 - Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma:
Testing forbidden order-pattern properties on hypergrids. 3072-3100 - Nicolas Menand, Erik Waingarten:
Streaming and Massively Parallel Algorithms for Euclidean Max-Cut. 3101-3161 - Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer:
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches. 3162-3200 - Michael Kapralov, Cameron Musco, Kshiteej Sheth:
Sublinear Time Low-Rank Approximation of Hankel Matrices. 3201-3248 - Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou:
Online Learning with Limited Information in the Sliding Window Model. 3249-3297 - Sebastian Brandt, Tim Göttlicher:
A Post-Quantum Lower Bound for the Distributed Lovasz Local Lemma. 3298-3312 - Angelos Pelecanos, Xinyu Tan, Ewin Tang, John Wright:
Beating full state tomography for unentangled spectrum estimation. 3313-3363 - Lorenzo Ciardo:
On the Quantum Chromatic Gap. 3364-3377 - David Gosset, Robin Kothari, Kewen Wu:
Quantum State Preparation with Optimal T-Count. 3378-3406 - Thiago Bergamaschi, Reza Gheissari, Yunchao Liu:
Rapid mixing for Gibbs states within a logical sector: a dynamical view of self-correcting quantum memories. 3407-3422 - Kuan Cheng, Ruiyang Wu:
Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions. 3423-3458 - Artur Bikeev, Andrey Kupavskii, Maxim Turevskii:
Tree covers of size 2 for the Euclidean plane. 3459-3471 - Hung Le, Lazar Milenkovic, Shay Solomon, Tianyi Zhang:
Covering the Euclidean Plane by a Pair of Trees. 3472-3497 - Alexander Armbruster, Lars Rohwedder, Andreas Wiese:
A (2 + ε)-approximation algorithm for the general scheduling problem in quasipolynomial time. 3498-3510 - Shiri Chechik, Gur Lifshitz:
(α, β)-Spanners and Hybrid Spanners with Nearly Tight Bounds. 3511-3535 - Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai:
Shortcuts and Transitive-Closure Spanners Approximation. 3536-3561 - Amir Abboud, Shyan Akmal, Nick Fischer:
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection. 3562-3599 - Timothy M. Chan:
Derandomizing Pseudopolynomial Algorithms for Subset Sum. 3600-3610 - Lin Chen, Yuchen Mao, Guochuan Zhang:
Long Arithmetic Progressions in Sparse Subset Sums: A Computational Perspective. 3611-3638 - Ce Jin, Yael Kirkpatrick, Michal Stawarz, Virginia Vassilevska Williams:
Improved Additive Approximation Algorithms for APSP. 3639-3651 - Daniel Paul-Pena, C. Seshadhri:
Near-linear time subhypergraph counting in bounded degeneracy hypergraphs. 3652-3687 - Joachim Gudmundsson, Sampson Wong:
A well-separated pair decomposition for low density graphs. 3688-3723 - Haitao Wang:
Dynamic 3D Convex Hulls Revisited and Applications. 3724-3744 - Pankaj K. Agarwal, Esther Ezra, Micha Sharir:
Computing the Heaviest Disk and Related Problems. 3745-3759 - William Kuszmaul, Jingxun Liang, Renfei Zhou:
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck. 3760-3804 - Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, Wuwei Yuan:
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows. 3805-3819 - Mikkel Thorup, Hanzhi Wang, Zhewei Wei, Mingji Yang:
PageRank Centrality in Directed Graphs with Bounded In-Degree. 3820-3840 - Danish Kashaev:
Selfish, Local and Online Scheduling via Vector Fitting. 3841-3871 - Enze Sun, Zhihao Gavin Tang, Yifan Wang:
Combinatorial Philosopher Inequalities. 3872-3904 - Charlie Carlson, Yury Makarychev, Ron Mosenzon:
Hardness of Approximation for Shortest Path with Vector Costs. 3905-3935 - Marc Dufay, Roger Wattenhofer:
A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays. 3936-3964 - Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný:
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. 3965-3977 - Tara Abrishami, Marcin Brianski, James Davies, Xiying Du, Jana Masaríková, Pawel Rzazewski, Bartosz Walczak:
Burling Graphs in Graphs with Large Chromatic Number. 3978-3998 - Rathish Das, William Kuszmaul:
History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees. 3999-4022 - Pavel A. Arkhipov, Vladimir Kolmogorov:
Faster algorithms for packing forests in graphs and related problems. 4023-4042 - Noah Fleming, Yuichi Yoshida:
Sensitivity Lower Bounds for Approximation Algorithms. 4043-4076 - Yotam Kenneth-Mordoch, Robert Krauthgamer:
All-Pairs Minimum Cut using Õ(n7/4) Cut Queries. 4077-4095 - Nemanja Draganic, Keith Frankston, Michael Krivelevich, Alexey Pokrovskiy, Liana Yepremyan:
On Independent Spanning Trees in Random Graphs. 4096-4104 - Tomer Adar, Eldar Fischer, Amit Levi:
Optimal mass estimation in the conditional sampling model. 4105-4174 - Gábor Kun, Jaroslav Nesetril:
Dichotomy for orderings? 4175-4187 - Adithya Bijoy, Ankit Mondal, Ashish Chiplunkar:
Weighted k-Server Admits an Exponentially Competitive Algorithm. 4188-4208 - Petra Berenbrink, Tom Friedetzky, Peter Kling, Lars Nagel:
Balls and Bins and the Infinite Process with Random Deletions. 4209-4223 - Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Hamed Hosseinpour, Dominik Kaaser, Peter Kling, Thomas Sauerwald:
(Almost) Perfect Discrete Iterative Load Balancing. 4224-4237 - Kun He:
Phase transition of the Sinkhorn-Knopp algorithm. 4238-4284 - Sebastian Lüderssen, Stefan Neumann, Pan Peng:
Near-Optimal Four-Cycle Counting in Graph Streams. 4285-4326 - Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, Weronika Wrzos-Kaminska:
Spectral Clustering with Side Information. 4327-4341 - Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou:
Lp Sampling in Distributed Data Streams with Applications to Adversarial Robustness. 4342-4409 - Hadley Black, Christopher Ye:
Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries. 4410-4480 - Yann Bourreau, Sebastian Brandt, Alexandre Nolin:
Faster Distributed Δ-Coloring via a Reduction to MIS. 4481-4500 - Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong:
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors. 4501-4559 - Friedrich Eisenbrand, Thomas Rothvoss:
A parameterized linear formulation of the integer hull. 4560-4571 - Michal Pilipczuk, Giannos Stamoulis, Michal Wlodarczyk:
Planar Disjoint Shortest Paths is Fixed-Parameter Tractable. 4572-4583 - Fedor V. Fomin, Petr A. Golovach, Laure Morelle, Dimitrios M. Thilikos:
ℋ-Planarity and Parametric Extensions: when Modulators Act Globally. 4584-4601 - Sarah Houdaigoui, Ken-ichi Kawarabayashi:
A quasi-polynomial bound for the minimal excluded minors for a surface. 4602-4627 - Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi:
Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization. 4628-4643 - Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos, Sebastian Wiederrecht:
Catching Rats in H-minor-free Graphs. 4644-4659 - Yiding Feng, Wei Tang:
Persuasive Calibration. 4660-4691 - Moran Feldman, Ola Svensson, Rico Zenklusen:
Nearly Tight Sample Complexity for Matroid Online Contention Resolution. 4692-4711 - Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, Mirah Shi:
Collaborative Prediction: Tractable Information Aggregation via Agreement. 4712-4798 - Michael Kearns, Aaron Roth, Emily Ryu:
Networked Information Aggregation via Machine Learning. 4799-4845 - Javier Cembrano, José Correa, Svenja M. Griesbach, Victor Verdugo:
Online Proportional Apportionment. 4846-4860 - Haoyu Song, Thành Nguyen, Young-San Lin:
A Few Good Choices. 4861-4874 - Natan Rubin:
On Lines Crossing Pairwise Intersecting Convex Sets in Three Dimensions. 4875-4893 - Weiming Feng, Minji Yang:
Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence. 4894-4929 - Rutger Campbell, Jochen Pascal Gollin, Meike Hatzel, O-joung Kwon, Rose McCarty, Sang-il Oum, Sebastian Wiederrecht:
The Erdős-Pósa property for circle graphs as vertex-minors. 4930-4952 - Sofia Brenner, Jean Cardinal, Thomas McConville, Arturo Merino, Torsten Mütze:
Traversing regions of supersolvable hyperplane arrangements and their lattice quotients. 4953-4968 - Yang Hu:
Nearly Optimal Bounds for Stochastic Online Sorting. 4969-4995 - Shaleen Baral, Robert Kleinberg, Sylvan Martin, Henry Rogers, Tegan Wilson, Ruogu Zhang:
Universal Connection Schedules for Reconfigurable Networking. 4996-5026 - Vihan Shah:
Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries. 5027-5065 - Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela:
On the Universality of Round Elimination Fixed Points. 5066-5092 - Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan:
Better Bounds for Semi-Streaming Single-Source Shortest Paths. 5093-5116 - Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi:
Downward self-reducibility in the total function polynomial hierarchy. 5117-5150 - Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai:
You (Almost) Can't Beat Brute Force for 3-Matroid Intersection. 5151-5171 - Amey Bhangale, Silas Richelson:
Plane vs. Plane Low Degree Test. 5172-5198 - Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang:
Entrywise Approximation for Matrix Inversion and Linear Systems. 5199-5210 - Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, James Worrell:
Algebraic Closure of Matrix Sets Recognized by 1-VASS. 5211-5240 - Roy Nissim, Oded Schwartz, Yuval Spiizer:
The Division Barrier: Optimal Bounds and Structural Limits in Toom-Cook Interpolation. 5241-5254 - Piotr Bacik, Joël Ouaknine, James Worrell:
On the Complexity of the Skolem Problem at Low Orders. 5255-5269 - S. Hitarth, Alessio Mansutti, Guruprerana Shabadi:
Optimization Modulo Integer Linear-Exponential Programs. 5270-5343 - Willem Fletcher, D. Ellis Hershkowitz:
Spanning Tree Embeddings Are Not Much Harder than Hierarchical Partitions. 5344-5373 - Manuel Christalla, Luise Puhlmann, Vera Traub:
Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap. 5374-5439 - Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins:
Additive Approximation Schemes for Low-Dimensional Embeddings. 5440-5488 - Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian:
An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the k-Means Problem. 5489-5533 - Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
MAX BISECTION might be harder to approximate than MAX CUT. 5534-5557 - Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang:
Vizing's Theorem in Deterministic Almost-Linear Time. 5558-5585 - Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi:
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs. 5586-5623 - Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin, Jacobus Conradi, Ce Jin, André Nusser, Carolin Rehs:
Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation. 5624-5640 - Karthik Gajulapalli, Alexander Golovnev, Samuel King, Sidhant Saraogi:
Online Orthogonal Vectors Revisited. 5641-5668 - Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak:
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems. 5669-5687 - Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou:
Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More. 5688-5728 - Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari, Samira Goudarzi, MohammadTaghi Hajiaghayi:
Sample-efficient Replicable Median in Polynomial Time. 5729-5770 - Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, Sandeep Silwal:
On the Structure of Replicable Hypothesis Testers. 5771-5823 - Kobbi Nissim, Eliad Tsfadia, Chao Yan:
Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems. 5824-5842 - Hannaneh Akrami, Roshan Raj, László A. Végh:
Matroids are Equitable. 5843-5860 - Sophia Heimann, Hung P. Hoang, Stefan Hougardy:
A Near-Complete Resolution of the Exponential-Time Complexity of k-opt for the Traveling Salesman Problem. 5861-5885 - Tristan Pollner, Amin Saberi, Anders Wikum:
Optimal Rounding for Two-Stage Bipartite Matching. 5886-5913 - Omri Ben-Eliezer, Slobodan Mitrovic, Pranjal Srivastava:
Approximate Counting of Permutation Patterns. 5914-5940 - Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian:
Sublinear Metric Steiner Forest via Maximal Independent Set. 5941-5959 - Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, Pinyan Lu:
Local Search for Clustering in Almost-linear Time. 5960-5977 - Kuldeep S. Meel, Alexis de Colnet:
#CFG and #DNNF admit FPRAS. 5978-6010 - Adam Karczmarz, Wojciech Nadara, Marek Sokolowski:
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP. 6011-6028 - Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, Rachel Yun Zhang:
Sparsifying Cayley Graphs on Every Group. 6029-6041 - Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka:
Sparsifying Sums of Positive Semidefinite Matrices. 6042-6064 - Sepehr Assadi, Janani Sundaresan, Helia Yazdanyar:
Coloring Graphs with Few Colors in the Streaming Model. 6065-6132 - Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe:
Three-edge-coloring (Tait coloring) cubic graphs and nowhere-zero 4-flow for graphs on the torus. 6133-6165 - Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye:
Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete. 6166-6183 - Simon Meierhans, Maximilian Probst Gutenberg:
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time. 6184-6198 - Jeck Lim, Jiaxi Nie, Ji Zeng:
Evasive sets, twisted varieties, and container-clique trees. 6199-6211 - Nastaran Behrooznia, Sofia Brenner, Arturo Merino, Torsten Mütze, Christian Rieck, Francesco Verciani:
Listing faces of polytopes. 6212-6222 - Noga Alon, Shakhar Smorodinsky:
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets. 6223-6232 - Jop Briët, Davi Castro-Silva:
A near-optimal quadratic Goldreich-Levin algorithm (extended abstract). 6233-6239 - Erin W. Chambers, Christopher Fillmore, Elizabeth Stephenson, Mathijs Wintraecken:
Braiding Vineyards. 6240-6263 - Marc Kaufmann, Kostas Lakis, Johannes Lengler, Raghu Raman Ravi, Ulysse Schaller, Konstantin Sturm:
Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models. 6264-6307 - Markus Bläser, Sagnik Dutta, Gorav Jindal:
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz. 6308-6331 - Per Austrin, Johan Håstad, Björn Martinsson:
On the Usefulness of Promises. 6332-6378 - Ziv Oznovich, Ben Lee Volk:
On Deterministically Finding an Element of High Order Modulo a Composite. 6379-6391 - Yiping Liu, Hoai-An Nguyen, Junzhao Yang:
Numerical Linear Algebra in Linear Space. 6392-6435 - Jonas Conneryd, Yassine Ghannane, Shuo Pang:
Lower Bounds for CSP Hierarchies Through Ideal Reduction. 6436-6463 - Paul Dütting, Michal Feldman, Yoav Gal Tzur, Aviad Rubinstein:
When Contracts Get Complex: Information-Theoretic Barriers. 6464-6493 - Anna Lunghi, Matteo Castiglioni, Alberto Marchesi:
Better Regret Rates in Bilateral Trade via Sublinear Budget Violation. 6494-6536 - Tomer Ezra, Michal Feldman, Maya Schlesinger:
Contract Design for Sequential Actions. 6537-6570 - David X. Lin, Siddhartha Banerjee, Giannis Fikioris, Éva Tardos:
Robust Equilibria in Shared Resource Allocation via Strengthening Border's Theorem. 6571-6612 - Siddharth Barman, Paritosh Verma:
Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning. 6613-6641 - Yossi Azar, Debmalya Panigrahi, Or Vardi:
Nearly Tight Bounds for the Online Sorting Problem. 6642-6658 - Christian Coester, Tze-Yang Poon:
Online 3-Taxi on General Metrics. 6659-6673 - Daniil Dmitriev, Harald Eskelund Franck, Carolin Heinzler, Amartya Sanyal:
Learning in an Echo Chamber: Online Learning with Replay Adversary. 6674-6695 - Vaidehi Srinivas:
Online Conformal Prediction with Efficiency Guarantees. 6696-6726 - Kalen Patton:
Online Resource Allocation with Concave, Diminishing-Returns Objectives. 6727-6741 - Ryoga Mahara:
Existence of Fair and Efficient Allocation of Indivisible Chores. 6742-6766 - Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio:
Is nasty noise actually harder than malicious noise? 6767-6787
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-03-12 22:58 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
