Track A

• Sebastian Forster and Tijn de Vos. Faster Cut Sparsification of Weighted Graphs
• Tal Yankovitz and Gil Cohen. LCC and LDC: Tailor-made distance amplification and a refined separation
• Bingkai Lin, Xuandi Ren, Yican Sun and Xiuhan Wang. On Lower Bounds of Approximating Parameterized $k$-Clique
• Pierre Bergé, Édouard Bonnet and Hugues Déprés. Deciding twin-width at most 4 is NP-complete
• Aviad Rubinstein and Junyao Zhao. Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation
• Louis Esperet and Sergey Norin. Testability and local certification of monotone properties in minor-closed classes
• Ishay Haviv. A Fixed-Parameter Algorithm for the Kneser Problem
• Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor and Nicole Wein. Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
• Penghui Yao, Yitong Yin and Xinyuan Zhang. Polynomial-Time Approximation of Zero-Free Partition Functions
• Tianyi Zhang. Faster Cut-Equivalent Trees in Simple Graphs
• Balagopal Komarath, Anurag Pandey and C. S. Rahul. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials
• Surya Mathialagan, Virginia Vassilevska Williams and Yinzhan Xu. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
• Yossi Azar, Chay Machluf, Boaz Patt-Shamir and Noam Touitou. Competitive Vertex Recoloring
• Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams and Ziqian Zhong. New additive approximations for shortest paths and cycles
• Chao Liao, Qingyun Chen, Bundit Laekhanukit and Yuhao Zhang. Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
• Luyining Gan and Jie Han. The decision problem for perfect matchings in dense hypergraphs
• Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla and Makrand Sinha. Smoothed Analysis of the Koml\’os Conjecture
• Aleksander B. G. Christiansen and Eva Rotenberg. Fully-dynamic α + 2 Arboricity Decomposition and Implicit Colouring
• Sourav Chakraborty, Chandrima Kayal and Manaswi Paraashar. Separations between Combinatorial Measures for Transitive Functions
• Ming Ding, Rasmus Kyng and Peng Zhang. Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions
• Zhenjian Lu, Igor Oliveira and Marius Zimand. Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
• Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee and Pasin Manurangsi. Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
• Jakub Tětek. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
• Lin Chen, Xiaoyu Wu and Guochuan Zhang. Approximation Algorithms for Interdiction Problem with Packing Constraints
• Shir Peleg, Gil Cohen, Dor Minzer and Aaron Potechin. Expander Random Walks: The General Case and Limitations
• Martin Grohe, Gaurav Rattan and Tim Seppelt. Homomorphism Tensors and Linear Equations
• Clément Legrand-Duchesne, Ashutosh Rai and Martin Tancer. Parameterized complexity of untangling knots
• Jakub Łącki and Yasamin Nazari. Near-Optimal Decremental Hopsets with Applications
• Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson and Rico Zenklusen. Streaming Submodular Maximization under Matroid Constraints
• Marcin Briański, Martin Koutecký, Daniel Kráľ, Kristýna Pekárková and Felix Schröder. Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• Josep Diaz, Varsha Dani, Cristopher Moore and Thomas Hayes. Improved Reconstruction of Random Geometric Graphs
• Alexandra Lassota, Aleksander Łukasiewicz and Adam Polak. Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
• Claire Mathieu and Hang Zhou. A PTAS for Capacitated Vehicle Routing on Trees
• Ilan Newman and Nithin Varma. Strongly Sublinear Algorithms for Testing Pattern Freeness
• Dean Doron and Mary Wootters. High-Probability List-Recovery, and Applications to Heavy Hitters
• Charilaos Efthymiou. On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
• Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer and Pavel Veselý. Streaming Algorithms for Geometric Steiner Forest
• Theodoros Papamakarios and Alexander Razborov. Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Omri Ben-Eliezer, Shoham Letzter and Erik Waingarten. Finding Monotone Patterns in Sublinear Time, Adaptively
• Talya Eden, Dana Ron and Will Rosenbaum. Almost Optimal Bounds for Sublinear-Time Sampling of $k$-Cliques in Bounded Arboricity Graphs
• Shweta Agrawal, Damien Stehle and Anshu Yadav. Round-Optimal Lattice-Based Threshold Signatures, Revisited
• Takaaki Nishimoto, Shunsuke Kanda and Yasuo Tabei. An Optimal-Time RLBWT Construction in BWT-runs Bounded Space
• Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg and Peng Zhang. Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
• Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa and Kirill Simonov. The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
• Nicolas Resch and Chen Yuan. Threshold Rates of Code Ensembles: Linear is Best
• Surender Baswana, Koustav Bhanja and Abhyuday Pandey. Minimum+1 (s,t)-cuts and dual edge sensitivity oracle
• Jaikumar Radhakrishnan, Shyam Dhamapurkar and Shubham Pawar. Set membership with two classical and quantum bit probes
• Joakim Blikstad. Sublinear-round Parallel Matroid Intersection
• Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma and Andreas Wiese. Tight Approximation Algorithms for Two-dimensional Guillotine Strip Packing
• Ivona Bezakova, Andreas Galanis, Leslie Goldberg and Daniel Stefankovic. Fast sampling via spectral independence beyond bounded-degree graphs
• Caroline Brosse, Vincent Limouzy and Arnaud Mary. Polynomial delay algorithm for minimal chordal completions
• Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert and Sorrachai Yingchareonthawornchai. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
• Aaron Bernstein, Jan van den Brand, Maximilian Probst, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
• Jacobus Conradi and Anne Driemel. On Computing the k-Shortcut Fréchet Distance
• Shimon Kogan and Merav Parter. Beating Matrix Multiplication for $n^{1/3}$-Directed Shortcuts
• Fedor Fomin, Petr Golovach, Tanmay Inamdar and Meirav Zehavi. (Re)packing Equal Disks into Rectangle
• William Kuszmaul and Shyam Narayanan. Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
• Amit Deshpande and Rameshwar Pratap. One-pass additive-error subset selection for $\ell_{p}$ subspace approximation
• Nathaniel Harms and Yuichi Yoshida. Downsampling for Testing and Learning in Product Distributions
• Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski and Marek Sokołowski. Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás’ path argument
• Elahe Ghasemi, Vincent Jugé and Ghazal Khalighinejad. Galloping in fast-growth natural merge sorts
• Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
• Shunhua Jiang, Bento Natura and Omri Weinstein. A Faster Interior-Point Method for Sum-of-Squares Optimization
• Debarati Das, Tomasz Kociumaka and Barna Saha. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
• Josh Alman and Dean Hirsch. Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
• Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk and Alexandre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures
• Arnab Ganguly, Rahul Shah and Sharma V. Thankachan. Fully Functional Parameterized Suffix Trees in Compact Space
• Ramanujan M. Sridharan, Daniel Lokshtanov and Fahad Panolan. Backdoor Sets on Nowhere Dense SAT
• Niclas Boehmer and Tomohiro Koana. The Complexity of Finding Fair Many-to-One Matchings
• Klaus Jansen, Arindam Khan, Marvin Lira and K. V. N. Sreenivas. A PTAS for Packing Hypercubes into a Knapsack
• Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic and Eric Vigoda. Metastability of the Potts ferromagnet on random regular graphs
• Andreas Galanis, Daniel Stefankovic and Eric Vigoda. Approximating observables is as hard as counting
• Pawel Gawrychowski and Karol Pokorski. Sublinear Dynamic Interval Scheduling (on one or multiple machines)
• Amulya Musipatla, Ryan O’Donnell, Tselil Schramm and Xinyu Wu. The SDP value of random 2CSPs
• Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury and Sayantan Sen. Tolerant Bipartiteness Testing in Dense Graphs
• David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie. Unique Assembly Verification in Two-Handed Self-Assembly
• Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner and Anna Melnichenko. Social Distancing Network Creation
• Stavros Ioannidis, Bart de Keijzer and Carmine Ventre. Strong Approximations and Irrationality in Financial Networks with Derivatives
• Justin Holmgren, Andrea Lincoln and Ron Rothblum. Delegation for Search Problems
• Jan Pich and Rahul Santhanam. Learning algorithms versus automatability of Frege systems
• Sepehr Assadi, Aaron Bernstein and Aditi Dudeja. Decremental Matching in General Graphs
• Jeremiah Blocki, Elena Grigorescu and Tamalika Mukherjee. Privately Estimating Graph Parameters in Sublinear time
• Karl Bringmann, Alejandro Cassis, Nick Fischer and Marvin Künnemann. A Structural Investigation of the Approximability of Polynomial-Time Problems
• Mitchell Black and Amir Nayyeri. Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes
• Akash Kumar, Anand Louis and Rameesh Paul. Exact recovery algorithm for Planted Bipartite Graph in Semi-random Graphs
• Ittai Rubinstein. Explicit and Efficient Construction of (nearly) Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel
• Karl Bringmann, Alejandro Cassis, Nick Fischer and Vasileios Nakos. Improved Sublinear-Time Edit Distance for Preprocessed Strings
• Calvin Beideman, Karthekeyan Chandrasekaran and Weihang Wang. Counting and enumerating optimum cut sets for hypergraph k-partitioning problems for fixed k
• Andrew McGregor and Rik Sengupta. Graph Reconstruction from Random Subgraphs
• Karl Bringmann and Alejandro Cassis. Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
• Ziyun Huang and Jinhui Xu. In-Range Farthest Point Queries and Related Problem in High Dimensions
• Diptarka Chakraborty, Kushagra Chatterjee and Keerti Choudhary. Pairwise Reachability Oracles and Preservers under Failures
• Guoliang Qiu, Yanheng Wang and Chihao Zhang. A Perfect Sampler for Hypergraph Independent Sets
• Guy Blanc, Jane Lange and Li-Yang Tan. Reconstructing Decision Trees
• Moses Charikar and Erik Waingarten. Polylogarithmic Sketches for Clustering
• Arun Jambulapati, Yujia Jin, Aaron Sidford and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching
• Chi-Ning Chou, Peter Love, Jonathan Shi and Juspreet Singh Sandhu. Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond
• Zvika Brakerski, Nico Döttling, Sanjam Garg and Giulio Malavolta. Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices
• Sandra Kiefer and Daniel Neuen. A Study of Weisfeiler-Leman Colorings on Planar Graphs
• Nikhil Ayyadevara, Rajni Dabas, Arindam Khan and K. V. N. Sreenivas. Near-optimal Algorithms for Stochastic Online Bin Packing
• Jakob Bæk Tejs Houen and Mikkel Thorup. Understanding the Moments of Tabulation Hashing via Chaoses
• Ryder Chen, Jahanvi Khatkar and Seeun William Umboh. Online Weighted Cardinality Joint Replenishment Problem with Delay
• Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li and João Ribeiro. Low-Degree Polynomials Extract from Local Sources

