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