Accepted papers

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


Co-organizers

Sponsors


CONTACT US
icalp2022@irif.fr
@ICALPconf