Portal - ICALP 2023

ICALP 2023	July 10-14, 2023, Paderborn, Germany
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) Kousha Etessami and Uriel Feige and Gabriele Puppis (Eds.)
ISBN 978-3-95977-278-5, LIPICS Vol. 261	ISSN 1868-8969

Additional Information

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

Authors

Berendsohn, Benjamin Aram

Bergamaschi, Thiago

Berkholz, Christoph

Bhattacharjee, Rajarshi

Bhattacharya, Sudatta

Chakraborty, Diptarka

Douéneau-Tabot, Gaëtan

Eleftheriadis, Ioannis

Houen, Jakob Bæk Tejs

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

Przybyszewski, Wojciech

Rasmussen, Peter M. R.

Rau, Malin

Ray, Archan

Reiffenhäuser, Rebecca

Sarmasarkar, Sahasrajit

Sau, Ignasi

Sauerwald, Thomas

Saurabh, Saket

Saxena, Raghuvansh R.

Sinclair-Banks, Henry

Surianarayanan, Vaishali

Thilikos, Dimitrios M.

Thinniyam, Ramanathan S.

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele

Abstract | Document (3,076 KB) | BibTeX

A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)

Authors: Karlin, Anna R.

Abstract | Document (332 KB) | BibTeX

An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk)

Authors: Kyng, Rasmus

Abstract | Document (377 KB) | BibTeX

Context-Bounded Analysis of Concurrent Programs (Invited Talk)

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

Abstract | Document (886 KB) | BibTeX

Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk)

Authors: Vidick, Thomas

Abstract | Document (312 KB) | BibTeX

The Skolem Landscape (Invited Talk)

Authors: Worrell, James

Abstract | Document (293 KB) | BibTeX

Optimal Decremental Connectivity in Non-Sparse Graphs

Authors: Aamand, Anders ; Karczmarz, Adam ; Łącki, Jakub ; Parotsidis, Nikos ; Rasmussen, Peter M. R. ; Thorup, Mikkel

Abstract | Document (780 KB) | BibTeX

On Range Summary Queries

Authors: Afshani, Peyman ; Cheng, Pingan ; Basu Roy, Aniket ; Wei, Zhewei

Abstract | Document (782 KB) | BibTeX

Stable Matching: Choosing Which Proposals to Make

Authors: Agarwal, Ishan ; Cole, Richard

Abstract | Document (979 KB) | BibTeX

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

Authors: Agassy, Daniel ; Dorfman, Dani ; Kaplan, Haim

Abstract | Document (816 KB) | BibTeX

Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms

Authors: Akbari, Amirreza ; Eslami, Navid ; Lievonen, Henrik ; Melnyk, Darya ; Särkijärvi, Joona ; Suomela, Jukka

Abstract | Document (2,096 KB) | BibTeX

An Efficient Algorithm for All-Pairs Bounded Edge Connectivity

Authors: Akmal, Shyan ; Jin, Ce

Abstract | Document (827 KB) | BibTeX

Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization

Authors: Amireddy, Prashanth ; Garg, Ankit ; Kayal, Neeraj ; Saha, Chandan ; Thankey, Bhargav

Abstract | Document (867 KB) | BibTeX

Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering

Authors: Azar, Yossi ; Vainstein, Danny

Abstract | Document (858 KB) | BibTeX

Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation

Authors: Azarmehr, Amir ; Behnezhad, Soheil

Abstract | Document (755 KB) | BibTeX

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

Authors: Bansal, Ishan ; Cheriyan, Joseph ; Grout, Logan ; Ibrahimpur, Sharat

Abstract | Document (877 KB) | BibTeX

Approximation Algorithms for Envy-Free Cake Division with Connected Pieces

Authors: Barman, Siddharth ; Kulkarni, Pooja

Abstract | Document (812 KB) | BibTeX

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Authors: Beame, Paul ; Kornerup, Niels

Abstract | Document (952 KB) | BibTeX

Dynamic Averaging Load Balancing on Arbitrary Graphs

Authors: Berenbrink, Petra ; Hintze, Lukas ; Hosseinpour, Hamed ; Kaaser, Dominik ; Rau, Malin

Abstract | Document (867 KB) | BibTeX

Fast Approximation of Search Trees on Trees with Centroid Trees

