Portal - ICALP 2022

ICALP 2022	July 4-8, 2022, Paris, France
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) Mikołaj Bojańczyk and Emanuela Merelli and David P. Woodruff (Eds.)
ISBN 978-3-95977-235-8, LIPICS Vol. 229	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 52 MB)
Search Publication Server

Authors

Ayyadevara, Nikhil ^*

Busatto-Gaston, Damien

Caballero, David

Casares, Antonio

Cassis, Alejandro

Chakraborty, Diptarka

Chakraborty, Sourav

Chalermsook, Parinya

Chandrasekaran, Karthekeyan

Christiansen, Aleksander B. G.

Daskalakis, Constantinos

Dhamapurkar, Shyam S.

Ding, Ming

Doron, Dean

Doumane, Amina

Douéneau-Tabot, Gaëtan

Gutenberg, Maximilian Probst

Houen, Jakob Bæk Tejs

Ioannidis, Stavros D.

Jiang, Shaofeng H.-C.

Khalighinejad, Ghazal

Legrand-Duchesne, Clément

Papamakarios, Theodoros

Pavlogiannis, Andreas

Probst Gutenberg, Maximilian

Przybyszewski, Wojciech

Qiu, Guoliang

Radhakrishnan, Jaikumar

Rahul, Chengot Sankaramenon

Rai, Ashutosh

Ramanujan, M. S.

Raskin, Jean-François

Rattan, Gaurav

Ravelomanana, Jean Bernoulli

Sandhu, Juspreet Singh

Sankur, Ocan

Santhanam, Rahul

Saranurak, Thatchaphol

Thankachan, Sharma V.

van de Wetering, John

van den Bogaard, Marie

van den Brand, Jan

Varma, Nithin

Vassilevska Williams, Virginia

Yingchareonthawornchai, Sorrachai

Łukasiewicz, Aleksander

Łącki, Jakub

Štefankovič, Daniel

Živný, Stanislav

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Bojańczyk, Mikołaj ; Merelli, Emanuela ; Woodruff, David P.

Abstract | Document (744 KB) | BibTeX

Towards a Theory of Algorithmic Proof Complexity (Invited Talk)

Authors: Atserias, Albert

Abstract | Document (347 KB) | BibTeX

Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning (Invited Talk)

Authors: Daskalakis, Constantinos

Abstract | Document (376 KB) | BibTeX

Some New (And Old) Results on Contention Resolution (Invited Talk)

Authors: Goldberg, Leslie Ann

Abstract | Document (572 KB) | BibTeX

The Manifold Joys of Sampling (Invited Talk)

Authors: Lee, Yin Tat ; Vempala, Santosh S.

Abstract | Document (978 KB) | BibTeX

Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk)

Authors: Sudan, Madhu

Abstract | Document (872 KB) | BibTeX

A Brief Tour in Twin-Width (Invited Talk)

Authors: Thomassé, Stéphan

Abstract | Document (406 KB) | BibTeX

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

Authors: Abboud, Amir ; Cohen-Addad, Vincent ; Lee, Euiwoong ; Manurangsi, Pasin

Abstract | Document (806 KB) | BibTeX

Round-Optimal Lattice-Based Threshold Signatures, Revisited

Authors: Agrawal, Shweta ; Stehlé, Damien ; Yadav, Anshu

Abstract | Document (878 KB) | BibTeX

Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras

Authors: Alman, Josh ; Hirsch, Dean

Abstract | Document (843 KB) | BibTeX

Low-Degree Polynomials Extract From Local Sources

Authors: Alrabiah, Omar ; Chattopadhyay, Eshan ; Goodman, Jesse ; Li, Xin ; Ribeiro, João

Abstract | Document (880 KB) | BibTeX

Decremental Matching in General Graphs

Authors: Assadi, Sepehr ; Bernstein, Aaron ; Dudeja, Aditi

Abstract | Document (1,054 KB) | BibTeX

