Portal - ICALP 2020

ICALP 2020	July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) Artur Czumaj and Anuj Dawar and Emanuela Merelli (Eds.)
ISBN 978-3-95977-138-2, LIPICS Vol. 168	ISSN 1868-8969

Additional Information

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

Authors

Chakraborty, Diptarka

Chalopin, Jérémie

Chan, Timothy F. N.

Charalampopoulos, Panagiotis

Christodoulou, George

Fichtenberger, Hendrik

Giannakopoulos, Yiannis

Guruswami, Venkatesan

Koumoutsos, Grigorios

Mousavi, Mohammad Reza

Nezhadi, Seyed Sajjad

Ngo, Hung Q.

Nguyen, Huy L.

Nguyễn, Lê Thành Dũng

Patsilinakos, Panagiotis

Raskin, Jean-François

Stoienescu, Paul-Ioan

Thilikos, Dimitrios M.

Thinniyam, Ramanathan S.

Vassilevska Williams, Virginia

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Czumaj, Artur ; Dawar, Anuj ; Merelli, Emanuela

Abstract | Document (484 KB) | BibTeX

An Incentive Analysis of Some Bitcoin Fee Designs (Invited Talk)

Authors: Yao, Andrew Chi chih

Abstract | Document (448 KB) | BibTeX

Sketching Graphs and Combinatorial Optimization (Invited Talk)

Authors: Krauthgamer, Robert

Abstract | Document (169 KB) | BibTeX

How to Play in Infinite MDPs (Invited Talk)

Authors: Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa ; Totzke, Patrick ; Wojtczak, Dominik

Abstract | Document (560 KB) | BibTeX

Scheduling Lower Bounds via AND Subset Sum

Authors: Abboud, Amir ; Bringmann, Karl ; Hermelin, Danny ; Shabtay, Dvir

Abstract | Document (537 KB) | BibTeX

On the Fine-Grained Complexity of Parity Problems

Authors: Abboud, Amir ; Feller, Shon ; Weimann, Oren

Abstract | Document (810 KB) | BibTeX

Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints

Authors: Alaluf, Naor ; Ene, Alina ; Feldman, Moran ; Nguyen, Huy L. ; Suh, Andrew

Abstract | Document (633 KB) | BibTeX

Dynamic Averaging Load Balancing on Cycles

Authors: Alistarh, Dan ; Nadiradze, Giorgi ; Sabour, Amirmojtaba

Abstract | Document (765 KB) | BibTeX

Asynchronous Majority Dynamics in Preferential Attachment Trees

Authors: Bahrani, Maryam ; Immorlica, Nicole ; Mohan, Divyarthi ; Weinberg, S. Matthew

Abstract | Document (552 KB) | BibTeX

The Power of Many Samples in Query Complexity

Authors: Bassilakis, Andrew ; Drucker, Andrew ; Göös, Mika ; Hu, Lunjia ; Ma, Weiyun ; Tan, Li-Yang

Abstract | Document (599 KB) | BibTeX

Medians in Median Graphs and Their Cube Complexes in Linear Time

Authors: Bénéteau, Laurine ; Chalopin, Jérémie ; Chepoi, Victor ; Vaxès, Yann

Abstract | Document (711 KB) | BibTeX

Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models

Authors: Bera, Suman K. ; Chakrabarti, Amit ; Ghosh, Prantar

Abstract | Document (666 KB) | BibTeX

Improved Bounds for Matching in Random-Order Streams

Authors: Bernstein, Aaron

Abstract | Document (591 KB) | BibTeX

An Optimal Algorithm for Online Multiple Knapsack

Authors: Bienkowski, Marcin ; Pacut, Maciej ; Piecuch, Krzysztof

Abstract | Document (731 KB) | BibTeX

Space Efficient Construction of Lyndon Arrays in Linear Time

Authors: Bille, Philip ; Ellert, Jonas ; Fischer, Johannes ; Gørtz, Inge Li ; Kurpicz, Florian ; Munro, J. Ian ; Rotenberg, Eva

Abstract | Document (631 KB) | BibTeX

New Fault Tolerant Subset Preservers

Authors: Bodwin, Greg ; Choudhary, Keerti ; Parter, Merav ; Shahar, Noa

Abstract | Document (621 KB) | BibTeX

Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

Authors: Bougeret, Marin ; Jansen, Bart M. P. ; Sau, Ignasi

Abstract | Document (1,261 KB) | BibTeX

The Complexity of Promise SAT on Non-Boolean Domains