Track B

• Tamio-Vesa Nakajima and Stanislav Živný. Linearly ordered colourings of hypergraphs
• Gaëtan Douéneau-Tabot. Hiding pebbles when the output alphabet is unary
• Djamel Eddine Amir and Mathieu Hoyrup. Computability of finite simplicial complexes
• Donald Stull. The Dimension Spectrum Conjecture for Planar Lines
• Enguerrand Prebet. Functions and references in the pi-calculus: full abstraction and proof techniques
• Hugo Gimbert, Corto Mascle, Anca Muscholl and Igor Walukiewicz. Distributed controller synthesis for deadlock avoidance
• Jakob Piribauer, Ocan Sankur and Christel Baier. The variance-penalized stochastic shortest path problem
• Mika Göös, Stefan Kiefer and Weiqiang Yuan. Lower Bounds for Unambiguous Automata via Communication Complexity
• Antonio Casares, Thomas Colcombet and Karoliina Lehtinen. On the size of good-for-games Rabin automata and its link with the memory in Muller games
• Ville Salo and Ilkka Törmä. What can oracles teach us about the ultimate fate of life?
• Nathalie Bertrand, Nicolas Markey, Ocan Sankur and Nicolas Waldburger. Parameterized safety verification of round-based shared-memory systems
• Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze and Georg Zetzsche. Reachability in Bidirected Pushdown VASS
• Léo Exibard, Emmanuel Filiot and Ayrat Khalimov. A Generic Solution to Register-bounded Synthesis With an Application to Discrete Orders
• David Barozzini, Paweł Parys and Jan Wróblewski. Unboundedness for Recursion Schemes: A Simpler Type System
• Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma and Raghunath Tewari. Dynamic Meta-theorems for Distance and Matching
• Todd Schmid, Wojciech Rozowski, Alexandra Silva and Jurriaan Rot. Processes Parametrised by an Algebraic Theory
• Amina Doumane. Regular expressions for tree-width 2 graphs
• Leon Bohn and Christof Löding. Passive Learning of Deterministic Büchi Automata by Combinations of DFAs
• Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski and Szymon Toruńczyk. Twin-width and types
• Léonard Brice, Jean-Francois Raskin and Marie Van Den Bogaard. The complexity of SPEs in Mean-payoff Games
• Benjamin Bordais, Damien Busatto-Gaston, Shibashis Guha and Jean-Francois Raskin. Strategy Synthesis for Global Window PCTL
• Niel De Beaudrap, Aleks Kissinger and John van de Wetering. Circuit Extraction for ZX-diagrams can be #P-hard
• Xavier Allamigeon, Stephane Gaubert, Ricardo D. Katz and Mateusz Skomra. Universal complexity bounds based on value iteration and application to entropy games
• Pawel Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß. Satisfiability problems for finite groups

---

• Mail
• Twitter

Co-organizers

Sponsors

---

CONTACT US
icalp2022@irif.fr
@ICALPconf