| 2022 | (Re)packing Equal Disks into Rectangle. Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Meirav Zehavi |
| 2022 | 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022 Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff |
| 2022 | A Brief Tour in Twin-Width (Invited Talk). Stéphan Thomassé |
| 2022 | A Faster Interior-Point Method for Sum-Of-Squares Optimization. Shunhua Jiang, Bento Natura, Omri Weinstein |
| 2022 | A Fixed-Parameter Algorithm for the Kneser Problem. Ishay Haviv |
| 2022 | A Generic Solution to Register-Bounded Synthesis with an Application to Discrete Orders. Léo Exibard, Emmanuel Filiot, Ayrat Khalimov |
| 2022 | A PTAS for Capacitated Vehicle Routing on Trees. Claire Mathieu, Hang Zhou |
| 2022 | A PTAS for Packing Hypercubes into a Knapsack. Klaus Jansen, Arindam Khan, Marvin Lira, K. V. N. Sreenivas |
| 2022 | A Perfect Sampler for Hypergraph Independent Sets. Guoliang Qiu, Yanheng Wang, Chihao Zhang |
| 2022 | A Structural Investigation of the Approximability of Polynomial-Time Problems. Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann |
| 2022 | A Study of Weisfeiler-Leman Colorings on Planar Graphs. Sandra Kiefer, Daniel Neuen |
| 2022 | Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures. Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, Alexandre Vigny |
| 2022 | Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs. Talya Eden, Dana Ron, Will Rosenbaum |
| 2022 | Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity. Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang |
| 2022 | An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space. Takaaki Nishimoto, Shunsuke Kanda, Yasuo Tabei |
| 2022 | Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. Jakub Tetek |
| 2022 | Approximating Observables Is as Hard as Counting. Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
| 2022 | Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai |
| 2022 | Approximation Algorithms for Interdiction Problem with Packing Constraints. Lin Chen, Xiaoyu Wu, Guochuan Zhang |
| 2022 | Backdoor Sets on Nowhere Dense SAT. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan |
| 2022 | Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts. Shimon Kogan, Merav Parter |
| 2022 | Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming. Marcin Brianski, Martin Koutecký, Daniel Král', Kristýna Pekárková, Felix Schröder |
| 2022 | Circuit Extraction for ZX-Diagrams Can Be #P-Hard. Niel de Beaudrap, Aleks Kissinger, John van de Wetering |
| 2022 | Competitive Vertex Recoloring. Yossi Azar, Chay Machluf, Boaz Patt-Shamir, Noam Touitou |
| 2022 | Computability of Finite Simplicial Complexes. Djamel Eddine Amir, Mathieu Hoyrup |
| 2022 | Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k. Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang |
| 2022 | Deciding Twin-Width at Most 4 Is NP-Complete. Pierre Bergé, Édouard Bonnet, Hugues Déprés |
| 2022 | Decremental Matching in General Graphs. Sepehr Assadi, Aaron Bernstein, Aditi Dudeja |
| 2022 | Delegation for Search Problems. Justin Holmgren, Andrea Lincoln, Ron D. Rothblum |
| 2022 | Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck |
| 2022 | Distributed Controller Synthesis for Deadlock Avoidance. Hugo Gimbert, Corto Mascle, Anca Muscholl, Igor Walukiewicz |
| 2022 | Downsampling for Testing and Learning in Product Distributions. Nathaniel Harms, Yuichi Yoshida |
| 2022 | Dynamic Meta-Theorems for Distance and Matching. Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari |
| 2022 | Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning (Invited Talk). Constantinos Daskalakis |
| 2022 | Exact Recovery Algorithm for Planted Bipartite Graph in Semi-Random Graphs. Akash Kumar, Anand Louis, Rameesh Paul |
| 2022 | Expander Random Walks: The General Case and Limitations. Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma |
| 2022 | Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel. Ittai Rubinstein |
| 2022 | Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices. Zvika Brakerski, Nico Döttling, Sanjam Garg, Giulio Malavolta |
| 2022 | Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic |
| 2022 | Faster Cut Sparsification of Weighted Graphs. Sebastian Forster, Tijn de Vos |
| 2022 | Faster Cut-Equivalent Trees in Simple Graphs. Tianyi Zhang |
| 2022 | Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. Karl Bringmann, Alejandro Cassis |
| 2022 | Finding Monotone Patterns in Sublinear Time, Adaptively. Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten |
| 2022 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2022 | Fully Functional Parameterized Suffix Trees in Compact Space. Arnab Ganguly, Rahul Shah, Sharma V. Thankachan |
| 2022 | Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun |
| 2022 | Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring. Aleksander B. G. Christiansen, Eva Rotenberg |
| 2022 | Functions and References in the Pi-Calculus: Full Abstraction and Proof Techniques. Enguerrand Prebet |
| 2022 | Galloping in Fast-Growth Natural Merge Sorts. Elahe Ghasemi, Vincent Jugé, Ghazal Khalighinejad |
| 2022 | Graph Reconstruction from Random Subgraphs. Andrew McGregor, Rik Sengupta |
| 2022 | Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang |
| 2022 | Hiding Pebbles When the Output Alphabet Is Unary. Gaëtan Douéneau-Tabot |
| 2022 | High-Probability List-Recovery, and Applications to Heavy Hitters. Dean Doron, Mary Wootters |
| 2022 | Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes. Mitchell Black, Amir Nayyeri |
| 2022 | Homomorphism Tensors and Linear Equations. Martin Grohe, Gaurav Rattan, Tim Seppelt |
| 2022 | Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi |
| 2022 | Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. Debarati Das, Tomasz Kociumaka, Barna Saha |
| 2022 | Improved Reconstruction of Random Geometric Graphs. Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore |
| 2022 | Improved Sublinear-Time Edit Distance for Preprocessed Strings. Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos |
| 2022 | In-Range Farthest Point Queries and Related Problem in High Dimensions. Ziyun Huang, Jinhui Xu |
| 2022 | LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation. Gil Cohen, Tal Yankovitz |
| 2022 | Learning Algorithms Versus Automatability of Frege Systems. Ján Pich, Rahul Santhanam |
| 2022 | Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond. Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi |
| 2022 | Linearly Ordered Colourings of Hypergraphs. Tamio-Vesa Nakajima, Stanislav Zivný |
| 2022 | Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2022 | Low-Degree Polynomials Extract From Local Sources. Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro |
| 2022 | Lower Bounds for Unambiguous Automata via Communication Complexity. Mika Göös, Stefan Kiefer, Weiqiang Yuan |
| 2022 | Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski |
| 2022 | Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. Aviad Rubinstein, Junyao Zhao |
| 2022 | Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost. Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein |
| 2022 | Metastability of the Potts Ferromagnet on Random Regular Graphs. Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, Eric Vigoda |
| 2022 | Minimum+1 (s, t)-cuts and Dual Edge Sensitivity Oracle. Surender Baswana, Koustav Bhanja, Abhyuday Pandey |
| 2022 | Monotone Arithmetic Complexity of Graph Homomorphism Polynomials. Balagopal Komarath, Anurag Pandey, Chengot Sankaramenon Rahul |
| 2022 | Near-Optimal Algorithms for Stochastic Online Bin Packing. Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, K. V. N. Sreenivas |
| 2022 | Near-Optimal Decremental Hopsets with Applications. Jakub Lacki, Yasamin Nazari |
| 2022 | New Additive Approximations for Shortest Paths and Cycles. Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, Ziqian Zhong |
| 2022 | On Computing the k-Shortcut Fréchet Distance. Jacobus Conradi, Anne Driemel |
| 2022 | On Lower Bounds of Approximating Parameterized k-Clique. Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang |
| 2022 | On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs. Charilaos Efthymiou |
| 2022 | On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games. Antonio Casares, Thomas Colcombet, Karoliina Lehtinen |
| 2022 | One-Pass Additive-Error Subset Selection for ℓ Amit Deshpande, Rameshwar Pratap |
| 2022 | Online Weighted Cardinality Joint Replenishment Problem with Delay. Ryder Chen, Jahanvi Khatkar, Seeun William Umboh |
| 2022 | Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. Zhenjian Lu, Igor C. Oliveira, Marius Zimand |
| 2022 | Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game. William Kuszmaul, Shyam Narayanan |
| 2022 | Pairwise Reachability Oracles and Preservers Under Failures. Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary |
| 2022 | Parameterized Complexity of Untangling Knots. Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer |
| 2022 | Parameterized Safety Verification of Round-Based Shared-Memory Systems. Nathalie Bertrand, Nicolas Markey, Ocan Sankur, Nicolas Waldburger |
| 2022 | Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras. Josh Alman, Dean Hirsch |
| 2022 | Passive Learning of Deterministic Büchi Automata by Combinations of DFAs. León Bohn, Christof Löding |
| 2022 | Polylogarithmic Sketches for Clustering. Moses Charikar, Erik Waingarten |
| 2022 | Polynomial Delay Algorithm for Minimal Chordal Completions. Caroline Brosse, Vincent Limouzy, Arnaud Mary |
| 2022 | Polynomial-Time Approximation of Zero-Free Partition Functions. Penghui Yao, Yitong Yin, Xinyuan Zhang |
| 2022 | Privately Estimating Graph Parameters in Sublinear Time. Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee |
| 2022 | Processes Parametrised by an Algebraic Theory. Todd Schmid, Wojciech Rozowski, Alexandra Silva, Jurriaan Rot |
| 2022 | Reachability in Bidirected Pushdown VASS. Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, Georg Zetzsche |
| 2022 | Reconstructing Decision Trees. Guy Blanc, Jane Lange, Li-Yang Tan |
| 2022 | Regular Expressions for Tree-Width 2 Graphs. Amina Doumane |
| 2022 | Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian |
| 2022 | Round-Optimal Lattice-Based Threshold Signatures, Revisited. Shweta Agrawal, Damien Stehlé, Anshu Yadav |
| 2022 | Satisfiability Problems for Finite Groups. Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski, Armin Weiß |
| 2022 | Separations Between Combinatorial Measures for Transitive Functions. Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar |
| 2022 | Set Membership with Two Classical and Quantum Bit Probes. Shyam Dhamapurkar, Shubham Vivek Pawar, Jaikumar Radhakrishnan |
| 2022 | Smoothed Analysis of the Komlós Conjecture. Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha |
| 2022 | Social Distancing Network Creation. Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, Anna Melnichenko |
| 2022 | Some New (And Old) Results on Contention Resolution (Invited Talk). Leslie Ann Goldberg |
| 2022 | Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems. Theodoros Papamakarios, Alexander A. Razborov |
| 2022 | Strategy Synthesis for Global Window PCTL. Benjamin Bordais, Damien Busatto-Gaston, Shibashis Guha, Jean-François Raskin |
| 2022 | Streaming Algorithms for Geometric Steiner Forest. Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý |
| 2022 | Streaming Submodular Maximization Under Matroid Constraints. Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen |
| 2022 | Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk). Madhu Sudan |
| 2022 | Strong Approximations and Irrationality in Financial Networks with Derivatives. Stavros D. Ioannidis, Bart de Keijzer, Carmine Ventre |
| 2022 | Strongly Sublinear Algorithms for Testing Pattern Freeness. Ilan Newman, Nithin Varma |
| 2022 | Sublinear Dynamic Interval Scheduling (On One or Multiple Machines). Pawel Gawrychowski, Karol Pokorski |
| 2022 | Sublinear-Round Parallel Matroid Intersection. Joakim Blikstad |
| 2022 | Testability and Local Certification of Monotone Properties in Minor-Closed Classes. Louis Esperet, Sergey Norin |
| 2022 | The Complexity of Finding Fair Many-To-One Matchings. Niclas Boehmer, Tomohiro Koana |
| 2022 | The Complexity of SPEs in Mean-Payoff Games. Léonard Brice, Jean-François Raskin, Marie van den Bogaard |
| 2022 | The Decision Problem for Perfect Matchings in Dense Hypergraphs. Luyining Gan, Jie Han |
| 2022 | The Dimension Spectrum Conjecture for Planar Lines. Donald M. Stull |
| 2022 | The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width. Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov |
| 2022 | The Manifold Joys of Sampling (Invited Talk). Yin Tat Lee, Santosh S. Vempala |
| 2022 | The SDP Value of Random 2CSPs. Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu |
| 2022 | The Variance-Penalized Stochastic Shortest Path Problem. Jakob Piribauer, Ocan Sankur, Christel Baier |
| 2022 | Threshold Rates of Code Ensembles: Linear Is Best. Nicolas Resch, Chen Yuan |
| 2022 | Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing. Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese |
| 2022 | Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs. Alexandra Lassota, Aleksander Lukasiewicz, Adam Polak |
| 2022 | Tolerant Bipartiteness Testing in Dense Graphs. Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, Sayantan Sen |
| 2022 | Towards a Theory of Algorithmic Proof Complexity (Invited Talk). Albert Atserias |
| 2022 | Twin-Width and Types. Jakub Gajarský, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk |
| 2022 | Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. Ming Ding, Rasmus Kyng, Peng Zhang |
| 2022 | Unboundedness for Recursion Schemes: A Simpler Type System. David Barozzini, Pawel Parys, Jan Wroblewski |
| 2022 | Understanding the Moments of Tabulation Hashing via Chaoses. Jakob Bæk Tejs Houen, Mikkel Thorup |
| 2022 | Unique Assembly Verification in Two-Handed Self-Assembly. David Caballero, Timothy Gomez, Robert Schweller, Tim Wylie |
| 2022 | Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games. Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz, Mateusz Skomra |
| 2022 | What Can Oracles Teach Us About the Ultimate Fate of Life? Ville Salo, Ilkka Törmä |