Portal - ICALP 2021

ICALP 2021	July 12-16, 2021, Glasgow, Scotland (Virtual Conference)
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) Nikhil Bansal and Emanuela Merelli and James Worrell (Eds.)
ISBN 978-3-95977-195-5, LIPICS Vol. 198	ISSN 1868-8969

Additional Information

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

Authors

Chakrabarty, Deeparnab

Chan, Timothy M.

Charalampopoulos, Panagiotis

Chatterjee, Krishnendu

Christodoulou, George

D'Angelo, Gianlorenzo

Fredslund-Hansen, Viktor

Freydenberger, Dominik D.

Guruswami, Venkatesan

Gutenberg, Maximilian Probst

Gärtner, Bernd

Göbel, Andreas

Haeupler, Bernhard

Hajiaghayi, MohammadTaghi

Hamm, Thekla

Hansen, Kristoffer Arnsfelt

Hartmann, Maria

Haslebacher, Sebastian

Henzinger, Monika

Hershkowitz, D. Ellis

Kawarabayashi, Ken-ichi

Kontogeorgiou, George

Korhonen, Tuukka

Kostopanagiotis, Panagiotis

Lagodzinski, J. A. Gregor

Mitzenmacher, Michael

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

Reynier, Pierre-Alain

Saxena, Raghuvansh R.

Starikovskaya, Tatiana

Thankachan, Sharma V.

Thomassé, Stéphan

Thompson, Kevin

Tomescu, Alexandru I.

Vassilevska Williams, Virginia

Wulff-Nilsen, Christian

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Bansal, Nikhil ; Merelli, Emanuela ; Worrell, James

Abstract | Document (768 KB) | BibTeX

From Verification to Causality-Based Explications (Invited Talk)

Authors: Baier, Christel ; Dubslaff, Clemens ; Funke, Florian ; Jantsch, Simon ; Majumdar, Rupak ; Piribauer, Jakob ; Ziemek, Robin

Abstract | Document (815 KB) | BibTeX

Symmetries and Complexity (Invited Talk)

Authors: Bulatov, Andrei A.

Abstract | Document (815 KB) | BibTeX

Distributed Subgraph Finding: Progress and Challenges (Invited Talk)

Authors: Censor-Hillel, Keren

Abstract | Document (667 KB) | BibTeX

Error Resilient Space Partitioning (Invited Talk)

Authors: Dunkelman, Orr ; Geyzel, Zeev ; Keller, Chaya ; Keller, Nathan ; Ronen, Eyal ; Shamir, Adi ; Tessler, Ran J.

Abstract | Document (765 KB) | BibTeX

Algebraic Proof Systems (Invited Talk)

Authors: Pitassi, Toniann

Abstract | Document (287 KB) | BibTeX

A Very Sketchy Talk (Invited Talk)

Authors: Woodruff, David P.

Abstract | Document (531 KB) | BibTeX

Fine-Grained Hardness for Edit Distance to a Fixed Sequence

Authors: Abboud, Amir ; Vassilevska Williams, Virginia

Abstract | Document (672 KB) | BibTeX

Local Approximations of the Independent Set Polynomial

Authors: Achlioptas, Dimitris ; Zampetakis, Kostas

Abstract | Document (826 KB) | BibTeX

Almost-Linear-Time Weighted 𝓁_p-Norm Solvers in Slightly Dense Graphs via Sparsification

Authors: Adil, Deeksha ; Bullins, Brian ; Kyng, Rasmus ; Sachdeva, Sushant

Abstract | Document (867 KB) | BibTeX

An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D

Authors: Agarwal, Pankaj K. ; Steiger, Alex

Abstract | Document (1,380 KB) | BibTeX

Dynamic Enumeration of Similarity Joins

Authors: Agarwal, Pankaj K. ; Hu, Xiao ; Sintos, Stavros ; Yang, Jun

Abstract | Document (971 KB) | BibTeX

