| 2022 | A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, Andreas Wiese |
| 2022 | A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision. Sumanta Ghosh, Rohit Gurjar, Roshan Raj |
| 2022 | A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method. Miriam Schlöter, Martin Skutella, Khai Van Tran |
| 2022 | A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs. Dániel Marx, Pranabendu Misra, Daniel Neuen, Prafullkumar Tale |
| 2022 | A Lower Bound for the n-queens Problem. Michael Simkin, Zur Luria |
| 2022 | A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen |
| 2022 | A Sublinear Bound on the Page Number of Upward Planar Graphs. Paul Jungeblut, Laura Merker, Torsten Ueckerdt |
| 2022 | A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures. Joachim Gudmundsson, Martin P. Seybold |
| 2022 | A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching. Sepehr Assadi |
| 2022 | Algorithmic Extensions of Dirac's Theorem. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov |
| 2022 | Algorithmic Thresholds for Refuting Random Polynomial Systems. Jun-Ting Hsieh, Pravesh K. Kothari |
| 2022 | Algorithmic trade-offs for girth approximation in undirected graphs. Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick |
| 2022 | Algorithms Using Local Graph Features to Predict Epidemics. Yeganeh Alimohammadi, Christian Borgs, Amin Saberi |
| 2022 | Almost Tight Approximation Algorithms for Explainable Clustering. Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan |
| 2022 | An Improved Algorithm for The k-Dyck Edit Distance Problem. Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya |
| 2022 | An Improved Analysis of Greedy for Online Steiner Forest. Étienne Bamas, Marina Drygala, Andreas Maggiori |
| 2022 | An Improved Local Search Algorithm for k-Median. Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic |
| 2022 | An Upper Bound and Linear-Space Queries on the LZ-End Parsing. Dominik Kempa, Barna Saha |
| 2022 | Approximate Core for Committee Selection via Multilinear Extension and Market Clearing. Kamesh Munagala, Yiheng Shen, Kangning Wang, Zhiyi Wang |
| 2022 | Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. Venkatesan Guruswami, Sai Sandeep |
| 2022 | Approximately counting independent sets in bipartite graphs via graph containers. Matthew Jenssen, Aditya Potukuchi, Will Perkins |
| 2022 | Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets. Jugal Garg, Yixin Tao, László A. Végh |
| 2022 | Approximating Fair Clustering with Cascaded Norm Objectives. Eden Chlamtác, Yury Makarychev, Ali Vakilian |
| 2022 | Approximating Sumset Size. Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2022 | Approximating the Arboricity in Sublinear Time. Talya Eden, Saleet Mossel, Dana Ron |
| 2022 | Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension. Aditya Jayaprakash, Mohammad R. Salavatipour |
| 2022 | Augmenting Edge Connectivity via Isolating Cuts. Ruoxu Cen, Jason Li, Debmalya Panigrahi |
| 2022 | Average Sensitivity of Dynamic Programming. Soh Kumabe, Yuichi Yoshida |
| 2022 | Average-Case Subset Balancing Problems. Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio |
| 2022 | Balanced Allocations: Caching and Packing, Twinning and Thinning. Dimitrios Los, Thomas Sauerwald, John Sylvester |
| 2022 | Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product. Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu |
| 2022 | Better Sum Estimation via Weighted Sampling. Lorenzo Beretta, Jakub Tetek |
| 2022 | CLAP: A New Algorithm for Promise CSPs. Lorenzo Ciardo, Stanislav Zivný |
| 2022 | Co-evolution of Opinion and Social Tie Dynamics Towards Structural Balance. Haotian Wang, Feng Luo, Jie Gao |
| 2022 | Collapsing the Tower - On the Complexity of Multistage Stochastic IPs. Kim-Manuel Klein, Janina Reuter |
| 2022 | Combinatorial Gap Theorem and Reductions between Promise CSPs. Libor Barto, Marcin Kozik |
| 2022 | Compact Redistricting Plans Have Many Spanning Trees. Ariel D. Procaccia, Jamie Tucker-Foltz |
| 2022 | Competitive Strategies for Symmetric Rendezvous on the Line. Max Klimm, Guillaume Sagnol, Martin Skutella, Khai Van Tran |
| 2022 | Computational Hardness of the Hylland-Zeckhauser Scheme. Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis |
| 2022 | Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology. Mitchell Black, William Maxwell, Amir Nayyeri, Eli Winkelman |
| 2022 | Computing Lewis Weights to High Precision. Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford |
| 2022 | Congruency-Constrained TU Problems Beyond the Bimodular Case. Martin Nägele, Richard Santiago, Rico Zenklusen |
| 2022 | Constructing Many Faces in Arrangements of Lines and Segments. Haitao Wang |
| 2022 | Counting Homomorphic Cycles in Degenerate Graphs. Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster |
| 2022 | Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. Jacob Focke, Dániel Marx, Pawel Rzazewski |
| 2022 | Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance. Joachim Gudmundsson, Sampson Wong |
| 2022 | Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. Antares Chen, Jonathan Shi, Luca Trevisan |
| 2022 | Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent. Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi |
| 2022 | Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. Chandra Chekuri, Kent Quanrud, Manuel R. Torres |
| 2022 | Deterministic Budget-Feasible Clock Auctions. Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, Xizhi Tan |
| 2022 | Deterministic algorithms for the Lovász Local Lemma: simpler, more general, and more parallel. David G. Harris |
| 2022 | Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. Karl Bringmann, Nick Fischer, Vasileios Nakos |
| 2022 | Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k. Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang |
| 2022 | Directed Tangle Tree-Decompositions and Applications. Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon |
| 2022 | Distortion-Oblivious Algorithms for Minimizing Flow Time. Yossi Azar, Stefano Leonardi, Noam Touitou |
| 2022 | Distributed Zero-Knowledge Proofs Over Networks. Aviv Bick, Gillat Kol, Rotem Oshman |
| 2022 | Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning. Xi Chen, Shyamal Patel |
| 2022 | Dynamic Geometric Set Cover, Revisited. Timothy M. Chan, Qizheng He, Subhash Suri, Jie Xue |
| 2022 | Efficient generation of elimination trees and graph associahedra. Jean Cardinal, Arturo Merino, Torsten Mütze |
| 2022 | Enumerating k-SAT functions. Dingding Dong, Nitya Mani, Yufei Zhao |
| 2022 | Fast Consensus via the Unconstrained Undecided State Dynamics. Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter Kling |
| 2022 | Faster Algorithms for Bounded-Difference Min-Plus Product. Shucheng Chi, Ran Duan, Tianle Xie |
| 2022 | Fixed-Price Approximations in Bilateral Trade. Zi Yang Kang, Francisco Pernice, Jan Vondrák |
| 2022 | Frequency Estimation with One-Sided Error. Piotr Indyk, Shyam Narayanan, David P. Woodruff |
| 2022 | Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2022 | Greedy Spanners in Euclidean Spaces Admit Sublinear Separators. Hung Le, Cuong Than |
| 2022 | High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games. Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett |
| 2022 | Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees. Timothy M. Chan, Da Wei Zheng |
| 2022 | How Compression and Approximation Affect Efficiency in String Distance Measures. Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha |
| 2022 | How many Clusters? - An algorithmic answer. Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar |
| 2022 | Improved Algorithms for Low Rank Approximation from Sparsity. David P. Woodruff, Taisuke Yasuda |
| 2022 | Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches. Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, Peilin Zhong |
| 2022 | Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths. Adam Karczmarz |
| 2022 | Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg |
| 2022 | Isomorphism Testing for Graphs Excluding Small Topological Subgraphs. Daniel Neuen |
| 2022 | Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓ Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee |
| 2022 | Learning-Augmented Weighted Paging. Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee |
| 2022 | Limits of Preprocessing for Single-Server PIR. Giuseppe Persiano, Kevin Yeo |
| 2022 | Local Search for Weighted Tree Augmentation and Steiner Tree. Vera Traub, Rico Zenklusen |
| 2022 | Massively Parallel and Dynamic Algorithms for Minimum Size Clustering. Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, Peilin Zhong |
| 2022 | Metric Distortion Bounds for Randomized Social Choice. Moses Charikar, Prasanna Ramakrishnan |
| 2022 | Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki |
| 2022 | Multi-token Markov Game with Switching Costs. Jian Li, Daogao Liu |
| 2022 | Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff |
| 2022 | Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
| 2022 | Near-Optimal Explainable k-Means for All Dimensions. Moses Charikar, Lunjia Hu |
| 2022 | Near-Optimal Quantum Algorithms for String Problems. Shyan Akmal, Ce Jin |
| 2022 | Near-Optimal Spanners for General Graphs in (Nearly) Linear Time. Hung Le, Shay Solomon |
| 2022 | Nearly 2-Approximate Distance Oracles in Subquadratic Time. Shiri Chechik, Tianyi Zhang |
| 2022 | Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time. Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye |
| 2022 | New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier. Shimon Kogan, Merav Parter |
| 2022 | New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. Soheil Behnezhad, Sanjeev Khanna |
| 2022 | On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization. Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, Eric Vigoda |
| 2022 | On complete classes of valuated matroids. Edin Husic, Georg Loho, Ben Smith, László A. Végh |
| 2022 | On finding exact solutions of linear programs in the oracle model. Daniel Dadush, László A. Végh, Giacomo Zambelli |
| 2022 | On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem. Kim-Manuel Klein |
| 2022 | On the Hardness of Scheduling With Non-Uniform Communication Delays. Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski, Yihao Zhang |
| 2022 | On the complexity of binary polynomial optimization over acyclic hypergraphs. Alberto Del Pia, Silvia Di Gregorio |
| 2022 | Online Discrepancy with Recourse for Vectors and Graphs. Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla |
| 2022 | Online Graph Algorithms with Predictions. Yossi Azar, Debmalya Panigrahi, Noam Touitou |
| 2022 | Online Nash Social Welfare Maximization with Predictions. Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, Billy Jin |
| 2022 | Online Weighted Matching with a Sample. Haim Kaplan, David Naori, Danny Raz |
| 2022 | Optimal Oblivious Parallel RAM. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi |
| 2022 | Optimal Sorting Circuits for Short Keys. Wei-Kai Lin, Elaine Shi |
| 2022 | Optimal angle bounds for Steiner triangulations of polygons. Christopher J. Bishop |
| 2022 | Partially Optimal Edge Fault-Tolerant Spanners. Greg Bodwin, Michael Dinitz, Caleb Robelle |
| 2022 | Pattern Matching on Grammar-Compressed Strings in Linear Time. Moses Ganardi, Pawel Gawrychowski |
| 2022 | Perfect Matching in Random Graphs is as Hard as Tseitin. Per Austrin, Kilian Risse |
| 2022 | Planar Multiway Cut with Terminals on Few Faces. Sukanya Pandey, Erik Jan van Leeuwen |
| 2022 | Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. Marvin Künnemann, André Nusser |
| 2022 | Polynomial Integrality Gap of Flow LP for Directed Steiner Tree. Shi Li, Bundit Laekhanukit |
| 2022 | Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta |
| 2022 | Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws. Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Pawel Rzazewski |
| 2022 | Preprocessing Imprecise Points for the Pareto Front. Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, Bettina Speckmann |
| 2022 | Private Interdependent Valuations. Alon Eden, Kira Goldner, Shuran Zheng |
| 2022 | Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022 Joseph (Seffi) Naor, Niv Buchbinder |
| 2022 | Promise Constraint Satisfaction and Width. Albert Atserias, Víctor Dalmau |
| 2022 | Recognizing <italic>k</italic>-leaf powers in polynomial time, for constant <italic>k</italic>. Manuel Lafond |
| 2022 | Robust Load Balancing with Machine Learned Advice. Sara Ahmadian, Hossein Esfandiari, Vahab S. Mirrokni, Binghui Peng |
| 2022 | Robust Secretary and Prophet Algorithms for Packing Integer Programs. C. J. Argue, Anupam Gupta, Marco Molinaro, Sahil Singla |
| 2022 | Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
| 2022 | Scalar and Matrix Chernoff Bounds from ℓ Tali Kaufman, Rasmus Kyng, Federico Soldà |
| 2022 | Selectable Heaps and Optimal Lazy Search Trees. Bryce Sandlund, Lingyi Zhang |
| 2022 | Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space. Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian |
| 2022 | Sensitivity Oracles for All-Pairs Mincuts. Surender Baswana, Abhyuday Pandey |
| 2022 | Simulating Random Walks in Random Streams. John Kallaugher, Michael Kapralov, Eric Price |
| 2022 | Simulating a stack using queues. Haim Kaplan, Robert E. Tarjan, Or Zamir, Uri Zwick |
| 2022 | Single-Sample Prophet Inequalities via Greedy-Ordered Selection. Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser |
| 2022 | Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time. Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu |
| 2022 | Spectral recovery of binary censored block models. Souvik Dhara, Julia Gaudio, Elchanan Mossel, Colin Sandon |
| 2022 | Splay trees on trees. Benjamin Aram Berendsohn, László Kozma |
| 2022 | Stochastic Vertex Cover with Few Queries. Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan |
| 2022 | Streaming Regular Expression Membership and Pattern Matching. Bartlomiej Dudek, Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya |
| 2022 | Strong recovery of geometric planted matchings. Dmitriy Kunisky, Jonathan Niles-Weed |
| 2022 | Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H<-Minor-Free Graphs. Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue |
| 2022 | Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract). Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi |
| 2022 | Testing matrix product states. Mehdi Soleimanifar, John Wright |
| 2022 | The Complexity of Average-Case Dynamic Subgraph Counting. Monika Henzinger, Andrea Lincoln, Barna Saha |
| 2022 | The Sparse Parity Matrix. Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, Jean Bernoulli Ravelomanana |
| 2022 | The complexity of testing all properties of planar graphs, and the role of isomorphism. Sabyasachi Basu, Akash Kumar, C. Seshadhri |
| 2022 | The popular assignment problem: when cardinality is more important than popularity. Telikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, Ulrike Schmidt-Kraepelin |
| 2022 | Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros |
| 2022 | Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack. Jiashuo Jiang, Will Ma, Jiawei Zhang |
| 2022 | Tight running times for minimum <italic>ℓ Lin Chen, Liangde Tao, José Verschae |
| 2022 | Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu |
| 2022 | Twin-width VI: the lens of contraction sequences. Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé |
| 2022 | Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun |
| 2022 | Unsplittable Flow on a Path: The Game!. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese |
| 2022 | Untangling Planar Graphs and Curves by Staying Positive. Santiago Aranguri, Hsien-Chih Chang, Dylan Fridman |