MFCS 2023: 48TH INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

A
Abe, Haruki	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
Abu-Khzam, Faisal	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Achilleos, Antonis	Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
Ahvonen, Veeti	Descriptive complexity for distributed computing with circuits
Akian, Marianne	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Almagor, Shaull	The Geometry of Reachability in Continuous Vector Addition Systems with States
Angelopoulos, Spyros	Competitive Search in the Line and the Star with Predictions Rényi-Ulam Games and Online Computation with Imperfect Advice
Arvind, Vikraman	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
Ağaoğlu Çağırıcı, Deniz	Recognizing H-graphs – beyond circular-arc graphs
B
Baier, Christel	Entropic Risk for Turn-Based Stochastic Games
Balun, Jiří	Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification
Barcelo, Pablo	Separating Automatic Relations
Binucci, Carla	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Biton, Noy	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Bizière, Clotilde	Locality Theorems in Semiring Semantics
Blanc, Manon	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Bliznets, Ivan	MaxCut Above Guarantee
Bonamy, Marthe	Exploring the space of colourings with Kempe changes
Bouillaguet, Charles	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Bournez, Olivier	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Boyar, Joan	Online Algorithms with Predictions
Braithwaite, Dylan	The Compositional Structure of Bayesian Inference
Brand, Cornelius	Deterministic Constrained Multilinear Detection
Brice, Léonard	Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games
Bshouty, Nader	On Property Testing of the Binary Rank
Bulín, Jakub	Short definitions in constraint languages
Burjons, Elisabet	The Online Simple Knapsack Problem with Reservation and Removability
C
Cadilhac, Michaël	Parikh One-Counter Automata
Cao, Yixin	Modification Problems toward Proper (Helly) Circular-arc Graphs
Chakraborty, Dibyayan	Isometric path complexity of graphs
Chakraborty, Diptarka	Support Size Estimation: The Power of Conditioning
Chalki, Aggeliki	Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
Chalopin, Jérémie	Isometric path complexity of graphs
Chatterjee, Krishnendu	Entropic Risk for Turn-Based Stochastic Games
Chattopadhyay, Arkadev	Query Complexity of Search Problems
Chekan, Vera	Tight Algorithmic Applications of Clique-Width Generalizations
Clément, Julien	An iterative approach for counting reduced ordered binary decision diagrams
Cohen, Liron	Inductive Continuity via Brouwer Trees
Czumaj, Artur	Modern Parallel Algorithms
D
da Rocho Paiva, Bruno	Inductive Continuity via Brouwer Trees
Dahiya, Yogesh	Query Complexity of Search Problems
Dantam, Mohan	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
Datta, Samir	Dynamic Planar Embedding is in DynFO
Daviaud, Laure	Universality and Forall-Exactness of Cost Register Automata with Few Registers
Demeulemeester, Tom	Relaxed core stability for hedonic games with size-dependent utilities
Derbisz, Jan	Recognizing H-graphs – beyond circular-arc graphs
Dissaux, Thomas	Recontamination helps a lot to hunt a rabbit
E
Earnshaw, Matthew	String Diagrammatic Trace Theory
Egidy, Fabian	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Eiben, Eduard	Finding a Highly Connected Steiner Subgraph and its Applications
Epifanov, Vladislav	MaxCut Above Guarantee
F
Fernau, Henning	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Figueira, Diego	Separating Automatic Relations
Fioravantes, Foivos	Recontamination helps a lot to hunt a rabbit
Fomin, Fedor V.	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Fotakis, Dimitris	Graph Connectivity with Noisy Queries
Foucaud, Florent	Isometric path complexity of graphs
Frank, Florian	Positive Data Languages
G
Gahlawat, Harmender	Recontamination helps a lot to hunt a rabbit Parameterized Analysis of the Cops and Robber Game
Gargano, Luisa	A FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular Width
Gaubert, Stéphane	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Gehnen, Matthias	The Online Simple Knapsack Problem with Reservation and Removability
Genitrini, Antoine	An iterative approach for counting reduced ordered binary decision diagrams
Gergatsouli, Evangelia	Graph Connectivity with Noisy Queries
Ghosh, Arka	The Geometry of Reachability in Continuous Vector Addition Systems with States Parikh One-Counter Automata
Glaßer, Christian	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Golovach, Petr A.	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Grädel, Erich	Locality Theorems in Semiring Semantics
Guan, Ziyi	Depth-3 Circuits for Inner Product
Göös, Mika	Depth-3 Circuits for Inner Product
H
Haase, Christoph	On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
Hahn, Niklas	The Covering Canadian Traveller Problem Revisited
Hartmann, Tim	Recognizing H-graphs – beyond circular-arc graphs
Hedges, Jules	The Compositional Structure of Bayesian Inference
Heiman, Damian	Descriptive complexity for distributed computing with circuits
Hella, Lauri	Descriptive complexity for distributed computing with circuits
Herold, Martin	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Hliněný, Petr	Recognizing H-graphs – beyond circular-arc graphs
Holznigenkemper, Jana	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric
I
Inamdar, Tanmay	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges Fixed-Parameter Algorithms for Fair Hitting Set Problems
J
Jana, Satyabrata	Parameterized Approximation Scheme for Feedback Vertex Set
Joglekar, Pushkar	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
Johnson, Matthew	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
K
Kamali, Shahin	Rényi-Ulam Games and Online Computation with Imperfect Advice
Kanesh, Lawqueen	Fixed-Parameter Algorithms for Fair Hitting Set Problems
Khan, Asif	Dynamic Planar Embedding is in DynFO
Koana, Tomohiro	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Kobayashi, Yasuaki	Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
Kompatscher, Michael	Short definitions in constraint languages
Komusiewicz, Christian	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric
Konecny, Michal	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
Kontinen, Juha	Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
Korchemna, Viktoriia	Deterministic Constrained Multilinear Detection
Kovacs, Laura	Algebraic Reasoning for (Un)Solvable Loops
Kratochvíl, Jan	Recognizing H-graphs – beyond circular-arc graphs
Kratsch, Stefan	Tight Algorithmic Applications of Clique-Width Generalizations
Krawczyk, Tomasz	Recognizing H-graphs – beyond circular-arc graphs
Kumar, Gunjan	Support Size Estimation: The Power of Conditioning
Kundu, Madhumita	Fixed-Parameter Algorithms for Fair Hitting Set Problems
Kurita, Kazuhiro	Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
Kuusisto, Antti	Descriptive complexity for distributed computing with circuits
L
Lafond, Manuel	Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Lampis, Michael	Parameterized Max Min Feedback Vertex Set
Le Gall, Francois	Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
Levi, Reut	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Leys, Tim	The Geometry of Reachability in Continuous Vector Addition Systems with States
Li, Wenjun	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
Liotta, Giuseppe	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Lokshtanov, Daniel	Parameterized Approximation Scheme for Feedback Vertex Set
Lotze, Henri	The Online Simple Knapsack Problem with Reservation and Removability
Lucke, Felicia	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
Luo, Weidong	Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Lutz, Jack H.	A Weyl Criterion for Finite-State Dimension and Applications
M
Mahajan, Meena	Query Complexity of Search Problems
Majumdar, Diptapriyo	Finding a Highly Connected Steiner Subgraph and its Applications
Mandal, Soumen	Parameterized Approximation Scheme for Feedback Vertex Set
Mann, Kevin	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Mansutti, Alessio	On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
Martin, Barnaby	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Martinez, Florette	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Masopust, Tomáš	Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification
Mayr, Peter	On the complexity dichotomy for the satisfiability of systems of term equations over finite algebras
Mayr, Richard	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
Medina, Moti	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Meel, Kuldeep	Support Size Estimation: The Power of Conditioning
Meggendorfer, Tobias	Entropic Risk for Turn-Based Stochastic Games
Melissinos, Nikolaos	Parameterized Max Min Feedback Vertex Set
Mikhelson, Margarita	Parallel enumeration of parse trees
Milius, Stefan	Positive Data Languages
Misra, Neeldhara	Spartan Bipartite Graphs are Essentially Elementary
Miyamoto, Masayuki	Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
Mock, Daniel	The Online Simple Knapsack Problem with Reservation and Removability
Montecchiani, Fabrizio	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Morawietz, Nils	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric
Morvan, Rémi	Separating Automatic Relations
Mosnoi, Tiberiu	Depth-3 Circuits for Inner Product
Mukherjee, Anish	Dynamic Planar Embedding is in DynFO
N
Naaf, Matthias	Locality Theorems in Semiring Semantics
Naepels, Ulysse	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Nakamura, Yoshiki	On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
Nandakumar, Satyadev	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals A Weyl Criterion for Finite-State Dimension and Applications
Nanoti, Saraswati	Spartan Bipartite Graphs are Essentially Elementary
Nishimura, Harumichi	Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
Nisse, Nicolas	Recontamination helps a lot to hunt a rabbit
Nogami, Taisei	On the Expressive Power of Regular Expressions with Backreferences
O
Okhotin, Alexander	Probabilistic Input-driven Pushdown Automata Parallel enumeration of parse trees
Oosterwijk, Tim	Exact and approximation algorithms for routing a convoy through a graph
Ortali, Giacomo	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Osička, Petr	Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification
Ovcharov, Sergei	OBDD(join) Proofs Cannot be Balanced
P
Pago, Benedikt	Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits
Pandey, Sukanya	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Papamakarios, Theodoros	A super-polynomial separation between resolution and cut-free sequent calculus
Park, Sewon	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
Paulusma, Daniel	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Paviet Salomon, Léo	Realizing finitely presented groups as projective fundamental groups of SFTs
Peters, Jannik	Relaxed core stability for hedonic games with size-dependent utilities
Pipis, Charilaos	Graph Connectivity with Noisy Queries
Piribauer, Jakob	Entropic Risk for Turn-Based Stochastic Games
Piselli, Tommaso	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Pouly, Amaury	On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
Pulari, Subin	A Weyl Criterion for Finite-State Dimension and Applications
Purohit, Nidhi	Fixed-Parameter Algorithms for Fair Hitting Set Problems
Pérez, Guillermo	The Geometry of Reachability in Continuous Vector Addition Systems with States Parikh One-Counter Automata
R
Raha, Ritam	Parikh One-Counter Automata
Rahli, Vincent	Inductive Continuity via Brouwer Trees
Rai, Ashutosh	Parameterized Approximation Scheme for Feedback Vertex Set
Raskin, Jean-Francois	Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games
Ratschan, Stefan	Deciding Predicate Logical Theories of Real-Valued Functions
Rescigno, Adele Anna	A FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular Width
Ries, Bernard	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
Rong, Guozhen	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
Rose, Alex	Probabilistic Input-driven Pushdown Automata
Rossmanith, Peter	The Online Simple Knapsack Problem with Reservation and Removability
Ryzhikov, Andrew	Universality and Forall-Exactness of Cost Register Automata with Few Registers
S
S, Akhil	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
Sandström, Max	Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
Saurabh, Saket	Fixed-Parameter Algorithms for Fair Hitting Set Problems Parameterized Approximation Scheme for Feedback Vertex Set
Scheidt, Benjamin	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
Schmidt, Jonas	On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages Dynamic constant-time parallel graph algorithms with sub-linear work
Schweikardt, Nicole	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
Schwentick, Thomas	On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages Dynamic constant-time parallel graph algorithms with sub-linear work
Seeger, Bernhard	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric
Seppelt, Tim	Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
Sitters, Rene	Exact and approximation algorithms for routing a convoy through a graph
Skotnica, Michael	Deterministic Constrained Multilinear Detection
Smith, Siani	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Sobociński, Paweł	String Diagrammatic Trace Theory
Spenner, Daniel Alexander	Decomposing Finite Languages
Spirakis, Paul	Some Algorithmic Problems on Temporal Graphs
Sridharan, Ramanujan	Finding a Highly Connected Steiner Subgraph and its Applications
St Clere Smithe, Toby	The Compositional Structure of Bayesian Inference
Stouras, Miltiadis	Graph Connectivity with Noisy Queries
T
Terauchi, Tachio	On the Expressive Power of Regular Expressions with Backreferences
Terver, Basile	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Thies, Holger	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
Todtenhoefer, Jennifer	On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages
Tosun, Ayberk	Inductive Continuity via Brouwer Trees
Tsai, Meng-Tsung	Dependent k-Set Packing on Polynomoids
Tsai, Shi-Chun	Dependent k-Set Packing on Polynomoids
Tzamos, Christos	Graph Connectivity with Noisy Queries
U
Uchizawa, Kei	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
Urbat, Henning	Positive Data Languages
V
Van Den Bogaard, Marie	Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games
van Ee, Martijn	Exact and approximation algorithms for routing a convoy through a graph
van Leeuwen, Erik Jan	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Vanier, Pascal	Realizing finitely presented groups as projective fundamental groups of SFTs
Vasilakis, Manolis	Parameterized Max Min Feedback Vertex Set
Vaxès, Yann	Isometric path complexity of graphs
Vergnaud, Damien	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Vialard, Isa	Ordinal measures of the set of finite multisets
Virtema, Jonni	Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
Vishnoi, Prateek	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
W
Waldburger, Nicolas	Checking Presence Reachability Properties on Parameterized Shared-Memory Systems
Wang, Jianxin	Modification Problems toward Proper (Helly) Circular-arc Graphs
Wasa, Kunihiro	Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
Wiese, Andreas	Exact and approximation algorithms for routing a convoy through a graph
Wu, Tsung-Ta	Dependent k-Set Packing on Polynomoids
X
Xefteris, Michalis	The Covering Canadian Traveller Problem Revisited
Y
Yang, Yongjie	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
Yuan, Hanchun	Modification Problems toward Proper (Helly) Circular-arc Graphs
Z
Zehavi, Meirav	Parameterized Analysis of the Cops and Robber Game
Zeman, Peter	Recognizing H-graphs – beyond circular-arc graphs
Ç
Çağırıcı, Onur	Recognizing H-graphs – beyond circular-arc graphs

Disclaimer | Powered by EasyChair Smart Program