Faster Algorithms for Bounded Tree Edit Distance

Authors: Akmal, Shyan ; Jin, Ce

Abstract | Document (811 KB) | BibTeX

Improved Approximation for Longest Common Subsequence over Small Alphabets

Authors: Akmal, Shyan ; Vassilevska Williams, Virginia

Abstract | Document (719 KB) | BibTeX

Efficient Splitting of Necklaces

Authors: Alon, Noga ; Graur, Andrei

Abstract | Document (680 KB) | BibTeX

Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case

Authors: Anders, Markus ; Schweitzer, Pascal ; Wetzels, Florian

Abstract | Document (831 KB) | BibTeX

Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms

Authors: Anders, Markus ; Schweitzer, Pascal

Abstract | Document (785 KB) | BibTeX

Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop

Authors: Antoniadis, Antonios ; Englert, Matthias ; Matsakis, Nicolaos ; Veselý, Pavel

Abstract | Document (791 KB) | BibTeX

Relaxed Locally Correctable Codes with Improved Parameters

Authors: Asadi, Vahid R. ; Shinkar, Igor

Abstract | Document (621 KB) | BibTeX

Beating Two-Thirds For Random-Order Streaming Matching

Authors: Assadi, Sepehr ; Behnezhad, Soheil

Abstract | Document (1,366 KB) | BibTeX

Optimal Fine-Grained Hardness of Approximation of Linear Equations

Authors: Bafna, Mitali ; Vyas, Nikhil

Abstract | Document (794 KB) | BibTeX

Revisiting Priority k-Center: Fairness and Outliers

Authors: Bajpai, Tanvi ; Chakrabarty, Deeparnab ; Chekuri, Chandra ; Negahbani, Maryam

Abstract | Document (828 KB) | BibTeX

The Submodular Santa Claus Problem in the Restricted Assignment Case

Authors: Bamas, Etienne ; Garg, Paritosh ; Rohwedder, Lars

Abstract | Document (670 KB) | BibTeX

On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

Authors: Bandyapadhyay, Sayan ; Fomin, Fedor V. ; Simonov, Kirill

Abstract | Document (803 KB) | BibTeX

Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem

Authors: Batziou, Eleni ; Hansen, Kristoffer Arnsfelt ; Høgh, Kasper

Abstract | Document (825 KB) | BibTeX

How to Send a Real Number Using a Single Bit (And Some Shared Randomness)

Authors: Ben Basat, Ran ; Mitzenmacher, Michael ; Vargaftik, Shay

Abstract | Document (908 KB) | BibTeX

Using a Geometric Lens to Find k Disjoint Shortest Paths

Authors: Bentert, Matthias ; Nichterlein, André ; Renken, Malte ; Zschoche, Philipp

Abstract | Document (929 KB) | BibTeX

Deterministic Rounding of Dynamic Fractional Matchings

Authors: Bhattacharya, Sayan ; Kiss, Peter

Abstract | Document (712 KB) | BibTeX

Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times

Authors: Bienkowski, Marcin ; Kraska, Artur ; Liu, Hsiang-Hsuan

Abstract | Document (1,007 KB) | BibTeX

Counting Short Vector Pairs by Inner Product and Relations to the Permanent

Authors: Björklund, Andreas ; Kaski, Petteri

Abstract | Document (812 KB) | BibTeX

Learning Stochastic Decision Trees

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

Abstract | Document (851 KB) | BibTeX

Breaking O(nr) for Matroid Intersection

Authors: Blikstad, Joakim

Abstract | Document (875 KB) | BibTeX

Graph Similarity and Homomorphism Densities

Authors: Böker, Jan

Abstract | Document (785 KB) | BibTeX

Direct Sum and Partitionability Testing over General Groups

Authors: Bogdanov, Andrej ; Prakriya, Gautam

Abstract | Document (877 KB) | BibTeX

4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}

Authors: Bonnet, Édouard

Abstract | Document (856 KB) | BibTeX

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