Authors: Berendsohn, Benjamin Aram ; Golinsky, Ishay ; Kaplan, Haim ; Kozma, László

Abstract | Document (965 KB) | BibTeX

Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians

Authors: Bergamaschi, Thiago

Abstract | Document (731 KB) | BibTeX

Sublinear Time Eigenvalue Approximation via Random Sampling

Authors: Bhattacharjee, Rajarshi ; Dexter, Gregory ; Drineas, Petros ; Musco, Cameron ; Ray, Archan

Abstract | Document (814 KB) | BibTeX

Streaming k-Edit Approximate Pattern Matching via String Decomposition

Authors: Bhattacharya, Sudatta ; Koucký, Michal

Abstract | Document (745 KB) | BibTeX

On Computing the Vertex Connectivity of 1-Plane Graphs

Authors: Biedl, Therese ; Murali, Karthik

Abstract | Document (1,135 KB) | BibTeX

Fault-Tolerant ST-Diameter Oracles

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

Abstract | Document (881 KB) | BibTeX

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Authors: Black, Hadley ; Kalemaj, Iden ; Raskhodnikova, Sofya

Abstract | Document (1,004 KB) | BibTeX

The Geometry of Tree-Based Sorting

Authors: Blelloch, Guy E. ; Dobson, Magdalen

Abstract | Document (1,437 KB) | BibTeX

Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters

Authors: Bodlaender, Hans L. ; Groenland, Carla ; Pilipczuk, Michał

Abstract | Document (897 KB) | BibTeX

Nondeterministic Interactive Refutations for Nearest Boolean Vector

Authors: Bogdanov, Andrej ; Rosen, Alon

Abstract | Document (731 KB) | BibTeX

A 4/3 Approximation for 2-Vertex-Connectivity

Authors: Bosch-Calvo, Miguel ; Grandoni, Fabrizio ; Jabal Ameli, Afrouz

Abstract | Document (688 KB) | BibTeX

Lower Bounds for Pseudo-Deterministic Counting in a Stream

Authors: Braverman, Vladimir ; Krauthgamer, Robert ; Krishnan, Aditya ; Sapir, Shay

Abstract | Document (735 KB) | BibTeX

Minimum Chain Cover in Almost Linear Time

Authors: Cáceres, Manuel

Abstract | Document (762 KB) | BibTeX

Improved Hardness Results for the Guided Local Hamiltonian Problem

Authors: Cade, Chris ; Folkertsma, Marten ; Gharibian, Sevag ; Hayakawa, Ryu ; Le Gall, François ; Morimae, Tomoyuki ; Weggemans, Jordi

Abstract | Document (766 KB) | BibTeX

Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint

Authors: Cai, Jin-Yi ; Young, Ben

Abstract | Document (846 KB) | BibTeX

On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k

Authors: Chan, Timothy M. ; He, Qizheng ; Yu, Yuancheng

Abstract | Document (889 KB) | BibTeX

Ortho-Radial Drawing in Near-Linear Time

Authors: Chang, Yi-Jun

Abstract | Document (1,185 KB) | BibTeX

Approximation Algorithms for Network Design in Non-Uniform Fault Models

Authors: Chekuri, Chandra ; Jain, Rhea

Abstract | Document (750 KB) | BibTeX

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics

Authors: Chen, Yu ; Khanna, Sanjeev ; Tan, Zihan

Abstract | Document (776 KB) | BibTeX

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Authors: Chen, Yanlin ; de Wolf, Ronald

Abstract | Document (799 KB) | BibTeX

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs

Authors: Chen, Lijie ; Lyu, Xin ; Tal, Avishay ; Wu, Hongxun

Abstract | Document (859 KB) | BibTeX

Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance

Authors: Cheng, Siu-Wing ; Huang, Haoqiang

Abstract | Document (932 KB) | BibTeX

Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes

Authors: Cheng, Kuan ; Jin, Zhengzhong ; Li, Xin ; Wei, Zhide ; Zheng, Yu

Abstract | Document (779 KB) | BibTeX

Online Learning and Disambiguations of Partial Concept Classes

Authors: Cheung, Tsun-Ming ; Hatami, Hamed ; Hatami, Pooya ; Hosseini, Kaave

Abstract | Document (646 KB) | BibTeX

A General Framework for Learning-Augmented Online Allocation

Authors: Cohen, Ilan Reuven ; Panigrahi, Debmalya

Abstract | Document (853 KB) | BibTeX

Sample-Based Distance-Approximation for Subsequence-Freeness

Authors: Cohen Sidon, Omer ; Ron, Dana

Abstract | Document (801 KB) | BibTeX

New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling

Authors: Compton, Spencer ; Mitrović, Slobodan ; Rubinfeld, Ronitt

Abstract | Document (653 KB) | BibTeX

Optimal (Degree+1)-Coloring in Congested Clique

Authors: Coy, Sam ; Czumaj, Artur ; Davies, Peter ; Mishra, Gopinath

Abstract | Document (1,011 KB) | BibTeX

Incremental Maximization via Continuization

Authors: Disser, Yann ; Klimm, Max ; Schewior, Kevin ; Weckbecker, David

Abstract | Document (796 KB) | BibTeX

Local Computation Algorithms for Hypergraph Coloring - Following Beck’s Approach

Authors: Dorobisz, Andrzej ; Kozik, Jakub

Abstract | Document (860 KB) | BibTeX

An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets

Authors: Doron-Arad, Ilan ; Kulik, Ariel ; Shachnai, Hadas

Abstract | Document (761 KB) | BibTeX

Connected k-Center and k-Diameter Clustering

Authors: Drexler, Lukas ; Eube, Jan ; Luo, Kelin ; Röglin, Heiko ; Schmidt, Melanie ; Wargalla, Julian

Abstract | Document (3,158 KB) | BibTeX

On Sparsification of Stochastic Packing Problems

Authors: Dughmi, Shaddin ; Kalayci, Yusuf Hakan ; Patel, Neel

Abstract | Document (922 KB) | BibTeX

Triangle Counting with Local Edge Differential Privacy

Authors: Eden, Talya ; Liu, Quanquan C. ; Raskhodnikova, Sofya ; Smith, Adam

Abstract | Document (1,066 KB) | BibTeX

Protecting Single-Hop Radio Networks from Message Drops

Authors: Efremenko, Klim ; Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R.

Abstract | Document (800 KB) | BibTeX

On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)

Authors: Efthymiou, Charilaos ; Feng, Weiming

Abstract | Document (718 KB) | BibTeX

Broadcasting with Random Matrices

Authors: Efthymiou, Charilaos ; Zampetakis, Kostas

Abstract | Document (636 KB) | BibTeX

Improved Mixing for the Convex Polygon Triangulation Flip Walk

Authors: Eppstein, David ; Frishberg, Daniel

Abstract | Document (1,082 KB) | BibTeX

Optimal Adjacency Labels for Subgraphs of Cartesian Products

Authors: Esperet, Louis ; Harms, Nathaniel ; Zamaraev, Viktor

Abstract | Document (676 KB) | BibTeX

Truthful Matching with Online Items and Offline Agents

Authors: Feldman, Michal ; Fusco, Federico ; Mauras, Simon ; Reiffenhäuser, Rebecca

Abstract | Document (793 KB) | BibTeX

Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds

Authors: Ferens, Robert ; Szykuła, Marek

Abstract | Document (790 KB) | BibTeX

Approximating Long Cycle Above Dirac’s Guarantee

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Sagunov, Danil ; Simonov, Kirill

Abstract | Document (824 KB) | BibTeX

Compound Logics for Modification Problems

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Sau, Ignasi ; Stamoulis, Giannos ; Thilikos, Dimitrios M.

Abstract | Document (981 KB) | BibTeX

Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs

Authors: Friedrich, Tobias ; Göbel, Andreas ; Katzmann, Maximilian ; Schiller, Leon

Abstract | Document (730 KB) | BibTeX

An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs

Authors: Friggstad, Zachary ; Mousavi, Ramin

Abstract | Document (1,225 KB) | BibTeX

Parallel Self-Testing of EPR Pairs Under Computational Assumptions

Authors: Fu, Honghao ; Wang, Daochen ; Zhao, Qi

Abstract | Document (873 KB) | BibTeX

Matching Augmentation via Simultaneous Contractions

Authors: Garg, Mohit ; Hommelsheim, Felix ; Megow, Nicole

Abstract | Document (737 KB) | BibTeX

On Differentially Private Counting on Trees

Authors: Ghazi, Badih ; Kamath, Pritish ; Kumar, Ravi ; Manurangsi, Pasin ; Wu, Kewen

Abstract | Document (991 KB) | BibTeX

Quantum Cryptography with Classical Communication: Parallel Remote State Preparation for Copy-Protection, Verification, and More

Authors: Gheorghiu, Alexandru ; Metger, Tony ; Poremba, Alexander

Abstract | Document (843 KB) | BibTeX

Parameterised and Fine-Grained Subgraph Counting, Modulo 2

Authors: Goldberg, Leslie Ann ; Roth, Marc

Abstract | Document (833 KB) | BibTeX

Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Authors: Goranci, Gramoz ; Henzinger, Monika

Abstract | Document (855 KB) | BibTeX

Low Sample Complexity Participatory Budgeting

Authors: Goyal, Mohak ; Sakshuwong, Sukolsak ; Sarmasarkar, Sahasrajit ; Goel, Ashish

Abstract | Document (1,404 KB) | BibTeX

The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Cross-Model Simulation in Tile-Based Self-Assembly

Authors: Hader, Daniel ; Patitz, Matthew J.

Abstract | Document (1,313 KB) | BibTeX

Parameter Estimation for Gibbs Distributions

Authors: Harris, David G. ; Kolmogorov, Vladimir

Abstract | Document (896 KB) | BibTeX

On Finding Constrained Independent Sets in Cycles

Authors: Haviv, Ishay

Abstract | Document (707 KB) | BibTeX

Faster Submodular Maximization for Several Classes of Matroids

Authors: Henzinger, Monika ; Liu, Paul ; Vondrák, Jan ; Zheng, Da Wei

Abstract | Document (909 KB) | BibTeX

Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar

Authors: Hliněný, Petr ; Jedelský, Jan

Abstract | Document (760 KB) | BibTeX

A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

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

Abstract | Document (753 KB) | BibTeX

Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm

Authors: Hsieh, Jun-Ting ; Kothari, Pravesh K.

Abstract | Document (624 KB) | BibTeX

Ellipsoid Fitting up to a Constant

Authors: Hsieh, Jun-Ting ; Kothari, Pravesh K. ; Potechin, Aaron ; Xu, Jeff

Abstract | Document (866 KB) | BibTeX

Finding Almost Tight Witness Trees

Authors: Hyatt-Denesik, Dylan ; Jabal Ameli, Afrouz ; Sanità, Laura

Abstract | Document (722 KB) | BibTeX

Efficient Caching with Reserves via Marking

Authors: Ibrahimpur, Sharat ; Purohit, Manish ; Svitkina, Zoya ; Vee, Erik ; Wang, Joshua R.

Abstract | Document (890 KB) | BibTeX

Rerouting Planar Curves and Disjoint Paths

Authors: Ito, Takehiro ; Iwamasa, Yuni ; Kakimura, Naonori ; Kobayashi, Yusuke ; Maezawa, Shun-ichi ; Nozaki, Yuta ; Okamoto, Yoshio ; Ozeki, Kenta

Abstract | Document (1,381 KB) | BibTeX

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Authors: Ito, Takehiro ; Kakimura, Naonori ; Kamiyama, Naoyuki ; Kobayashi, Yusuke ; Maezawa, Shun-ichi ; Nozaki, Yuta ; Okamoto, Yoshio

Abstract | Document (1,112 KB) | BibTeX

Searching for Regularity in Bounded Functions

Authors: Iyer, Siddharth ; Whitmeyer, Michael

Abstract | Document (862 KB) | BibTeX

Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs

Authors: Karczmarz, Adam ; Sankowski, Piotr

Abstract | Document (788 KB) | BibTeX

New Additive Emulators

Authors: Kogan, Shimon ; Parter, Merav

Abstract | Document (845 KB) | BibTeX

Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems

Authors: Li, Shi

Abstract | Document (990 KB) | BibTeX

Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion

Authors: Li, Xiantao ; Wang, Chunhao

Abstract | Document (695 KB) | BibTeX

Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching

Authors: Liu, S. Cliff ; Song, Zhao ; Zhang, Hengjie ; Zhang, Lichen ; Zhou, Tianyi

Abstract | Document (788 KB) | BibTeX

List Decoding of Rank-Metric Codes with Row-To-Column Ratio Bigger Than 1/2

Authors: Liu, Shu ; Xing, Chaoping ; Yuan, Chen

Abstract | Document (960 KB) | BibTeX

Breaking the All Subsets Barrier for Min k-Cut

Authors: Lokshtanov, Daniel ; Saurabh, Saket ; Surianarayanan, Vaishali

Abstract | Document (1,100 KB) | BibTeX

A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees

Authors: Mathieu, Claire ; Zhou, Hang

Abstract | Document (960 KB) | BibTeX

Online Demand Scheduling with Failovers

Authors: Mellou, Konstantina ; Molinaro, Marco ; Zhou, Rudy

Abstract | Document (919 KB) | BibTeX

Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes

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

Abstract | Document (956 KB) | BibTeX

Nearly Tight Spectral Sparsification of Directed Hypergraphs

Authors: Oko, Kazusato ; Sakaue, Shinsaku ; Tanigawa, Shin-ichi

Abstract | Document (804 KB) | BibTeX

The Communication Complexity of Set Intersection Under Product Distributions

Authors: Oshman, Rotem ; Roth, Tal

Abstract | Document (761 KB) | BibTeX

An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs

Authors: Peng, Pan ; Wang, Yuyang

Abstract | Document (779 KB) | BibTeX

Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States

Authors: Qin, Minglong ; Yao, Penghui

Abstract | Document (900 KB) | BibTeX

Scheduling Under Non-Uniform Job and Machine Delays

Authors: Rajaraman, Rajmohan ; Stalfa, David ; Yang, Sheng

Abstract | Document (985 KB) | BibTeX

Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery

Authors: Resch, Nicolas ; Yuan, Chen ; Zhang, Yihan

Abstract | Document (1,115 KB) | BibTeX

Convergence of the Number of Period Sets in Strings

Authors: Rivals, Eric ; Sweering, Michelle ; Wang, Pengfei

Abstract | Document (782 KB) | BibTeX

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability

Authors: Roberson, David E. ; Seppelt, Tim

Abstract | Document (893 KB) | BibTeX

Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Authors: Rubinstein, Ittai

Abstract | Document (903 KB) | BibTeX

The Support of Open Versus Closed Random Walks

Authors: Sauerwald, Thomas ; Sun, He ; Vagnozzi, Danny

Abstract | Document (791 KB) | BibTeX

Faster Matroid Partition Algorithms

Authors: Terao, Tatsuya

Abstract | Document (852 KB) | BibTeX

Frameworks for Nonclairvoyant Network Design with Deadlines or Delay

Authors: Touitou, Noam

Abstract | Document (842 KB) | BibTeX

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth

Authors: Włodarczyk, Michał

Abstract | Document (1,164 KB) | BibTeX

The Wrong Direction of Jensen’s Inequality Is Algorithmically Right

Authors: Zamir, Or

Abstract | Document (620 KB) | BibTeX

A Hyperbolic Extension of Kadison-Singer Type Results

Authors: Zhang, Ruizhe ; Zhang, Xinzhi

Abstract | Document (692 KB) | BibTeX

On Semantically-Deterministic Automata

Authors: Abu Radi, Bader ; Kupferman, Orna

Abstract | Document (774 KB) | BibTeX

Checking Refinement of Asynchronous Programs Against Context-Free Specifications

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

Abstract | Document (948 KB) | BibTeX

On the Limits of Decision: the Adjacent Fragment of First-Order Logic

Authors: Bednarczyk, Bartosz ; Kojelis, Daumantas ; Pratt-Hartmann, Ian

Abstract | Document (917 KB) | BibTeX

The Complexity of Presburger Arithmetic with Power or Powers

Authors: Benedikt, Michael ; Chistikov, Dmitry ; Mansutti, Alessio

Abstract | Document (822 KB) | BibTeX

A Dichotomy for Succinct Representations of Homomorphisms

Authors: Berkholz, Christoph ; Vinall-Smeeth, Harry

Abstract | Document (823 KB) | BibTeX

Nominal Topology for Data Languages

Authors: Birkmann, Fabian ; Milius, Stefan ; Urbat, Henning

Abstract | Document (800 KB) | BibTeX

Population Protocols with Unordered Data

Authors: Blondin, Michael ; Ladouceur, François

Abstract | Document (863 KB) | BibTeX

Network Satisfaction Problems Solved by k-Consistency

Authors: Bodirsky, Manuel ; Knäuer, Simon

Abstract | Document (835 KB) | BibTeX

Algebraic Recognition of Regular Functions

Authors: Bojańczyk, Mikołaj ; Nguyễn, Lê Thành Dũng (Tito)

Abstract | Document (960 KB) | BibTeX

How to Play Optimally for Regular Objectives?

Authors: Bouyer, Patricia ; Fijalkow, Nathanaël ; Randour, Mickael ; Vandenhove, Pierre

Abstract | Document (856 KB) | BibTeX

Monadic NIP in Monotone Classes of Relational Structures

Authors: Braunfeld, Samuel ; Dawar, Anuj ; Eleftheriadis, Ioannis ; Papadopoulos, Aris

Abstract | Document (826 KB) | BibTeX

Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus

Authors: Carette, Titouan ; Moutot, Etienne ; Perez, Thomas ; Vilmart, Renaud

Abstract | Document (910 KB) | BibTeX

Deterministic Regular Functions of Infinite Words

Authors: Carton, Olivier ; Douéneau-Tabot, Gaëtan ; Filiot, Emmanuel ; Winter, Sarah

Abstract | Document (806 KB) | BibTeX

Characterising Memory in Infinite Games

Authors: Casares, Antonio ; Ohlmann, Pierre

Abstract | Document (1,161 KB) | BibTeX

Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?

Authors: Chakraborty, Diptarka ; Chakraborty, Sourav ; Kumar, Gunjan ; Meel, Kuldeep S.

Abstract | Document (700 KB) | BibTeX

The Identity Problem in ℤ ≀ ℤ Is Decidable

Authors: Dong, Ruiwen

Abstract | Document (882 KB) | BibTeX

Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes

Authors: Dreier, Jan ; Mählmann, Nikolas ; Siebertz, Sebastian ; Toruńczyk, Szymon

Abstract | Document (1,021 KB) | BibTeX

Black-Box Testing Liveness Properties of Partially Observable Stochastic Systems

Authors: Esparza, Javier ; Grande, Vincent P.

Abstract | Document (990 KB) | BibTeX

The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems

Authors: Fan, Austen Z. ; Koutris, Paraschos ; Zhao, Hangdong

Abstract | Document (857 KB) | BibTeX

Flipper Games for Monadically Stable Graph Classes

Authors: Gajarský, Jakub ; Mählmann, Nikolas ; McCarty, Rose ; Ohlmann, Pierre ; Pilipczuk, Michał ; Przybyszewski, Wojciech ; Siebertz, Sebastian ; Sokołowski, Marek ; Toruńczyk, Szymon

Abstract | Document (893 KB) | BibTeX

Regular Methods for Operator Precedence Languages

Authors: Henzinger, Thomas A. ; Kebis, Pavol ; Mazzocchi, Nicolas ; Saraç, N. Ege

Abstract | Document (998 KB) | BibTeX

Positivity Problems for Reversible Linear Recurrence Sequences

Authors: Kenison, George ; Nieuwveld, Joris ; Ouaknine, Joël ; Worrell, James

Abstract | Document (686 KB) | BibTeX

Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality

Authors: Künnemann, Marvin ; Mazowiecki, Filip ; Schütze, Lia ; Sinclair-Banks, Henry ; Węgrzycki, Karol

Abstract | Document (1,030 KB) | BibTeX

First Order Logic on Pathwidth Revisited Again

Authors: Lampis, Michael

Abstract | Document (777 KB) | BibTeX

Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting

Authors: Lichter, Moritz

Abstract | Document (839 KB) | BibTeX

On the Complexity of Diameter and Related Problems in Permutation Groups

Authors: Lohrey, Markus ; Rosowski, Andreas

Abstract | Document (796 KB) | BibTeX

Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes

Authors: Ohlmann, Pierre ; Pilipczuk, Michał ; Przybyszewski, Wojciech ; Toruńczyk, Szymon

Abstract | Document (909 KB) | BibTeX

Probabilistic Guarded KAT Modulo Bisimilarity: Completeness and Complexity

Authors: Różowski, Wojciech ; Kappé, Tobias ; Kozen, Dexter ; Schmid, Todd ; Silva, Alexandra

Abstract | Document (968 KB) | BibTeX

Action Codes

Authors: Vaandrager, Frits ; Wißmann, Thorsten

Abstract | Document (973 KB) | BibTeX

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

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)