Authors: Brandts, Alex ; Wrochna, Marcin ; Živný, Stanislav

Abstract | Document (542 KB) | BibTeX

A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions

Authors: Brankovic, Milutin ; Grujic, Nikola ; van Renssen, André ; Seybold, Martin P.

Abstract | Document (905 KB) | BibTeX

Faster Minimization of Tardy Processing Time on a Single Machine

Authors: Bringmann, Karl ; Fischer, Nick ; Hermelin, Danny ; Shabtay, Dvir ; Wellnitz, Philip

Abstract | Document (496 KB) | BibTeX

Fréchet Distance for Uncertain Curves

Authors: Buchin, Kevin ; Fan, Chenglin ; Löffler, Maarten ; Popov, Aleksandr ; Raichel, Benjamin ; Roeloffzen, Marcel

Abstract | Document (750 KB) | BibTeX

Counting Homomorphisms in Plain Exponential Time

Authors: Bulatov, Andrei A. ; Dadsetan, Amineh

Abstract | Document (568 KB) | BibTeX

From Holant to Quantum Entanglement and Back

Authors: Cai, Jin-Yi ; Fu, Zhiguo ; Shao, Shuai

Abstract | Document (621 KB) | BibTeX

Counting Perfect Matchings and the Eight-Vertex Model

Authors: Cai, Jin-Yi ; Liu, Tianyu

Abstract | Document (1,150 KB) | BibTeX

Roundtrip Spanners with (2k-1) Stretch

Authors: Cen, Ruoxu ; Duan, Ran ; Gu, Yong

Abstract | Document (488 KB) | BibTeX

New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures

Authors: Chakraborty, Diptarka ; Choudhary, Keerti

Abstract | Document (650 KB) | BibTeX

Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming

Authors: Chan, Timothy F. N. ; Cooper, Jacob W. ; Koutecký, Martin ; Král', Daniel ; Pekárková, Kristýna

Abstract | Document (540 KB) | BibTeX

Dynamic Longest Common Substring in Polylogarithmic Time

Authors: Charalampopoulos, Panagiotis ; Gawrychowski, Paweł ; Pokorski, Karol

Abstract | Document (678 KB) | BibTeX

Improved Black-Box Constructions of Composable Secure Computation

Authors: Chatterjee, Rohit ; Liang, Xiao ; Pandey, Omkant

Abstract | Document (619 KB) | BibTeX

Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs

Authors: Chechik, Shiri ; Nechushtan, Moran

Abstract | Document (881 KB) | BibTeX

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

Authors: Chen, Yu ; Kannan, Sampath ; Khanna, Sanjeev

Abstract | Document (536 KB) | BibTeX

Computational Complexity of the α-Ham-Sandwich Problem

Authors: Chiu, Man-Kwun ; Choudhary, Aruni ; Mulzer, Wolfgang

Abstract | Document (731 KB) | BibTeX

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Authors: Christodoulou, George ; Gairing, Martin ; Giannakopoulos, Yiannis ; Poças, Diogo ; Waldmann, Clara

Abstract | Document (587 KB) | BibTeX

On Packing Low-Diameter Spanning Trees

Authors: Chuzhoy, Julia ; Parter, Merav ; Tan, Zihan

Abstract | Document (634 KB) | BibTeX

Online Two-Dimensional Load Balancing

Authors: Cohen, Ilan ; Im, Sungjin ; Panigrahi, Debmalya

Abstract | Document (602 KB) | BibTeX

Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph

Authors: Dalirrooyfard, Mina ; Vassilevska Williams, Virginia

Abstract | Document (774 KB) | BibTeX

Symmetric Arithmetic Circuits

Authors: Dawar, Anuj ; Wilsenach, Gregory

Abstract | Document (589 KB) | BibTeX

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

Authors: De, Anindya ; Khanna, Sanjeev ; Li, Huan ; Nikpey, Hesam

Abstract | Document (637 KB) | BibTeX

Tree Polymatrix Games Are PPAD-Hard

Authors: Deligkas, Argyrios ; Fearnley, John ; Savani, Rahul

Abstract | Document (621 KB) | BibTeX

Spectral Sparsification via Bounded-Independence Sampling

Authors: Doron, Dean ; Murtagh, Jack ; Vadhan, Salil ; Zuckerman, David

Abstract | Document (580 KB) | BibTeX

Hard Problems on Random Graphs

Authors: Dreier, Jan ; Lotze, Henri ; Rossmanith, Peter

Abstract | Document (577 KB) | BibTeX