Authors: Bonnet, Édouard ; Geniet, Colin ; Kim, Eun Jung ; Thomassé, Stéphan ; Watrigant, Rémi

Abstract | Document (928 KB) | BibTeX

Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Authors: Bouchard, Sébastien ; Dieudonné, Yoann ; Labourel, Arnaud ; Pelc, Andrzej

Abstract | Document (823 KB) | BibTeX

Conditional Dichotomy of Boolean Ordered Promise CSPs

Authors: Brakensiek, Joshua ; Guruswami, Venkatesan ; Sandeep, Sai

Abstract | Document (739 KB) | BibTeX

Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials

Authors: Brand, Cornelius ; Pratt, Kevin

Abstract | Document (736 KB) | BibTeX

A Linear-Time n^{0.4}-Approximation for Longest Common Subsequence

Authors: Bringmann, Karl ; Das, Debarati

Abstract | Document (736 KB) | BibTeX

Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal

Authors: Bringmann, Karl ; Slusallek, Jasper

Abstract | Document (782 KB) | BibTeX

Fast n-Fold Boolean Convolution via Additive Combinatorics

Authors: Bringmann, Karl ; Nakos, Vasileios

Abstract | Document (718 KB) | BibTeX

Additive Approximation Schemes for Load Balancing Problems

Authors: Buchem, Moritz ; Rohwedder, Lars ; Vredeveld, Tjark ; Wiese, Andreas

Abstract | Document (627 KB) | BibTeX

Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time

Authors: Cairo, Massimo ; Rizzi, Romeo ; Tomescu, Alexandru I. ; Zirondelli, Elia C.

Abstract | Document (1,363 KB) | BibTeX

Lifting for Constant-Depth Circuits and Applications to MCSP

Authors: Carmosino, Marco ; Hoover, Kenneth ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

Abstract | Document (903 KB) | BibTeX

Sparsification of Directed Graphs via Cut Balance

Authors: Cen, Ruoxu ; Cheng, Yu ; Panigrahi, Debmalya ; Sun, Kevin

Abstract | Document (834 KB) | BibTeX

Fault Tolerant Max-Cut

Authors: Censor-Hillel, Keren ; Marelly, Noa ; Schwartz, Roy ; Tonoyan, Tigran

Abstract | Document (820 KB) | BibTeX

Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths

Authors: Chan, Timothy M. ; Vassilevska Williams, Virginia ; Xu, Yinzhan

Abstract | Document (771 KB) | BibTeX

An Almost Optimal Edit Distance Oracle

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

Abstract | Document (1,127 KB) | BibTeX

Faster Algorithms for Rooted Connectivity in Directed Graphs

Authors: Chekuri, Chandra ; Quanrud, Kent

Abstract | Document (975 KB) | BibTeX

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity

Authors: Chekuri, Chandra ; Quanrud, Kent

Abstract | Document (937 KB) | BibTeX

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹

Authors: Chen, Lijie ; Lu, Zhenjian ; Lyu, Xin ; Oliveira, Igor C.

Abstract | Document (844 KB) | BibTeX

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

Authors: Chen, Lijie ; Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R. ; Song, Zhao ; Yu, Huacheng

Abstract | Document (838 KB) | BibTeX

Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries

Authors: Chen, Yu ; Khanna, Sanjeev ; Nagda, Ansh

Abstract | Document (782 KB) | BibTeX

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence

Authors: Cheng, Kuan ; Farhadi, Alireza ; Hajiaghayi, MohammadTaghi ; Jin, Zhengzhong ; Li, Xin ; Rubinstein, Aviad ; Seddighin, Saeed ; Zheng, Yu

Abstract | Document (818 KB) | BibTeX

Quantum Query Complexity with Matrix-Vector Products

Authors: Childs, Andrew M. ; Hung, Shih-Han ; Li, Tongyang

Abstract | Document (740 KB) | BibTeX

Truthful Allocation in Graphs and Hypergraphs

