default search action
33rd SODA 2022: Virtual Conference / Alexandria, VA, USA
- Joseph (Seffi) Naor, Niv Buchbinder:
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022. SIAM 2022, ISBN 978-1-61197-707-3 - Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, Billy Jin:
Online Nash Social Welfare Maximization with Predictions. 1-19 - Sara Ahmadian, Hossein Esfandiari, Vahab S. Mirrokni, Binghui Peng:
Robust Load Balancing with Machine Learned Advice. 20-34 - Yossi Azar, Debmalya Panigrahi, Noam Touitou:
Online Graph Algorithms with Predictions. 35-66 - Nikhil Bansal, Christian Coester
, Ravi Kumar, Manish Purohit, Erik Vee:
Learning-Augmented Weighted Paging. 67-89 - Miriam Schlöter, Martin Skutella, Khai Van Tran:
A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method. 90-102 - Telikepalli Kavitha, Tamás Király, Jannik Matuschke
The popular assignment problem: when cardinality is more important than popularity. 103-123 - Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye:
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time. 124-153 - Adam Karczmarz:
Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths. 154-172 - Joachim Gudmundsson, Sampson Wong:
Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance. 173-189 - Timothy M. Chan, Da Wei Zheng
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees. 190-210 - Santiago Aranguri, Hsien-Chih Chang, Dylan Fridman:
Untangling Planar Graphs and Curves by Staying Positive. 211-225 - Mitchell Black, William Maxwell, Amir Nayyeri, Eli Winkelman:
Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology. 226-251 - Yossi Azar, Stefano Leonardi, Noam Touitou:
Distortion-Oblivious Algorithms for Minimizing Flow Time. 252-274 - Lin Chen
Tight running times for minimum <italic>ℓq</italic>-norm load balancing: beyond exponential dependencies on 1/<italic>∊</italic>. 275-315 - Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski, Yihao Zhang:
On the Hardness of Scheduling With Non-Uniform Communication Delays. 316-328 - Max Klimm, Guillaume Sagnol, Martin Skutella, Khai Van Tran:
Competitive Strategies for Symmetric Rendezvous on the Line. 329-347 - Kim-Manuel Klein, Janina Reuter:
Collapsing the Tower - On the Complexity of Multistage Stochastic IPs. 348-358 - Manuel Cáceres
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time. 359-376 - Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon:
Directed Tangle Tree-Decompositions and Applications. 377-405 - Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov:
Algorithmic Extensions of Dirac's Theorem. 406-416 - Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster:
Counting Homomorphic Cycles in Degenerate Graphs. 417-430 - Jacob Focke, Dániel Marx, Pawel Rzazewski:
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. 431-458 - Monika Henzinger, Andrea Lincoln
The Complexity of Average-Case Dynamic Subgraph Counting. 459-498 - Matthew Jenssen, Aditya Potukuchi, Will Perkins:
Approximately counting independent sets in bipartite graphs via graph containers. 499-516 - Karl Bringmann, Anne Driemel
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. 517-550 - Shiri Chechik, Tianyi Zhang:
Nearly 2-Approximate Distance Oracles in Subquadratic Time. 551-580 - Surender Baswana, Abhyuday Pandey
Sensitivity Oracles for All-Pairs Mincuts. 581-609 - Joachim Gudmundsson, Martin P. Seybold
A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures. 610-626 - Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian:
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space. 627-669 - Bartlomiej Dudek
Streaming Regular Expression Membership and Pattern Matching. 670-694 - Piotr Indyk, Shyam Narayanan, David P. Woodruff:
Frequency Estimation with One-Sided Error. 695-707 - Sepehr Assadi:
A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching. 708-742 - Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Average-Case Subset Balancing Problems. 743-778 - Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. 779-821 - Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, Jean Bernoulli Ravelomanana:
The Sparse Parity Matrix. 822-833 - Dmitriy Kunisky, Jonathan Niles-Weed:
Strong recovery of geometric planted matchings. 834-876 - Aditya Jayaprakash, Mohammad R. Salavatipour:
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension. 877-893 - Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, Andreas Wiese:
A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. 894-905 - Fabrizio Grandoni, Tobias Mömke, Andreas Wiese:
Unsplittable Flow on a Path: The Game!. 906-926 - Venkatesan Guruswami, Sai Sandeep:
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. 927-944 - Edin Husic
On complete classes of valuated matroids. 945-962 - Paul Jungeblut
A Sublinear Bound on the Page Number of Upward Planar Graphs. 963-978 - Per Austrin, Kilian Risse:
Perfect Matching in Random Graphs is as Hard as Tseitin. 979-1012 - Sumanta Ghosh, Rohit Gurjar, Roshan Raj:
A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision. 1013-1035 - Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé:
Twin-width VI: the lens of contraction sequences. 1036-1056 - Lorenzo Ciardo, Stanislav Zivný:
CLAP: A New Algorithm for Promise CSPs. 1057-1068 - Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett:
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games. 1069-1128 - Albert Atserias, Víctor Dalmau:
Promise Constraint Satisfaction and Width. 1129-1153 - Jun-Ting Hsieh, Pravesh K. Kothari:
Algorithmic Thresholds for Refuting Random Polynomial Systems. 1154-1203 - Libor Barto, Marcin Kozik:
Combinatorial Gap Theorem and Reductions between Promise CSPs. 1204-1220 - Jiashuo Jiang, Will Ma, Jiawei Zhang:
Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack. 1221-1246 - Haim Kaplan, David Naori, Danny Raz:
Online Weighted Matching with a Sample. 1247-1272 - C. J. Argue, Anupam Gupta
Robust Secretary and Prophet Algorithms for Packing Integer Programs. 1273-1297 - Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser:
Single-Sample Prophet Inequalities via Greedy-Ordered Selection. 1298-1325 - Shimon Kogan, Merav Parter:
New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier. 1326-1341 - Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams. 1342-1355 - Anupam Gupta
Online Discrepancy with Recourse for Vectors and Graphs. 1356-1383 - Manuel Lafond:
Recognizing <italic>k</italic>-leaf powers in polynomial time, for constant <italic>k</italic>. 1384-1410 - Daniel Neuen:
Isomorphism Testing for Graphs Excluding Small Topological Subgraphs. 1411-1434 - Shucheng Chi, Ran Duan, Tianle Xie:
Faster Algorithms for Bounded-Difference Min-Plus Product. 1435-1447 - Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Pawel Rzazewski:
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws. 1448-1470 - Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick:
Algorithmic trade-offs for girth approximation in undirected graphs. 1471-1492 - Vincent Cohen-Addad, Karthik C. S.
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics. 1493-1530 - Chandra Chekuri, Kent Quanrud, Manuel R. Torres:
Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. 1531-1555 - Vincent Cohen-Addad, Anupam Gupta
An Improved Local Search Algorithm for k-Median. 1556-1612 - Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, Peilin Zhong:
Massively Parallel and Dynamic Algorithms for Minimum Size Clustering. 1613-1660 - Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu:
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. 1661-1678 - Mehdi Soleimanifar, John Wright:
Testing matrix product states. 1679-1701 - Sabyasachi Basu
The complexity of testing all properties of planar graphs, and the role of isomorphism. 1702-1714 - Xi Chen, Shyamal Patel:
Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning. 1715-1743 - David G. Harris:
Deterministic algorithms for the Lovász Local Lemma: simpler, more general, and more parallel. 1744-1779 - Jian Li, Daogao Liu:
Multi-token Markov Game with Switching Costs. 1780-1807 - Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan:
Stochastic Vertex Cover with Few Queries. 1808-1846 - Dimitrios Los
Balanced Allocations: Caching and Packing, Twinning and Thinning. 1847-1874 - Benjamin Aram Berendsohn
Splay trees on trees. 1875-1900 - Haim Kaplan, Robert E. Tarjan, Or Zamir, Uri Zwick:
Simulating a stack using queues. 1901-1924 - Soh Kumabe, Yuichi Yoshida:
Average Sensitivity of Dynamic Programming. 1925-1961 - Bryce Sandlund, Lingyi Zhang:
Selectable Heaps and Optimal Lazy Search Trees. 1962-1975 - Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan
Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent. 1976-2004 - Daniel Lokshtanov, Fahad Panolan
Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract). 2005-2031 - Sukanya Pandey
Planar Multiway Cut with Terminals on Few Faces. 2032-2063 - Sayan Bandyapadhyay, William Lochet
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H<-Minor-Free Graphs. 2063-2084 - Dániel Marx, Pranabendu Misra, Daniel Neuen, Prafullkumar Tale:
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs. 2085-2127 - Jean Cardinal, Arturo Merino, Torsten Mütze:
Efficient generation of elimination trees and graph associahedra. 2128-2140 - Dingding Dong
Enumerating k-SAT functions. 2141-2184 - Michael Simkin, Zur Luria:
A Lower Bound for the n-queens Problem. 2185-2197 - Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda:
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. 2198-2207 - Calvin Beideman
Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k. 2208-2228 - Kamesh Munagala, Yiheng Shen, Kangning Wang, Zhiyi Wang:
Approximate Core for Committee Selection via Multilinear Extension and Market Clearing. 2229-2252 - Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis:
Computational Hardness of the Hylland-Zeckhauser Scheme. 2253-2268 - Jugal Garg, Yixin Tao, László A. Végh
Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets. 2269-2284 - Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta:
Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. 2285-2302 - Lorenzo Beretta, Jakub Tetek:
Better Sum Estimation via Weighted Sampling. 2303-2338 - Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Approximating Sumset Size. 2339-2357 - David P. Woodruff, Taisuke Yasuda
Improved Algorithms for Low Rank Approximation from Sparsity. 2358-2403 - Talya Eden, Saleet Mossel, Dana Ron:
Approximating the Arboricity in Sublinear Time. 2404-2425 - Aviv Bick, Gillat Kol, Rotem Oshman:
Distributed Zero-Knowledge Proofs Over Networks. 2426-2458 - Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi:
Optimal Oblivious Parallel RAM. 2459-2521 - Giuseppe Persiano
Limits of Preprocessing for Single-Server PIR. 2522-2548 - Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun:
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ1-Oblivious Routing. 2549-2579 - Moses Charikar, Lunjia Hu
Near-Optimal Explainable k-Means for All Dimensions. 2580-2606 - Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar:
How many Clusters? - An algorithmic answer. 2607-2640 - Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan:
Almost Tight Approximation Algorithms for Explainable Clustering. 2641-2663 - Eden Chlamtác, Yury Makarychev, Ali Vakilian
Approximating Fair Clustering with Cascaded Norm Objectives. 2664-2683 - Alberto Del Pia, Silvia Di Gregorio
On the complexity of binary polynomial optimization over acyclic hypergraphs. 2684-2699 - Daniel Dadush, László A. Végh
On finding exact solutions of linear programs in the oracle model. 2700-2722 - Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford:
Computing Lewis Weights to High Precision. 2723-2742 - Martin Nägele, Richard Santiago, Rico Zenklusen:
Congruency-Constrained TU Problems Beyond the Bimodular Case. 2743-2790 - Shyan Akmal
Near-Optimal Quantum Algorithms for String Problems. 2791-2832 - Moses Ganardi, Pawel Gawrychowski:
Pattern Matching on Grammar-Compressed Strings in Linear Time. 2833-2846 - Dominik Kempa, Barna Saha:
An Upper Bound and Linear-Space Queries on the LZ-End Parsing. 2847-2866 - Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln
How Compression and Approximation Affect Efficiency in String Distance Measures. 2867-2919 - Alon Eden, Kira Goldner
Private Interdependent Valuations. 2920-2939 - Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, Xizhi Tan:
Deterministic Budget-Feasible Clock Auctions. 2940-2963 - Zi Yang Kang, Francisco Pernice, Jan Vondrák:
Fixed-Price Approximations in Bilateral Trade. 2964-2985 - Moses Charikar, Prasanna Ramakrishnan:
Metric Distortion Bounds for Randomized Social Choice. 2986-3004 - Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, Peilin Zhong:
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches. 3005-3042 - Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff:
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. 3043-3068 - Karl Bringmann, Nick Fischer, Vasileios Nakos:
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. 3069-3090 - John Kallaugher, Michael Kapralov
Simulating Random Walks in Random Streams. 3091-3126 - Christopher J. Bishop:
Optimal angle bounds for Steiner triangulations of polygons. 3127-3143 - Ivor van der Hoog
Preprocessing Imprecise Points for the Pareto Front. 3144-3167 - Haitao Wang:
Constructing Many Faces in Arrangements of Lines and Segments. 3168-3180 - Marvin Künnemann, André Nusser:
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. 3181-3201 - Étienne Bamas, Marina Drygala, Andreas Maggiori
An Improved Analysis of Greedy for Online Steiner Forest. 3202-3229 - Shi Li, Bundit Laekhanukit:
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree. 3230-3236 - Ruoxu Cen, Jason Li, Debmalya Panigrahi:
Augmenting Edge Connectivity via Isolating Cuts. 3237-3252 - Vera Traub
Local Search for Weighted Tree Augmentation and Steiner Tree. 3253-3272 - Greg Bodwin, Michael Dinitz, Caleb Robelle:
Partially Optimal Edge Fault-Tolerant Spanners. 3272-3286 - Hung Le, Cuong Than:
Greedy Spanners in Euclidean Spaces Admit Sublinear Separators. 3287-3310 - Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu:
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product. 3311-3331 - Hung Le, Shay Solomon:
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time. 3332-3361 - Haotian Wang, Feng Luo, Jie Gao:
Co-evolution of Opinion and Social Tie Dynamics Towards Structural Balance. 3362-3388 - Souvik Dhara
Spectral recovery of binary censored block models. 3389-3416 - Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter Kling:
Fast Consensus via the Unconstrained Undecided State Dynamics. 3417-3429 - Yeganeh Alimohammadi, Christian Borgs, Amin Saberi:
Algorithms Using Local Graph Features to Predict Epidemics. 3430-3451 - Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. 3452-3481 - Debarati Das, Maximilian Probst Gutenberg
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. 3482-3495 - Timothy M. Chan, Qizheng He
Dynamic Geometric Set Cover, Revisited. 3496-3528 - Soheil Behnezhad, Sanjeev Khanna
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. 3529-3566 - Kim-Manuel Klein:
On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem. 3567-3582 - Wei-Kai Lin, Elaine Shi:
Optimal Sorting Circuits for Short Keys. 3583-3629 - Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. 3630-3649 - Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya:
An Improved Algorithm for The k-Dyck Edit Distance Problem. 3650-3669 - Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, Eric Vigoda:
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization. 3670-3692 - Antares Chen, Jonathan Shi, Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. 3693-3731 - Tali Kaufman, Rasmus Kyng, Federico Soldà:
Scalar and Matrix Chernoff Bounds from ℓ∞-Independence. 3732-3753 - Ariel D. Procaccia, Jamie Tucker-Foltz:
Compact Redistricting Plans Have Many Spanning Trees. 3754-3771
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 2025-01-06 23:26 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: