Portal - MFCS 2023

MFCS 2023	August 28 to September 1, 2023, Bordeaux, France
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) Jérôme Leroux and Sylvain Lombardy and David Peleg (Eds.)
ISBN 978-3-95977-292-1, LIPICS Vol. 272	ISSN 1868-8969

Additional Information

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

Authors

Ağaoğlu Çağırıcı, Deniz

Chakraborty, Dibyayan

Chakraborty, Diptarka

Chalki, Aggeliki

Chalopin, Jérémie

Chatterjee, Krishnendu

Chattopadhyay, Arkadev

da Rocha Paiva, Bruno

Gergatsouli, Evangelia

Holznigenkemper, Jana

Komusiewicz, Christian

Montecchiani, Fabrizio

Nanoti, Saraswati Girish

Papamakarios, Theodoros

Raskin, Jean-François

Spenner, Daniel Alexander

Spirakis, Paul G.

St Clere Smithe, Toby

Todtenhoefer, Jennifer

van den Bogaard, Marie

van Ee, Martijn

van Leeuwen, Erik Jan

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Leroux, Jérôme ; Lombardy, Sylvain ; Peleg, David

Abstract | Document (561 KB) | BibTeX

Exploring the Space of Colourings with Kempe Changes (Invited Talk)

Authors: Bonamy, Marthe

Abstract | Document (391 KB) | BibTeX

Online Algorithms with Predictions (Invited Talk)

Authors: Boyar, Joan

Abstract | Document (449 KB) | BibTeX

Modern Parallel Algorithms (Invited Talk)

Authors: Czumaj, Artur

Abstract | Document (438 KB) | BibTeX

Algebraic Reasoning for (Un)Solvable Loops (Invited Talk)

Authors: Kovács, Laura

Abstract | Document (378 KB) | BibTeX

Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk)

Authors: Klobas, Nina ; Mertzios, George B. ; Spirakis, Paul G.

Abstract | Document (621 KB) | BibTeX

Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes

Authors: Abu-Khzam, Faisal N. ; Fernau, Henning ; Mann, Kevin

Abstract | Document (785 KB) | BibTeX

Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes

Authors: Achilleos, Antonis ; Chalki, Aggeliki

Abstract | Document (973 KB) | BibTeX

Recognizing H-Graphs - Beyond Circular-Arc Graphs

Authors: Ağaoğlu Çağırıcı, Deniz ; Çağırıcı, Onur ; Derbisz, Jan ; Hartmann, Tim A. ; Hliněný, Petr ; Kratochvíl, Jan ; Krawczyk, Tomasz ; Zeman, Peter

Abstract | Document (827 KB) | BibTeX

Descriptive Complexity for Distributed Computing with Circuits

Authors: Ahvonen, Veeti ; Heiman, Damian ; Hella, Lauri ; Kuusisto, Antti

Abstract | Document (761 KB) | BibTeX

Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration

Authors: Akian, Marianne ; Gaubert, Stéphane ; Naepels, Ulysse ; Terver, Basile

Abstract | Document (769 KB) | BibTeX

The Geometry of Reachability in Continuous Vector Addition Systems with States

Authors: Almagor, Shaull ; Ghosh, Arka ; Leys, Tim ; Pérez, Guillermo A.

Abstract | Document (836 KB) | BibTeX

Competitive Search in the Line and the Star with Predictions

Authors: Angelopoulos, Spyros

Abstract | Document (667 KB) | BibTeX

Rényi-Ulam Games and Online Computation with Imperfect Advice

Authors: Angelopoulos, Spyros ; Kamali, Shahin

Abstract | Document (772 KB) | BibTeX

Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

Authors: Arvind, Vikraman ; Joglekar, Pushkar S.

Abstract | Document (655 KB) | BibTeX

Entropic Risk for Turn-Based Stochastic Games

Authors: Baier, Christel ; Chatterjee, Krishnendu ; Meggendorfer, Tobias ; Piribauer, Jakob

Abstract | Document (807 KB) | BibTeX

Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification

Authors: Balun, Jiří ; Masopust, Tomáš ; Osička, Petr

Abstract | Document (1,010 KB) | BibTeX

Separating Automatic Relations