Authors: Christodoulou, George ; Koutsoupias, Elias ; Kovács, Annamária

Abstract | Document (761 KB) | BibTeX

Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle

Authors: Coester, Christian ; Koutsoupias, Elias

Abstract | Document (742 KB) | BibTeX

Haystack Hunting Hints and Locker Room Communication

Authors: Czumaj, Artur ; Kontogeorgiou, George ; Paterson, Mike

Abstract | Document (1,657 KB) | BibTeX

Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies

Authors: D'Angelo, Gianlorenzo ; Poddar, Debashmita ; Vinci, Cosimo

Abstract | Document (714 KB) | BibTeX

Approximation Algorithms for Min-Distance Problems in DAGs

Authors: Dalirrooyfard, Mina ; Kaufmann, Jenny

Abstract | Document (918 KB) | BibTeX

On Greedily Packing Anchored Rectangles

Authors: Damerius, Christoph ; Kaaser, Dominik ; Kling, Peter ; Schneider, Florian

Abstract | Document (1,663 KB) | BibTeX

Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

Authors: Davies, Ewan ; Perkins, Will

Abstract | Document (817 KB) | BibTeX

Linear Time Runs Over General Ordered Alphabets

Authors: Ellert, Jonas ; Fischer, Johannes

Abstract | Document (980 KB) | BibTeX

Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary

Authors: Evald, Jacob ; Fredslund-Hansen, Viktor ; Gutenberg, Maximilian Probst ; Wulff-Nilsen, Christian

Abstract | Document (982 KB) | BibTeX

On the Approximability of Multistage Min-Sum Set Cover

Authors: Fotakis, Dimitris ; Kostopanagiotis, Panagiotis ; Nakos, Vasileios ; Piliouras, Georgios ; Skoulakis, Stratis

Abstract | Document (819 KB) | BibTeX

A Spectral Independence View on Hard Spheres via Block Dynamics

Authors: Friedrich, Tobias ; Göbel, Andreas ; Krejca, Martin S. ; Pappik, Marcus

Abstract | Document (692 KB) | BibTeX

Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime

Authors: Friggstad, Zachary ; Swamy, Chaitanya

Abstract | Document (856 KB) | BibTeX

Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications

Authors: Fu, Hu ; Tang, Zhihao Gavin ; Wu, Hongxun ; Wu, Jinzhao ; Zhang, Qianfan

Abstract | Document (704 KB) | BibTeX

A Subexponential Algorithm for ARRIVAL

Authors: Gärtner, Bernd ; Haslebacher, Sebastian ; Hoang, Hung P.

Abstract | Document (786 KB) | BibTeX

Universal Algorithms for Clustering Problems

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

Abstract | Document (761 KB) | BibTeX

LF Successor: Compact Space Indexing for Order-Isomorphic Pattern Matching

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

Abstract | Document (998 KB) | BibTeX

Crossing-Optimal Extension of Simple Drawings

Authors: Ganian, Robert ; Hamm, Thekla ; Klute, Fabian ; Parada, Irene ; Vogtenhuber, Birgit

Abstract | Document (1,046 KB) | BibTeX

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Authors: Girish, Uma ; Raz, Ran ; Zhan, Wei

Abstract | Document (789 KB) | BibTeX

Online Stochastic Matching with Edge Arrivals

Authors: Gravin, Nick ; Tang, Zhihao Gavin ; Wang, Kangning

Abstract | Document (944 KB) | BibTeX

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Authors: Gu, Yuzhou ; Polak, Adam ; Vassilevska Williams, Virginia ; Xu, Yinzhan

Abstract | Document (804 KB) | BibTeX

Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time

Authors: Gu, Yong ; Ren, Hanlin

Abstract | Document (914 KB) | BibTeX

Structural Iterative Rounding for Generalized k-Median Problems

Authors: Gupta, Anupam ; Moseley, Benjamin ; Zhou, Rudy

Abstract | Document (883 KB) | BibTeX

Near-Optimal Schedules for Simultaneous Multicasts

Authors: Haeupler, Bernhard ; Hershkowitz, D. Ellis ; Wajc, David

Abstract | Document (825 KB) | BibTeX

Analysis of Smooth Heaps and Slim Heaps

Authors: Hartmann, Maria ; Kozma, László ; Sinnamon, Corwin ; Tarjan, Robert E.

Abstract | Document (1,361 KB) | BibTeX

Approximating Maximum Integral Multiflows on Bounded Genus Graphs

Authors: Huang, Chien-Chung ; Mari, Mathieu ; Mathieu, Claire ; Vygen, Jens

Abstract | Document (904 KB) | BibTeX

Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan

Authors: Ibrahimpur, Sharat ; Swamy, Chaitanya

Abstract | Document (922 KB) | BibTeX

Quasi-Polynomial Time Algorithms for Free Quantum Games in Bounded Dimension

Authors: Jee, Hyejung H. ; Sparaciari, Carlo ; Fawzi, Omar ; Berta, Mario

Abstract | Document (756 KB) | BibTeX

Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems

Authors: Karczmarz, Adam

Abstract | Document (818 KB) | BibTeX

Coboundary and Cosystolic Expansion from Strong Symmetry

Authors: Kaufman, Tali ; Oppenheim, Izhar

Abstract | Document (729 KB) | BibTeX

Maximum Matchings and Popularity

Authors: Kavitha, Telikepalli

Abstract | Document (903 KB) | BibTeX

Automorphisms and Isomorphisms of Maps in Linear Time

Authors: Kawarabayashi, Ken-ichi ; Mohar, Bojan ; Nedela, Roman ; Zeman, Peter

Abstract | Document (679 KB) | BibTeX

Lower Bounds on Dynamic Programming for Maximum Weight Independent Set

Authors: Korhonen, Tuukka

Abstract | Document (710 KB) | BibTeX

Sorting Short Integers

Authors: Koucký, Michal ; Král, Karel

Abstract | Document (763 KB) | BibTeX

Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges

Authors: Kozik, Jakub

Abstract | Document (662 KB) | BibTeX

SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

Authors: Kurpisz, Adam ; Potechin, Aaron ; Wirth, Elias Samuel

Abstract | Document (792 KB) | BibTeX

On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order

Authors: Lagodzinski, J. A. Gregor ; Göbel, Andreas ; Casel, Katrin ; Friedrich, Tobias

Abstract | Document (1,106 KB) | BibTeX

Minimum Stable Cut and Treewidth

Authors: Lampis, Michael

Abstract | Document (797 KB) | BibTeX

Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n)

Authors: Levi, Reut

Abstract | Document (776 KB) | BibTeX

An Efficient Coding Theorem via Probabilistic Representations and Its Applications

Authors: Lu, Zhenjian ; Oliveira, Igor C.

Abstract | Document (810 KB) | BibTeX

Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth

Authors: Marx, Dániel ; Sankar, Govind S. ; Schepper, Philipp

Abstract | Document (1,174 KB) | BibTeX

High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion

Authors: McKenzie, Theo ; Mohanty, Sidhanth

Abstract | Document (759 KB) | BibTeX

Relational Algorithms for k-Means Clustering

Authors: Moseley, Benjamin ; Pruhs, Kirk ; Samadian, Alireza ; Wang, Yuyan

Abstract | Document (794 KB) | BibTeX

Testing Dynamic Environments: Back to Basics

Authors: Nakar, Yonatan ; Ron, Dana

Abstract | Document (960 KB) | BibTeX

Decision Problems for Second-Order Holonomic Recurrences

Authors: Neumann, Eike ; Ouaknine, Joël ; Worrell, James

Abstract | Document (707 KB) | BibTeX

New Sublinear Algorithms and Lower Bounds for LIS Estimation

Authors: Newman, Ilan ; Varma, Nithin