Near-Optimal Algorithms for Stochastic Online Bin Packing

Authors: Ayyadevara, Nikhil ^* ; Dabas, Rajni ; Khan, Arindam ; Sreenivas, K. V. N.

Abstract | Document (892 KB) | BibTeX

Competitive Vertex Recoloring

Authors: Azar, Yossi ; Machluf, Chay ; Patt-Shamir, Boaz ; Touitou, Noam

Abstract | Document (804 KB) | BibTeX

Smoothed Analysis of the Komlós Conjecture

Authors: Bansal, Nikhil ; Jiang, Haotian ; Meka, Raghu ; Singla, Sahil ; Sinha, Makrand

Abstract | Document (659 KB) | BibTeX

Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle

Authors: Baswana, Surender ; Bhanja, Koustav ; Pandey, Abhyuday

Abstract | Document (1,612 KB) | BibTeX

Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k

Authors: Beideman, Calvin ; Chandrasekaran, Karthekeyan ; Wang, Weihang

Abstract | Document (908 KB) | BibTeX

Finding Monotone Patterns in Sublinear Time, Adaptively

Authors: Ben-Eliezer, Omri ; Letzter, Shoham ; Waingarten, Erik

Abstract | Document (900 KB) | BibTeX

Deciding Twin-Width at Most 4 Is NP-Complete

Authors: Bergé, Pierre ; Bonnet, Édouard ; Déprés, Hugues

Abstract | Document (854 KB) | BibTeX

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Authors: Berger, Aaron ; Kuszmaul, William ; Polak, Adam ; Tidor, Jonathan ; Wein, Nicole

Abstract | Document (821 KB) | BibTeX

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Authors: Bernstein, Aaron ; van den Brand, Jan ; Probst Gutenberg, Maximilian ; Nanongkai, Danupon ; Saranurak, Thatchaphol ; Sidford, Aaron ; Sun, He

Abstract | Document (743 KB) | BibTeX

Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs

Authors: Bezáková, Ivona ; Galanis, Andreas ; Goldberg, Leslie Ann ; Štefankovič, Daniel

Abstract | Document (777 KB) | BibTeX

Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

Authors: Bilò, Davide ; Choudhary, Keerti ; Cohen, Sarel ; Friedrich, Tobias ; Schirneck, Martin

Abstract | Document (870 KB) | BibTeX

Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

Authors: Black, Mitchell ; Nayyeri, Amir

Abstract | Document (741 KB) | BibTeX

Reconstructing Decision Trees

Authors: Blanc, Guy ; Lange, Jane ; Tan, Li-Yang

Abstract | Document (800 KB) | BibTeX

Sublinear-Round Parallel Matroid Intersection

Authors: Blikstad, Joakim

Abstract | Document (799 KB) | BibTeX

Privately Estimating Graph Parameters in Sublinear Time

Authors: Blocki, Jeremiah ; Grigorescu, Elena ; Mukherjee, Tamalika

Abstract | Document (869 KB) | BibTeX

The Complexity of Finding Fair Many-To-One Matchings

Authors: Boehmer, Niclas ; Koana, Tomohiro

Abstract | Document (854 KB) | BibTeX

Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices

Authors: Brakerski, Zvika ; Döttling, Nico ; Garg, Sanjam ; Malavolta, Giulio

Abstract | Document (793 KB) | BibTeX

Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Authors: Briański, Marcin ; Koutecký, Martin ; Král', Daniel ; Pekárková, Kristýna ; Schröder, Felix

Abstract | Document (668 KB) | BibTeX

A Structural Investigation of the Approximability of Polynomial-Time Problems

Authors: Bringmann, Karl ; Cassis, Alejandro ; Fischer, Nick ; Künnemann, Marvin

Abstract | Document (789 KB) | BibTeX

Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

Authors: Bringmann, Karl ; Cassis, Alejandro

Abstract | Document (879 KB) | BibTeX

Improved Sublinear-Time Edit Distance for Preprocessed Strings