Authors: Barceló, Pablo ; Figueira, Diego ; Morvan, Rémi

Abstract | Document (949 KB) | BibTeX

On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges

Authors: Binucci, Carla ; Liotta, Giuseppe ; Montecchiani, Fabrizio ; Ortali, Giacomo ; Piselli, Tommaso

Abstract | Document (1,272 KB) | BibTeX

Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations

Authors: Biton, Noy ; Levi, Reut ; Medina, Moti

Abstract | Document (932 KB) | BibTeX

Locality Theorems in Semiring Semantics

Authors: Bizière, Clotilde ; Grädel, Erich ; Naaf, Matthias

Abstract | Document (744 KB) | BibTeX

A Characterisation of Functions Computable in Polynomial Time and Space over the Reals with Discrete Ordinary Differential Equations: Simulation of Turing Machines with Analytic Discrete ODEs

Authors: Blanc, Manon ; Bournez, Olivier

Abstract | Document (904 KB) | BibTeX

MaxCut Above Guarantee

Authors: Bliznets, Ivan ; Epifanov, Vladislav

Abstract | Document (815 KB) | BibTeX

Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator

Authors: Bouillaguet, Charles ; Martinez, Florette ; Vergnaud, Damien

Abstract | Document (720 KB) | BibTeX

The Compositional Structure of Bayesian Inference

Authors: Braithwaite, Dylan ; Hedges, Jules ; St Clere Smithe, Toby

Abstract | Document (767 KB) | BibTeX

Deterministic Constrained Multilinear Detection

Authors: Brand, Cornelius ; Korchemna, Viktoriia ; Skotnica, Michael

Abstract | Document (677 KB) | BibTeX

Rational Verification for Nash and Subgame-Perfect Equilibria in Graph Games

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

Abstract | Document (655 KB) | BibTeX

On Property Testing of the Binary Rank

Authors: Bshouty, Nader H.

Abstract | Document (697 KB) | BibTeX

Short Definitions in Constraint Languages

Authors: Bulín, Jakub ; Kompatscher, Michael

Abstract | Document (740 KB) | BibTeX

The Online Simple Knapsack Problem with Reservation and Removability

Authors: Burjons, Elisabet ; Gehnen, Matthias ; Lotze, Henri ; Mock, Daniel ; Rossmanith, Peter

Abstract | Document (708 KB) | BibTeX

Parikh One-Counter Automata

Authors: Cadilhac, Michaël ; Ghosh, Arka ; Pérez, Guillermo A. ; Raha, Ritam

Abstract | Document (800 KB) | BibTeX

Modification Problems Toward Proper (Helly) Circular-Arc Graphs

Authors: Cao, Yixin ; Yuan, Hanchun ; Wang, Jianxin

Abstract | Document (718 KB) | BibTeX

Isometric Path Complexity of Graphs

Authors: Chakraborty, Dibyayan ; Chalopin, Jérémie ; Foucaud, Florent ; Vaxès, Yann

Abstract | Document (804 KB) | BibTeX

Support Size Estimation: The Power of Conditioning

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

Abstract | Document (688 KB) | BibTeX

Query Complexity of Search Problems

Authors: Chattopadhyay, Arkadev ; Dahiya, Yogesh ; Mahajan, Meena

Abstract | Document (805 KB) | BibTeX

Tight Algorithmic Applications of Clique-Width Generalizations

Authors: Chekan, Vera ; Kratsch, Stefan

Abstract | Document (758 KB) | BibTeX

An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams

Authors: Clément, Julien ; Genitrini, Antoine

Abstract | Document (945 KB) | BibTeX

Inductive Continuity via Brouwer Trees

Authors: Cohen, Liron ; da Rocha Paiva, Bruno ; Rahli, Vincent ; Tosun, Ayberk

Abstract | Document (1,103 KB) | BibTeX

Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games

Authors: Dantam, Mohan ; Mayr, Richard

Abstract | Document (784 KB) | BibTeX

Dynamic Planar Embedding Is in DynFO

Authors: Datta, Samir ; Khan, Asif ; Mukherjee, Anish

Abstract | Document (1,002 KB) | BibTeX

Universality and Forall-Exactness of Cost Register Automata with Few Registers

Authors: Daviaud, Laure ; Ryzhikov, Andrew

Abstract | Document (874 KB) | BibTeX

Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities

Authors: Demeulemeester, Tom ; Peters, Jannik

Abstract | Document (794 KB) | BibTeX

Recontamination Helps a Lot to Hunt a Rabbit

Authors: Dissaux, Thomas ; Fioravantes, Foivos ; Gahlawat, Harmender ; Nisse, Nicolas

Abstract | Document (790 KB) | BibTeX

String Diagrammatic Trace Theory

Authors: Earnshaw, Matthew ; Sobociński, Paweł

Abstract | Document (983 KB) | BibTeX

Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP

Authors: Egidy, Fabian ; Glaßer, Christian ; Herold, Martin

Abstract | Document (781 KB) | BibTeX

Finding a Highly Connected Steiner Subgraph and its Applications

Authors: Eiben, Eduard ; Majumdar, Diptapriyo ; Ramanujan, M. S.

Abstract | Document (795 KB) | BibTeX

FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Inamdar, Tanmay ; Koana, Tomohiro

Abstract | Document (674 KB) | BibTeX

Graph Connectivity with Noisy Queries

Authors: Fotakis, Dimitris ; Gergatsouli, Evangelia ; Pipis, Charilaos ; Stouras, Miltiadis ; Tzamos, Christos

Abstract | Document (975 KB) | BibTeX

Positive Data Languages

Authors: Frank, Florian ; Milius, Stefan ; Urbat, Henning

Abstract | Document (836 KB) | BibTeX

Parameterized Analysis of the Cops and Robber Game

Authors: Gahlawat, Harmender ; Zehavi, Meirav

Abstract | Document (940 KB) | BibTeX

An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width

Authors: Gargano, Luisa ; Rescigno, Adele A.

Abstract | Document (775 KB) | BibTeX

Depth-3 Circuits for Inner Product

Authors: Göös, Mika ; Guan, Ziyi ; Mosnoi, Tiberiu

Abstract | Document (782 KB) | BibTeX

On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)

Authors: Haase, Christoph ; Mansutti, Alessio ; Pouly, Amaury

Abstract | Document (941 KB) | BibTeX

The Covering Canadian Traveller Problem Revisited

Authors: Hahn, Niklas ; Xefteris, Michalis

Abstract | Document (803 KB) | BibTeX

On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric

Authors: Holznigenkemper, Jana ; Komusiewicz, Christian ; Morawietz, Nils ; Seeger, Bernhard

Abstract | Document (876 KB) | BibTeX

Fixed-Parameter Algorithms for Fair Hitting Set Problems

Authors: Inamdar, Tanmay ; Kanesh, Lawqueen ; Kundu, Madhumita ; Purohit, Nidhi ; Saurabh, Saket

Abstract | Document (831 KB) | BibTeX

Parameterized Approximation Scheme for Feedback Vertex Set

Authors: Jana, Satyabrata ; Lokshtanov, Daniel ; Mandal, Soumen ; Rai, Ashutosh ; Saurabh, Saket

Abstract | Document (909 KB) | BibTeX

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Authors: Johnson, Matthew ; Martin, Barnaby ; Pandey, Sukanya ; Paulusma, Daniël ; Smith, Siani ; van Leeuwen, Erik Jan

Abstract | Document (797 KB) | BibTeX

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids

Authors: Kobayashi, Yasuaki ; Kurita, Kazuhiro ; Wasa, Kunihiro

Abstract | Document (824 KB) | BibTeX

Formalizing Hyperspaces for Extracting Efficient Exact Real Computation

Authors: Konečný, Michal ; Park, Sewon ; Thies, Holger

Abstract | Document (1,113 KB) | BibTeX

Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity

Authors: Kontinen, Juha ; Sandström, Max ; Virtema, Jonni

Abstract | Document (726 KB) | BibTeX

Parameterized Complexity of Domination Problems Using Restricted Modular Partitions

Authors: Lafond, Manuel ; Luo, Weidong

Abstract | Document (858 KB) | BibTeX

Parameterized Max Min Feedback Vertex Set