A Scaling Algorithm for Weighted f-Factors in General Graphs

Authors: Duan, Ran ; He, Haoqing ; Zhang, Tianyi

Abstract | Document (643 KB) | BibTeX

The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem

Authors: Dughmi, Shaddin

Abstract | Document (529 KB) | BibTeX

Extending Partial 1-Planar Drawings

Authors: Eiben, Eduard ; Ganian, Robert ; Hamm, Thekla ; Klute, Fabian ; Nöllenburg, Martin

Abstract | Document (850 KB) | BibTeX

How to Hide a Clique?

Authors: Feige, Uriel ; Grinberg, Vadim

Abstract | Document (457 KB) | BibTeX

Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time

Authors: Fichtenberger, Hendrik ; Gao, Mingze ; Peng, Pan

Abstract | Document (551 KB) | BibTeX

A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems

Authors: Fielbaum, Andrés ; Morales, Ignacio ; Verschae, José

Abstract | Document (490 KB) | BibTeX

Scattering and Sparse Partitions, and Their Applications

Authors: Filtser, Arnold

Abstract | Document (735 KB) | BibTeX

Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic

Authors: Filtser, Arnold ; Filtser, Omrit ; Katz, Matthew J.

Abstract | Document (586 KB) | BibTeX

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds

Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Mihajlin, Ivan ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (3,332 KB) | BibTeX

Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games

Authors: Fotakis, Dimitris ; Kandiros, Vardis ; Lianeas, Thanasis ; Mouzakis, Nikos ; Patsilinakos, Panagiotis ; Skoulakis, Stratis

Abstract | Document (865 KB) | BibTeX

The Online Min-Sum Set Cover Problem

Authors: Fotakis, Dimitris ; Kavouras, Loukas ; Koumoutsos, Grigorios ; Skoulakis, Stratis ; Vardas, Manolis

Abstract | Document (479 KB) | BibTeX

Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth

Authors: Fürer, Martin ; Hoppen, Carlos ; Trevisan, Vilmar

Abstract | Document (536 KB) | BibTeX

Counting Solutions to Random CNF Formulas

Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Guo, Heng ; Yang, Kuan

Abstract | Document (533 KB) | BibTeX

Robust Algorithms for TSP and Steiner Tree

Authors: Ganesh, Arun ; Maggs, Bruce M. ; Panigrahi, Debmalya

Abstract | Document (580 KB) | BibTeX

Cryptographic Reverse Firewalls for Interactive Proof Systems

Authors: Ganesh, Chaya ; Magri, Bernardo ; Venturi, Daniele

Abstract | Document (532 KB) | BibTeX

Robust Algorithms Under Adversarial Injections

Authors: Garg, Paritosh ; Kale, Sagar ; Rohwedder, Lars ; Svensson, Ola

Abstract | Document (575 KB) | BibTeX

Minimum Cut in O(m log² n) Time

Authors: Gawrychowski, Paweł ; Mozes, Shay ; Weimann, Oren

Abstract | Document (601 KB) | BibTeX

Sparse Recovery for Orthogonal Polynomial Transforms

Authors: Gilbert, Anna ; Gu, Albert ; Ré, Christopher ; Rudra, Atri ; Wootters, Mary

Abstract | Document (593 KB) | BibTeX

Hitting Long Directed Cycles Is Fixed-Parameter Tractable

Authors: Göke, Alexander ; Marx, Dániel ; Mnich, Matthias

Abstract | Document (638 KB) | BibTeX

On the Central Levels Problem

Authors: Gregor, Petr ; Mička, Ondřej ; Mütze, Torsten

Abstract | Document (854 KB) | BibTeX

Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization

Authors: Gurjar, Rohit ; Rathi, Rajat

Abstract | Document (520 KB) | BibTeX

d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors

Authors: Guruswami, Venkatesan ; Sandeep, Sai

Abstract | Document (475 KB) | BibTeX

Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares

Authors: Hakoniemi, Tuomas

Abstract | Document (442 KB) | BibTeX

Active Learning a Convex Body in Low Dimensions

Authors: Har-Peled, Sariel ; Jones, Mitchell ; Rahul, Saladi

Abstract | Document (732 KB) | BibTeX

Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity

Authors: Hirai, Hiroshi ; Ikeda, Motoki

Abstract | Document (575 KB) | BibTeX

A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights

Authors: Govorov, Artem ; Cai, Jin-Yi ; Dyer, Martin

Abstract | Document (686 KB) | BibTeX

Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs

Authors: Izumi, Taisuke ; Otachi, Yota

Abstract | Document (737 KB) | BibTeX

Scheduling in the Random-Order Model

Authors: Albers, Susanne ; Janke, Maximilian

Abstract | Document (486 KB) | BibTeX

Online Algorithms for Weighted Paging with Predictions

Authors: Jiang, Zhihao ; Panigrahi, Debmalya ; Sun, Kevin

Abstract | Document (571 KB) | BibTeX

Popular Matchings with One-Sided Bias

Authors: Kavitha, Telikepalli

Abstract | Document (552 KB) | BibTeX

Obviously Strategyproof Single-Minded Combinatorial Auctions

Authors: de Keijzer, Bart ; Kyropoulou, Maria ; Ventre, Carmine

Abstract | Document (531 KB) | BibTeX

Knapsack Secretary with Bursty Adversary

Authors: Kesselheim, Thomas ; Molinaro, Marco

Abstract | Document (615 KB) | BibTeX

The Iteration Number of Colour Refinement

Authors: Kiefer, Sandra ; McKay, Brendan D.

Abstract | Document (582 KB) | BibTeX

Towards Optimal Set-Disjointness and Set-Intersection Data Structures

Authors: Kopelowitz, Tsvi ; Vassilevska Williams, Virginia

Abstract | Document (635 KB) | BibTeX

Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Authors: Korman, Matias ; van Renssen, André ; Roeloffzen, Marcel ; Staals, Frank

Abstract | Document (744 KB) | BibTeX

Polytopes, Lattices, and Spherical Codes for the Nearest Neighbor Problem

Authors: Laarhoven, Thijs

Abstract | Document (873 KB) | BibTeX

Deterministic Sparse Fourier Transform with an 𝓁_{∞} Guarantee

Authors: Li, Yi ; Nakos, Vasileios

Abstract | Document (542 KB) | BibTeX

Faster Random k-CNF Satisfiability

Authors: Lincoln, Andrea ; Yedidia, Adam

Abstract | Document (633 KB) | BibTeX

Succinct Filters for Sets of Unknown Sizes

Authors: Liu, Mingmou ; Yin, Yitong ; Yu, Huacheng

Abstract | Document (546 KB) | BibTeX

A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion

Authors: Lokshtanov, Daniel ; Misra, Pranabendu ; Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket

Abstract | Document (678 KB) | BibTeX

Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem

Authors: Chechik, Shiri ; Magen, Ofer

Abstract | Document (563 KB) | BibTeX

Quantum Distributed Complexity of Set Disjointness on a Line

Authors: Magniez, Frédéric ; Nayak, Ashwin

Abstract | Document (1,787 KB) | BibTeX

Can Verifiable Delay Functions Be Based on Random Oracles?

Authors: Mahmoody, Mohammad ; Smith, Caleb ; Wu, David J.

Abstract | Document (522 KB) | BibTeX

On the Two-Dimensional Knapsack Problem for Convex Polygons

Authors: Merino, Arturo ; Wiese, Andreas

Abstract | Document (635 KB) | BibTeX

Proportionally Fair Clustering Revisited

Authors: Micha, Evi ; Shah, Nisarg

Abstract | Document (508 KB) | BibTeX

Breaking the Barrier of 2 for the Storage Allocation Problem

Authors: Mömke, Tobias ; Wiese, Andreas

Abstract | Document (599 KB) | BibTeX

On the Complexity of Zero Gap MIP*

Authors: Mousavi, Hamoon ; Nezhadi, Seyed Sajjad ; Yuen, Henry

Abstract | Document (541 KB) | BibTeX

Hypergraph Isomorphism for Groups with Restricted Composition Factors

Authors: Neuen, Daniel

Abstract | Document (557 KB) | BibTeX

On Solving (Non)commutative Weighted Edmonds' Problem

Authors: Oki, Taihei

Abstract | Document (470 KB) | BibTeX

A General Stabilization Bound for Influence Propagation in Graphs

Authors: Papp, Pál András ; Wattenhofer, Roger

Abstract | Document (491 KB) | BibTeX

Network-Aware Strategies in Financial Systems

Authors: Papp, Pál András ; Wattenhofer, Roger

Abstract | Document (442 KB) | BibTeX

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Authors: Pitassi, Toniann ; Shirley, Morgan ; Watson, Thomas

Abstract | Document (611 KB) | BibTeX

A Spectral Bound on Hypergraph Discrepancy

Authors: Potukuchi, Aditya