Authors: Bringmann, Karl ; Cassis, Alejandro ; Fischer, Nick ; Nakos, Vasileios

Abstract | Document (790 KB) | BibTeX

Polynomial Delay Algorithm for Minimal Chordal Completions

Authors: Brosse, Caroline ; Limouzy, Vincent ; Mary, Arnaud

Abstract | Document (766 KB) | BibTeX

Unique Assembly Verification in Two-Handed Self-Assembly

Authors: Caballero, David ; Gomez, Timothy ; Schweller, Robert ; Wylie, Tim

Abstract | Document (1,221 KB) | BibTeX

Pairwise Reachability Oracles and Preservers Under Failures

Authors: Chakraborty, Diptarka ; Chatterjee, Kushagra ; Choudhary, Keerti

Abstract | Document (913 KB) | BibTeX

Separations Between Combinatorial Measures for Transitive Functions

Authors: Chakraborty, Sourav ; Kayal, Chandrima ; Paraashar, Manaswi

Abstract | Document (853 KB) | BibTeX

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Authors: Chalermsook, Parinya ; Huang, Chien-Chung ; Nanongkai, Danupon ; Saranurak, Thatchaphol ; Sukprasert, Pattara ; Yingchareonthawornchai, Sorrachai

Abstract | Document (928 KB) | BibTeX

Polylogarithmic Sketches for Clustering

Authors: Charikar, Moses ; Waingarten, Erik

Abstract | Document (828 KB) | BibTeX

Approximation Algorithms for Interdiction Problem with Packing Constraints

Authors: Chen, Lin ; Wu, Xiaoyu ; Zhang, Guochuan

Abstract | Document (830 KB) | BibTeX

Online Weighted Cardinality Joint Replenishment Problem with Delay

Authors: Chen, Ryder ; Khatkar, Jahanvi ; Umboh, Seeun William

Abstract | Document (762 KB) | BibTeX

Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond

Authors: Chou, Chi-Ning ; Love, Peter J. ; Sandhu, Juspreet Singh ; Shi, Jonathan

Abstract | Document (806 KB) | BibTeX

Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring

Authors: Christiansen, Aleksander B. G. ; Rotenberg, Eva

Abstract | Document (982 KB) | BibTeX

Expander Random Walks: The General Case and Limitations

Authors: Cohen, Gil ; Minzer, Dor ; Peleg, Shir ; Potechin, Aaron ; Ta-Shma, Amnon

Abstract | Document (782 KB) | BibTeX

LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation

Authors: Cohen, Gil ; Yankovitz, Tal

Abstract | Document (788 KB) | BibTeX

Metastability of the Potts Ferromagnet on Random Regular Graphs

Authors: Coja-Oghlan, Amin ; Galanis, Andreas ; Goldberg, Leslie Ann ; Ravelomanana, Jean Bernoulli ; Štefankovič, Daniel ; Vigoda, Eric

Abstract | Document (807 KB) | BibTeX

On Computing the k-Shortcut Fréchet Distance

Authors: Conradi, Jacobus ; Driemel, Anne

Abstract | Document (1,096 KB) | BibTeX

Streaming Algorithms for Geometric Steiner Forest

Authors: Czumaj, Artur ; Jiang, Shaofeng H.-C. ; Krauthgamer, Robert ; Veselý, Pavel

Abstract | Document (912 KB) | BibTeX

Improved Reconstruction of Random Geometric Graphs

Authors: Dani, Varsha ; Díaz, Josep ; Hayes, Thomas P. ; Moore, Cristopher

Abstract | Document (1,319 KB) | BibTeX

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding

Authors: Das, Debarati ; Kociumaka, Tomasz ; Saha, Barna

Abstract | Document (1,038 KB) | BibTeX

New Additive Approximations for Shortest Paths and Cycles

Authors: Deng, Mingyang ; Kirkpatrick, Yael ; Rong, Victor ; Vassilevska Williams, Virginia ; Zhong, Ziqian