Authors: Lampis, Michael ; Melissinos, Nikolaos ; Vasilakis, Manolis

Abstract | Document (753 KB) | BibTeX

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

Authors: Le Gall, François ; Miyamoto, Masayuki ; Nishimura, Harumichi

Abstract | Document (731 KB) | BibTeX

Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius

Authors: Lucke, Felicia ; Paulusma, Daniël ; Ries, Bernard

Abstract | Document (738 KB) | BibTeX

A Weyl Criterion for Finite-State Dimension and Applications

Authors: Lutz, Jack H. ; Nandakumar, Satyadev ; Pulari, Subin

Abstract | Document (790 KB) | BibTeX

On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Authors: Mayr, Peter

Abstract | Document (656 KB) | BibTeX

Parallel Enumeration of Parse Trees

Authors: Mikhelson, Margarita ; Okhotin, Alexander

Abstract | Document (1,132 KB) | BibTeX

Spartan Bipartite Graphs Are Essentially Elementary

Authors: Misra, Neeldhara ; Nanoti, Saraswati Girish

Abstract | Document (758 KB) | BibTeX

On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation

Authors: Nakamura, Yoshiki

Abstract | Document (1,198 KB) | BibTeX

Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals

Authors: Nandakumar, Satyadev ; S, Akhil ; Vishnoi, Prateek

Abstract | Document (772 KB) | BibTeX

On the Expressive Power of Regular Expressions with Backreferences

Authors: Nogami, Taisei ; Terauchi, Tachio

Abstract | Document (816 KB) | BibTeX

OBDD(Join) Proofs Cannot Be Balanced

Authors: Ovcharov, Sergei

Abstract | Document (757 KB) | BibTeX

Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits

Authors: Pago, Benedikt

Abstract | Document (842 KB) | BibTeX

A Super-Polynomial Separation Between Resolution and Cut-Free Sequent Calculus

Authors: Papamakarios, Theodoros

Abstract | Document (666 KB) | BibTeX

Realizing Finitely Presented Groups as Projective Fundamental Groups of SFTs

Authors: Paviet Salomon, Léo ; Vanier, Pascal

Abstract | Document (895 KB) | BibTeX

Deciding Predicate Logical Theories Of Real-Valued Functions

Authors: Ratschan, Stefan

Abstract | Document (714 KB) | BibTeX

A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs

Authors: Rong, Guozhen ; Yang, Yongjie ; Li, Wenjun

Abstract | Document (855 KB) | BibTeX

Probabilistic Input-Driven Pushdown Automata

Authors: Rose, Alex ; Okhotin, Alexander

Abstract | Document (713 KB) | BibTeX

Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation

Authors: Scheidt, Benjamin ; Schweikardt, Nicole

Abstract | Document (948 KB) | BibTeX

Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work

Authors: Schmidt, Jonas ; Schwentick, Thomas

Abstract | Document (674 KB) | BibTeX

On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages

Authors: Schmidt, Jonas ; Schwentick, Thomas ; Todtenhoefer, Jennifer

Abstract | Document (890 KB) | BibTeX

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors

Authors: Seppelt, Tim

Abstract | Document (839 KB) | BibTeX

Decomposing Finite Languages

Authors: Spenner, Daniel Alexander

Abstract | Document (807 KB) | BibTeX

Dependent k-Set Packing on Polynomoids

Authors: Tsai, Meng-Tsung ; Tsai, Shi-Chun ; Wu, Tsung-Ta

Abstract | Document (752 KB) | BibTeX

Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy

Authors: Uchizawa, Kei ; Abe, Haruki

Abstract | Document (673 KB) | BibTeX

Exact and Approximation Algorithms for Routing a Convoy Through a Graph

Authors: van Ee, Martijn ; Oosterwijk, Tim ; Sitters, René ; Wiese, Andreas

Abstract | Document (622 KB) | BibTeX

Ordinal Measures of the Set of Finite Multisets

Authors: Vialard, Isa

Abstract | Document (824 KB) | BibTeX

Checking Presence Reachability Properties on Parameterized Shared-Memory Systems

Authors: Waldburger, Nicolas

Abstract | Document (873 KB) | BibTeX

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

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)