Abstract | Document (850 KB) | BibTeX

Optimal-Time Queries on BWT-Runs Compressed Indexes

Authors: Nishimoto, Takaaki ; Tabei, Yasuo

Abstract | Document (870 KB) | BibTeX

Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms

Authors: Parekh, Ojas ; Thompson, Kevin

Abstract | Document (770 KB) | BibTeX

Matching on the Line Admits No o(√log n)-Competitive Algorithm

Authors: Peserico, Enoch ; Scquizzato, Michele

Abstract | Document (534 KB) | BibTeX

Non-Mergeable Sketching for Cardinality Estimation

Authors: Pettie, Seth ; Wang, Dingyu ; Yin, Longhui

Abstract | Document (1,205 KB) | BibTeX

The Structure of Minimum Vertex Cuts

Authors: Pettie, Seth ; Yin, Longhui

Abstract | Document (1,251 KB) | BibTeX

Knapsack and Subset Sum with Small Items

Authors: Polak, Adam ; Rohwedder, Lars ; Węgrzycki, Karol

Abstract | Document (1,006 KB) | BibTeX

Multiple Random Walks on Graphs: Mixing Few to Cover Many

Authors: Rivera, Nicolás ; Sauerwald, Thomas ; Sylvester, John

Abstract | Document (785 KB) | BibTeX

Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders

Authors: Roth, Marc ; Schmitt, Johannes ; Wellnitz, Philip

Abstract | Document (849 KB) | BibTeX

The Greedy Algorithm Is not Optimal for On-Line Edge Coloring

Authors: Saberi, Amin ; Wajc, David

Abstract | Document (738 KB) | BibTeX

Quantum Algorithms for Matrix Scaling and Matrix Balancing

Authors: van Apeldoorn, Joran ; Gribling, Sander ; Li, Yinan ; Nieuwboer, Harold ; Walter, Michael ; de Wolf, Ronald

Abstract | Document (901 KB) | BibTeX

Fourier Conjectures, Correlation Bounds, and Majority

Authors: Viola, Emanuele

Abstract | Document (660 KB) | BibTeX

Separations for Estimating Large Frequency Moments on Data Streams

Authors: Woodruff, David P. ; Zhou, Samson

Abstract | Document (860 KB) | BibTeX

Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring

Authors: Zamir, Or

Abstract | Document (965 KB) | BibTeX

Deterministic Maximum Flows in Simple Graphs

Authors: Zhang, Tianyi

Abstract | Document (750 KB) | BibTeX

Arboreal Categories and Resources

Authors: Abramsky, Samson ; Reggio, Luca

Abstract | Document (802 KB) | BibTeX

Dynamic Membership for Regular Languages

Authors: Amarilli, Antoine ; Jachiet, Louis ; Paperman, Charles

Abstract | Document (844 KB) | BibTeX

A Rice’s Theorem for Abstract Semantics

Authors: Baldan, Paolo ; Ranzato, Francesco ; Zhang, Linpeng

Abstract | Document (809 KB) | BibTeX

Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata

Authors: Balle, Borja ; Lacroce, Clara ; Panangaden, Prakash ; Precup, Doina ; Rabusseau, Guillaume

Abstract | Document (900 KB) | BibTeX

Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages

Authors: Bathie, Gabriel ; Starikovskaya, Tatiana

Abstract | Document (782 KB) | BibTeX

Datalog-Expressibility for Monadic and Guarded Second-Order Logic

Authors: Bodirsky, Manuel ; Knäuer, Simon ; Rudolph, Sebastian

Abstract | Document (758 KB) | BibTeX

Beyond PCSP(1-in-3, NAE)

Authors: Brandts, Alex ; Živný, Stanislav

Abstract | Document (834 KB) | BibTeX

Computational Characterization of Surface Entropies for ℤ² Subshifts of Finite Type

Authors: Callard, Antonin ; Vanier, Pascal

Abstract | Document (910 KB) | BibTeX