Abstract | Document (532 KB) | BibTeX

Faster Dynamic Range Mode

Authors: Sandlund, Bryce ; Xu, Yinzhan

Abstract | Document (515 KB) | BibTeX

An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes

Authors: Sau, Ignasi ; Stamoulis, Giannos ; Thilikos, Dimitrios M.

Abstract | Document (951 KB) | BibTeX

Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems

Authors: Shao, Shuai ; Sun, Yuxin

Abstract | Document (572 KB) | BibTeX

Quasi-Majority Functional Voting on Expander Graphs

Authors: Shimizu, Nobutaka ; Shiraga, Takeharu

Abstract | Document (661 KB) | BibTeX

Property Testing of LP-Type Problems

Authors: Epstein, Rogers ; Silwal, Sandeep

Abstract | Document (556 KB) | BibTeX

Lower Bounds for Dynamic Distributed Task Allocation

Authors: Su, Hsin-Hao ; Wein, Nicole

Abstract | Document (430 KB) | BibTeX

On the Degree of Boolean Functions as Polynomials over ℤ_m

Authors: Sun, Xiaoming ; Sun, Yuan ; Wang, Jiaheng ; Wu, Kewen ; Xia, Zhiyu ; Zheng, Yufan

Abstract | Document (554 KB) | BibTeX

On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems

Authors: Wahlström, Magnus

Abstract | Document (530 KB) | BibTeX

Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis

Authors: Weiß, Armin

Abstract | Document (655 KB) | BibTeX

Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth

Authors: Wiebking, Daniel

Abstract | Document (579 KB) | BibTeX

Parameterized Inapproximability for Steiner Orientation by Gap Amplification

Authors: Włodarczyk, Michał

Abstract | Document (799 KB) | BibTeX

Near-Optimal Algorithm for Constructing Greedy Consensus Tree

Authors: Wu, Hongxun

Abstract | Document (525 KB) | BibTeX

Decision Problems in Information Theory

Authors: Abo Khamis, Mahmoud ; Kolaitis, Phokion G. ; Ngo, Hung Q. ; Suciu, Dan

Abstract | Document (702 KB) | BibTeX

Invariants for Continuous Linear Dynamical Systems

Authors: Almagor, Shaull ; Kelmendi, Edon ; Ouaknine, Joël ; Worrell, James

Abstract | Document (553 KB) | BibTeX

On Higher-Order Cryptography

Authors: Barak, Boaz ; Crubillé, Raphaëlle ; Dal Lago, Ugo

Abstract | Document (640 KB) | BibTeX

Cost Automata, Safe Schemes, and Downward Closures

Authors: Barozzini, David ; Clemente, Lorenzo ; Colcombet, Thomas ; Parys, Paweł

Abstract | Document (574 KB) | BibTeX

Sensitive Instances of the Constraint Satisfaction Problem

Authors: Barto, Libor ; Kozik, Marcin ; Tan, Johnson ; Valeriote, Matt

Abstract | Document (572 KB) | BibTeX

The Complexity of Bounded Context Switching with Dynamic Thread Creation

Authors: Baumann, Pascal ; Majumdar, Rupak ; Thinniyam, Ramanathan S. ; Zetzsche, Georg

Abstract | Document (651 KB) | BibTeX

Two Variable Logic with Ultimately Periodic Counting

Authors: Benedikt, Michael ; Kostylev, Egor V. ; Tan, Tony

Abstract | Document (675 KB) | BibTeX

Single-Use Automata and Transducers for Infinite Alphabets

Authors: Bojańczyk, Mikołaj ; Stefański, Rafał

Abstract | Document (1,125 KB) | BibTeX

Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Authors: Bostan, Alin ; Carayol, Arnaud ; Koechlin, Florent ; Nicaud, Cyril

Abstract | Document (582 KB) | BibTeX

On the Size of Finite Rational Matrix Semigroups

Authors: Bumpus, Georgina ; Haase, Christoph ; Kiefer, Stefan ; Stoienescu, Paul-Ioan ; Tanner, Jonathan

Abstract | Document (673 KB) | BibTeX

Rational Subsets of Baumslag-Solitar Groups

Authors: Cadilhac, Michaël ; Chistikov, Dmitry ; Zetzsche, Georg

Abstract | Document (548 KB) | BibTeX

On Polynomial Recursive Sequences

Authors: Cadilhac, Michaël ; Mazowiecki, Filip ; Paperman, Charles ; Pilipczuk, Michał ; Sénizergues, Géraud

Abstract | Document (724 KB) | BibTeX