Abstract | Document (678 KB) | BibTeX

One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation

Authors: Deshpande, Amit ; Pratap, Rameshwar

Abstract | Document (430 KB) | Document 2 (729 KB) | BibTeX

Set Membership with Two Classical and Quantum Bit Probes

Authors: Dhamapurkar, Shyam S. ; Pawar, Shubham Vivek ; Radhakrishnan, Jaikumar

Abstract | Document (787 KB) | BibTeX

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets

Authors: Ding, Ming ; Kyng, Rasmus ; Gutenberg, Maximilian Probst ; Zhang, Peng

Abstract | Document (1,135 KB) | BibTeX

Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions

Authors: Ding, Ming ; Kyng, Rasmus ; Zhang, Peng

Abstract | Document (1,047 KB) | BibTeX

High-Probability List-Recovery, and Applications to Heavy Hitters

Authors: Doron, Dean ; Wootters, Mary

Abstract | Document (812 KB) | BibTeX

Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs

Authors: Eden, Talya ; Ron, Dana ; Rosenbaum, Will

Abstract | Document (868 KB) | BibTeX

On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs

Authors: Efthymiou, Charilaos

Abstract | Document (718 KB) | BibTeX

Testability and Local Certification of Monotone Properties in Minor-Closed Classes

Authors: Esperet, Louis ; Norin, Sergey

Abstract | Document (750 KB) | BibTeX

Streaming Submodular Maximization Under Matroid Constraints

Authors: Feldman, Moran ; Liu, Paul ; Norouzi-Fard, Ashkan ; Svensson, Ola ; Zenklusen, Rico

Abstract | Document (1,159 KB) | BibTeX

(Re)packing Equal Disks into Rectangle

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Inamdar, Tanmay ; Zehavi, Meirav

Abstract | Document (886 KB) | BibTeX

Faster Cut Sparsification of Weighted Graphs

Authors: Forster, Sebastian ; de Vos, Tijn

Abstract | Document (829 KB) | BibTeX

Social Distancing Network Creation

Authors: Friedrich, Tobias ; Gawendowicz, Hans ; Lenzner, Pascal ; Melnichenko, Anna

Abstract | Document (1,103 KB) | BibTeX

Approximating Observables Is as Hard as Counting

Authors: Galanis, Andreas ; Štefankovič, Daniel ; Vigoda, Eric

Abstract | Document (768 KB) | BibTeX

The Decision Problem for Perfect Matchings in Dense Hypergraphs

Authors: Gan, Luyining ; Han, Jie

Abstract | Document (848 KB) | BibTeX

Fully Functional Parameterized Suffix Trees in Compact Space

Authors: Ganguly, Arnab ; Shah, Rahul ; Thankachan, Sharma V.

Abstract | Document (908 KB) | BibTeX

The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width

Authors: Ganian, Robert ; Hamm, Thekla ; Korchemna, Viktoriia ; Okrasa, Karolina ; Simonov, Kirill

Abstract | Document (919 KB) | BibTeX

Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)

Authors: Gawrychowski, Paweł ; Pokorski, Karol

Abstract | Document (1,000 KB) | BibTeX

Galloping in Fast-Growth Natural Merge Sorts

Authors: Ghasemi, Elahe ; Jugé, Vincent ; Khalighinejad, Ghazal

Abstract | Document (924 KB) | BibTeX

Tolerant Bipartiteness Testing in Dense Graphs

Authors: Ghosh, Arijit ; Mishra, Gopinath ; Raychaudhury, Rahul ; Sen, Sayantan

Abstract | Document (843 KB) | BibTeX

Homomorphism Tensors and Linear Equations

Authors: Grohe, Martin ; Rattan, Gaurav ; Seppelt, Tim

Abstract | Document (877 KB) | BibTeX

Downsampling for Testing and Learning in Product Distributions

Authors: Harms, Nathaniel ; Yoshida, Yuichi

Abstract | Document (862 KB) | BibTeX

A Fixed-Parameter Algorithm for the Kneser Problem

Authors: Haviv, Ishay

Abstract | Document (743 KB) | BibTeX

Delegation for Search Problems

Authors: Holmgren, Justin ; Lincoln, Andrea ; Rothblum, Ron D.

Abstract | Document (800 KB) | BibTeX

Understanding the Moments of Tabulation Hashing via Chaoses

Authors: Houen, Jakob Bæk Tejs ; Thorup, Mikkel

Abstract | Document (764 KB) | BibTeX

In-Range Farthest Point Queries and Related Problem in High Dimensions

Authors: Huang, Ziyun ; Xu, Jinhui

Abstract | Document (1,297 KB) | BibTeX

Strong Approximations and Irrationality in Financial Networks with Derivatives

Authors: Ioannidis, Stavros D. ; de Keijzer, Bart ; Ventre, Carmine

Abstract | Document (843 KB) | BibTeX

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Authors: Jambulapati, Arun ; Jin, Yujia ; Sidford, Aaron ; Tian, Kevin

Abstract | Document (917 KB) | BibTeX

A PTAS for Packing Hypercubes into a Knapsack

Authors: Jansen, Klaus ; Khan, Arindam ; Lira, Marvin ; Sreenivas, K. V. N.

Abstract | Document (835 KB) | BibTeX

A Faster Interior-Point Method for Sum-Of-Squares Optimization

Authors: Jiang, Shunhua ; Natura, Bento ; Weinstein, Omri

Abstract | Document (910 KB) | BibTeX

Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing

Authors: Khan, Arindam ; Lonkar, Aditya ; Maiti, Arnab ; Sharma, Amatya ; Wiese, Andreas

Abstract | Document (887 KB) | BibTeX

A Study of Weisfeiler-Leman Colorings on Planar Graphs

Authors: Kiefer, Sandra ; Neuen, Daniel

Abstract | Document (857 KB) | BibTeX

Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts

Authors: Kogan, Shimon ; Parter, Merav

Abstract | Document (1,007 KB) | BibTeX

Monotone Arithmetic Complexity of Graph Homomorphism Polynomials

Authors: Komarath, Balagopal ; Pandey, Anurag ; Rahul, Chengot Sankaramenon

Abstract | Document (716 KB) | BibTeX

Exact Recovery Algorithm for Planted Bipartite Graph in Semi-Random Graphs

Authors: Kumar, Akash ; Louis, Anand ; Paul, Rameesh

Abstract | Document (827 KB) | BibTeX

Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game

Authors: Kuszmaul, William ; Narayanan, Shyam

Abstract | Document (706 KB) | BibTeX

Near-Optimal Decremental Hopsets with Applications

Authors: Łącki, Jakub ; Nazari, Yasamin

Abstract | Document (802 KB) | BibTeX

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Authors: Lassota, Alexandra ; Łukasiewicz, Aleksander ; Polak, Adam

Abstract | Document (799 KB) | BibTeX

Parameterized Complexity of Untangling Knots

Authors: Legrand-Duchesne, Clément ; Rai, Ashutosh ; Tancer, Martin

Abstract | Document (1,014 KB) | BibTeX

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

Authors: Liao, Chao ; Chen, Qingyun ; Laekhanukit, Bundit ; Zhang, Yuhao

Abstract | Document (803 KB) | BibTeX

On Lower Bounds of Approximating Parameterized k-Clique

Authors: Lin, Bingkai ; Ren, Xuandi ; Sun, Yican ; Wang, Xiuhan

Abstract | Document (838 KB) | BibTeX

Backdoor Sets on Nowhere Dense SAT

Authors: Lokshtanov, Daniel ; Panolan, Fahad ; Ramanujan, M. S.

Abstract | Document (889 KB) | BibTeX

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

Authors: Lu, Zhenjian ; Oliveira, Igor C. ; Zimand, Marius

Abstract | Document (748 KB) | BibTeX

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument

Authors: Majewski, Konrad ; Masařík, Tomáš ; Novotná, Jana ; Okrasa, Karolina ; Pilipczuk, Marcin ; Rzążewski, Paweł ; Sokołowski, Marek

Abstract | Document (1,229 KB) | BibTeX

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Authors: Mathialagan, Surya ; Vassilevska Williams, Virginia ; Xu, Yinzhan

Abstract | Document (803 KB) | BibTeX

A PTAS for Capacitated Vehicle Routing on Trees

Authors: Mathieu, Claire ; Zhou, Hang

Abstract | Document (802 KB) | BibTeX

Graph Reconstruction from Random Subgraphs

Authors: McGregor, Andrew ; Sengupta, Rik

Abstract | Document (749 KB) | BibTeX

The SDP Value of Random 2CSPs

Authors: Musipatla, Amulya ; O'Donnell, Ryan ; Schramm, Tselil ; Wu, Xinyu

Abstract | Document (864 KB) | BibTeX

Strongly Sublinear Algorithms for Testing Pattern Freeness

Authors: Newman, Ilan ; Varma, Nithin

Abstract | Document (770 KB) | BibTeX

An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space

Authors: Nishimoto, Takaaki ; Kanda, Shunsuke ; Tabei, Yasuo

Abstract | Document (1,556 KB) | BibTeX

Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems

Authors: Papamakarios, Theodoros ; Razborov, Alexander

Abstract | Document (715 KB) | BibTeX

Learning Algorithms Versus Automatability of Frege Systems

Authors: Pich, Ján ; Santhanam, Rahul

Abstract | Document (2,437 KB) | BibTeX

Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures

Authors: Pilipczuk, Michał ; Schirrmacher, Nicole ; Siebertz, Sebastian ; Toruńczyk, Szymon ; Vigny, Alexandre

Abstract | Document (1,020 KB) | BibTeX

A Perfect Sampler for Hypergraph Independent Sets

Authors: Qiu, Guoliang ; Wang, Yanheng ; Zhang, Chihao

Abstract | Document (929 KB) | BibTeX

Threshold Rates of Code Ensembles: Linear Is Best

Authors: Resch, Nicolas ; Yuan, Chen

Abstract | Document (793 KB) | BibTeX

Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel

Authors: Rubinstein, Ittai

Abstract | Document (965 KB) | BibTeX

Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation

Authors: Rubinstein, Aviad ; Zhao, Junyao

Abstract | Document (797 KB) | BibTeX

Approximate Triangle Counting via Sampling and Fast Matrix Multiplication

Authors: Tětek, Jakub

Abstract | Document (849 KB) | BibTeX

Polynomial-Time Approximation of Zero-Free Partition Functions

Authors: Yao, Penghui ; Yin, Yitong ; Zhang, Xinyuan

Abstract | Document (746 KB) | BibTeX

Faster Cut-Equivalent Trees in Simple Graphs

Authors: Zhang, Tianyi

Abstract | Document (878 KB) | BibTeX

Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games

Authors: Allamigeon, Xavier ; Gaubert, Stéphane ; Katz, Ricardo D. ; Skomra, Mateusz

Abstract | Document (862 KB) | BibTeX

Computability of Finite Simplicial Complexes

Authors: Amir, Djamel Eddine ; Hoyrup, Mathieu

Abstract | Document (671 KB) | BibTeX

Unboundedness for Recursion Schemes: A Simpler Type System

Authors: Barozzini, David ; Parys, Paweł ; Wróblewski, Jan

Abstract | Document (783 KB) | BibTeX

Parameterized Safety Verification of Round-Based Shared-Memory Systems

Authors: Bertrand, Nathalie ; Markey, Nicolas ; Sankur, Ocan ; Waldburger, Nicolas

Abstract | Document (986 KB) | BibTeX

Passive Learning of Deterministic Büchi Automata by Combinations of DFAs

Authors: Bohn, León ; Löding, Christof