Optimal Transformations of Games and Automata Using Muller Conditions

Authors: Casares, Antonio ; Colcombet, Thomas ; Fijalkow, Nathanaël

Abstract | Document (791 KB) | BibTeX

Faster Algorithms for Bounded Liveness in Graphs and Game Graphs

Authors: Chatterjee, Krishnendu ; Henzinger, Monika ; Kale, Sagar Sudhir ; Svozil, Alexander

Abstract | Document (835 KB) | BibTeX

Inference Systems with Corules for Fair Subtyping and Liveness Properties of Binary Session Types

Authors: Ciccone, Luca ; Padovani, Luca

Abstract | Document (726 KB) | BibTeX

Deterministic and Game Separability for Regular Languages of Infinite Trees

Authors: Clemente, Lorenzo ; Skrzypczak, Michał

Abstract | Document (790 KB) | BibTeX

A Complexity Approach to Tree Algebras: the Bounded Case

Authors: Colcombet, Thomas ; Jaquard, Arthur

Abstract | Document (819 KB) | BibTeX

Improved Lower Bounds for Reachability in Vector Addition Systems

Authors: Czerwiński, Wojciech ; Lasota, Sławomir ; Orlikowski, Łukasz

Abstract | Document (828 KB) | BibTeX

New Techniques for Universality in Unambiguous Register Automata

Authors: Czerwiński, Wojciech ; Mottet, Antoine ; Quaas, Karin

Abstract | Document (817 KB) | BibTeX

The Theory of Concatenation over Finite Models

Authors: Freydenberger, Dominik D. ; Peterfreund, Liat

Abstract | Document (810 KB) | BibTeX

Uniform Elgot Iteration in Foundations

Authors: Goncharov, Sergey

Abstract | Document (752 KB) | BibTeX

Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces

Authors: Goy, Alexandre ; Petrişan, Daniela ; Aiguier, Marc

Abstract | Document (971 KB) | BibTeX

Elementary Equivalence Versus Isomorphism in Semiring Semantics

Authors: Grädel, Erich ; Mrkonjić, Lovro

Abstract | Document (815 KB) | BibTeX

Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

Authors: Grohe, Martin ; Kiefer, Sandra

Abstract | Document (830 KB) | BibTeX

Kernelization, Proof Complexity and Social Choice

Authors: Istrate, Gabriel ; Bonchiş, Cosmin ; Crăciun, Adrian

Abstract | Document (787 KB) | BibTeX

Quantum Relational Hoare Logic with Expectations

Authors: Li, Yangjia ; Unruh, Dominique

Abstract | Document (955 KB) | BibTeX

Playing Stochastically in Weighted Timed Games to Emulate Memory

Authors: Monmege, Benjamin ; Parreaux, Julie ; Reynier, Pierre-Alain

Abstract | Document (840 KB) | BibTeX

Smooth Approximations and Relational Width Collapses

Authors: Mottet, Antoine ; Nagy, Tomáš ; Pinsker, Michael ; Wrona, Michał

Abstract | Document (788 KB) | BibTeX

Comparison-Free Polyregular Functions

Authors: Nguyễn, Lê Thành Dũng (Tito) ; Noûs, Camille ; Pradic, Pierre

Abstract | Document (934 KB) | BibTeX

Higher-Order Model Checking Step by Step

Authors: Parys, Paweł

Abstract | Document (768 KB) | BibTeX

Fluted Logic with Counting

Authors: Pratt-Hartmann, Ian

Abstract | Document (778 KB) | BibTeX

Guarded Kleene Algebra with Tests: Coequations, Coinduction, and Completeness

Authors: Schmid, Todd ; Kappé, Tobias ; Kozen, Dexter ; Silva, Alexandra

Abstract | Document (926 KB) | BibTeX

Analytical Differential Calculus with Integration

Authors: Xu, Han ; Hu, Zhenjiang

Abstract | Document (658 KB) | BibTeX

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

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)