A Recipe for Quantum Graphical Languages

Authors: Carette, Titouan ; Jeandel, Emmanuel

Abstract | Document (602 KB) | BibTeX

On the Power of Ordering in Linear Arithmetic Theories

Authors: Chistikov, Dmitry ; Haase, Christoph

Abstract | Document (740 KB) | BibTeX

The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms

Authors: Ciobanu, Laura ; Logan, Alan D.

Abstract | Document (554 KB) | BibTeX

Timed Games and Deterministic Separability

Authors: Clemente, Lorenzo ; Lasota, Sławomir ; Piórkowski, Radosław

Abstract | Document (619 KB) | BibTeX

Dynamic Complexity of Reachability: How Many Changes Can We Handle?

Authors: Datta, Samir ; Kumar, Pankaj ; Mukherjee, Anish ; Tawari, Anuj ; Vortmeier, Nils ; Zeume, Thomas

Abstract | Document (579 KB) | BibTeX

The Strahler Number of a Parity Game

Authors: Daviaud, Laure ; Jurdziński, Marcin ; Thejaswini, K. S.

Abstract | Document (507 KB) | BibTeX

On the Structure of Solution Sets to Regular Word Equations

Authors: Day, Joel D. ; Manea, Florin

Abstract | Document (585 KB) | BibTeX

From Linear to Additive Cellular Automata

Authors: Dennunzio, Alberto ; Formenti, Enrico ; Grinberg, Darij ; Margara, Luciano

Abstract | Document (516 KB) | BibTeX

The Complexity of Knapsack Problems in Wreath Products

Authors: Figelius, Michael ; Ganardi, Moses ; Lohrey, Markus ; Zetzsche, Georg

Abstract | Document (600 KB) | BibTeX

The Adversarial Stackelberg Value in Quantitative Games

Authors: Filiot, Emmanuel ; Gentilini, Raffaella ; Raskin, Jean-François

Abstract | Document (632 KB) | BibTeX

The Topology of Local Computing in Networks

Authors: Fraigniaud, Pierre ; Paz, Ami

Abstract | Document (1,117 KB) | BibTeX

The Complexity of Verifying Loop-Free Programs as Differentially Private

Authors: Gaboardi, Marco ; Nissim, Kobbi ; Purser, David

Abstract | Document (704 KB) | BibTeX

Logical Characterisation of Hybrid Conformance

Authors: Gazda, Maciej ; Mousavi, Mohammad Reza

Abstract | Document (688 KB) | BibTeX

Hrushovski’s Encoding and ω-Categorical CSP Monsters

Authors: Gillibert, Pierre ; Jonušas, Julius ; Kompatscher, Michael ; Mottet, Antoine ; Pinsker, Michael

Abstract | Document (632 KB) | BibTeX

Descriptive Complexity on Non-Polish Spaces II

Authors: Hoyrup, Mathieu

Abstract | Document (531 KB) | BibTeX

On Decidability of Time-Bounded Reachability in CTMDPs

Authors: Majumdar, Rupak ; Salamati, Mahmoud ; Soudjani, Sadegh

Abstract | Document (637 KB) | BibTeX

When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?

Authors: Maneth, Sebastian ; Seidl, Helmut

Abstract | Document (545 KB) | BibTeX

Implicit Automata in Typed λ-Calculi I: Aperiodicity in a Non-Commutative Logic

Authors: Nguyễn, Lê Thành Dũng ; Pradic, Pierre

Abstract | Document (605 KB) | BibTeX

Computing Measures of Weak-MSO Definable Sets of Trees

Authors: Niwiński, Damian ; Przybyłko, Marcin ; Skrzypczak, Michał

Abstract | Document (560 KB) | BibTeX

Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata

Authors: Paul, Erik

Abstract | Document (581 KB) | BibTeX

On Skolem-Hardness and Saturation Points in Markov Decision Processes

Authors: Piribauer, Jakob ; Baier, Christel

Abstract | Document (609 KB) | BibTeX

The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem

Authors: Remscrim, Zachary

Abstract | Document (522 KB) | BibTeX

Hardness Results for Constant-Free Pattern Languages and Word Equations

Authors: Saarela, Aleksi

Abstract | Document (415 KB) | BibTeX

Bisimulation Equivalence of Pushdown Automata Is Ackermann-Complete

Authors: Zhang, Wenbo ; Yin, Qiang ; Long, Huan ; Xu, Xian

Abstract | Document (618 KB) | BibTeX

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

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)