Abstract | Document (839 KB) | BibTeX

Strategy Synthesis for Global Window PCTL

Authors: Bordais, Benjamin ; Busatto-Gaston, Damien ; Guha, Shibashis ; Raskin, Jean-François

Abstract | Document (1,197 KB) | BibTeX

The Complexity of SPEs in Mean-Payoff Games

Authors: Brice, Léonard ; Raskin, Jean-François ; van den Bogaard, Marie

Abstract | Document (826 KB) | BibTeX

On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games

Authors: Casares, Antonio ; Colcombet, Thomas ; Lehtinen, Karoliina

Abstract | Document (971 KB) | BibTeX

Dynamic Meta-Theorems for Distance and Matching

Authors: Datta, Samir ; Gupta, Chetan ; Jain, Rahul ; Mukherjee, Anish ; Sharma, Vimal Raj ; Tewari, Raghunath

Abstract | Document (838 KB) | BibTeX

Circuit Extraction for ZX-Diagrams Can Be #P-Hard

Authors: de Beaudrap, Niel ; Kissinger, Aleks ; van de Wetering, John

Abstract | Document (905 KB) | BibTeX

Hiding Pebbles When the Output Alphabet Is Unary

Authors: Douéneau-Tabot, Gaëtan

Abstract | Document (775 KB) | BibTeX

Regular Expressions for Tree-Width 2 Graphs

Authors: Doumane, Amina

Abstract | Document (833 KB) | BibTeX

A Generic Solution to Register-Bounded Synthesis with an Application to Discrete Orders

Authors: Exibard, Léo ; Filiot, Emmanuel ; Khalimov, Ayrat

Abstract | Document (846 KB) | BibTeX

Twin-Width and Types

Authors: Gajarský, Jakub ; Pilipczuk, Michał ; Przybyszewski, Wojciech ; Toruńczyk, Szymon

Abstract | Document (1,077 KB) | BibTeX

Reachability in Bidirected Pushdown VASS

Authors: Ganardi, Moses ; Majumdar, Rupak ; Pavlogiannis, Andreas ; Schütze, Lia ; Zetzsche, Georg

Abstract | Document (881 KB) | BibTeX

Distributed Controller Synthesis for Deadlock Avoidance

Authors: Gimbert, Hugo ; Mascle, Corto ; Muscholl, Anca ; Walukiewicz, Igor

Abstract | Document (727 KB) | BibTeX

Lower Bounds for Unambiguous Automata via Communication Complexity

Authors: Göös, Mika ; Kiefer, Stefan ; Yuan, Weiqiang

Abstract | Document (771 KB) | BibTeX

Satisfiability Problems for Finite Groups

Authors: Idziak, Paweł M. ; Kawałek, Piotr ; Krzaczkowski, Jacek ; Weiß, Armin

Abstract | Document (915 KB) | BibTeX

Linearly Ordered Colourings of Hypergraphs

Authors: Nakajima, Tamio-Vesa ; Živný, Stanislav

Abstract | Document (879 KB) | BibTeX

The Variance-Penalized Stochastic Shortest Path Problem

Authors: Piribauer, Jakob ; Sankur, Ocan ; Baier, Christel

Abstract | Document (797 KB) | BibTeX

Functions and References in the Pi-Calculus: Full Abstraction and Proof Techniques

Authors: Prebet, Enguerrand

Abstract | Document (804 KB) | BibTeX

What Can Oracles Teach Us About the Ultimate Fate of Life?

Authors: Salo, Ville ; Törmä, Ilkka

Abstract | Document (1,149 KB) | BibTeX

Processes Parametrised by an Algebraic Theory

Authors: Schmid, Todd ; Różowski, Wojciech ; Rot, Jurriaan ; Silva, Alexandra

Abstract | Document (947 KB) | BibTeX

The Dimension Spectrum Conjecture for Planar Lines

Authors: Stull, D. M.

Abstract | Document (684 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)