MFCS 2022: 47TH INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

A
Abhinav, Ankit	Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Abramsky, Samson	Comonadic semantics for hybrid logic
Adamson, Duncan	The Complexity of Periodic Energy Minimisation
Akshay, S.	On Synthesizing Computable Skolem Functions for First Order Logic
Amarilli, Antoine	Weighted counting of matchings in unbounded-treewidth graph families
Angelini, Patrizio	On Upward-Planar L-Drawings of Graphs RAC Drawings of Graphs with Low Degree
Auger, David	Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
B
Bandopadhyay, Susobhan	Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Banik, Aritra	Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Bar-Noy, Amotz	On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph Graph Realization of Distance Sets
Bednarczyk, Bartosz	Towards a Model Theory of Ordered Logics: Expressivity and Interpolation
Bekos, Michael A.	RAC Drawings of Graphs with Low Degree
Beniamini, Gal	Algebraic Representations of Unique Bipartite Perfect Matching
Berendsohn, Benjamin Aram	Fixed-point cycles and approximate EFX allocations
Bhargav, C. S.	Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
Bhyravarapu, Sriram	Conflict-free Coloring on Claw-free graphs and Interval graphs
Bilu, Yuri	Skolem Meets Schanuel
Boehmer, Niclas	Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Bojko, Dominik	Tree exploration in dual-memory model
Bonacina, Ilario	On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Booth, Robert	Complete ZX-calculi for the stabiliser fragment in odd prime dimensions
Boyadzhiyska, Simona	Fixed-point cycles and approximate EFX allocations
Brückner, Guido	Extending Partial Representations of Circle Graphs in Near-Linear Time
Bullinger, Martin	Boundaries to Single-Agent Stability in Additively Separable Hedonic Games
Böhnlein, Toni	On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph
C
Cai, Jin-Yi	Bounded Degree Nonnegative Counting CSP
Carette, Titouan	Complete ZX-calculi for the stabiliser fragment in odd prime dimensions
Carton, Olivier	Continuous rational functions are deterministic regular
Chakraborty, Supratik	On Synthesizing Computable Skolem Functions for First Order Logic
Chalopin, Jérémie	Sample compression schemes for balls in graphs
Chaplick, Steven	On Upward-Planar L-Drawings of Graphs
Chen, Yijia	On Algorithms Based on Finitely Many Homomorphism Counts
Chepoi, Victor	Sample compression schemes for balls in graphs
Chistikov, Dmitry	Higher-Order Quantified Boolean Satisfiability
Choudhary, Pratibha	On Kernels for d-Path Vertex Cover
Christiansen, Aleksander Bjørn Grodt Christiansen	On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
Clément, Alexandre	Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Colcombet, Thomas	A Complexity Approach to Tree Algebras: the Polynomial Case
Cornelsen, Sabine	On Upward-Planar L-Drawings of Graphs
Coucheney, Pierre	Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
Creignou, Nadia	Enumeration Classes Defined by Circuits
D
D'Costa, Julian	Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set The Pseudo-Reachability Problem for Affine Dynamical Systems
Da Lozzo, Giordano	On Upward-Planar L-Drawings of Graphs
Deligkas, Argyrios	The Complexity of Periodic Energy Minimisation
Deng, Mingyang	New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Dereniowski, Dariusz	Constant-factor approximation algorithm for binary search in trees with monotonic query times
Dong, Ruiwen	On the Identity Problem for Unitriangular Matrices of Dimension Four
dos Santos, Vinicius F.	Reducing the Vertex Cover Number via Edge Contractions
Douéneau-Tabot, Gaëtan	Continuous rational functions are deterministic regular
Duhaze, Loric	Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
Durand, Arnaud	Enumeration Classes Defined by Circuits
Dutta, Sagnik	Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
E
Earnshaw, Matthew	Regular Monoidal Languages
Egidy, Fabian	Oracle with P = NP ∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
Ehrmanntraut, Anton	Oracle with P = NP ∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
El Maalouly, Nicolas	Exact Matching in Graphs of Bounded Independence Number
Emdin, Gregory	CNF Encodings of Parity
F
Fagin, Ronald	On the Number of Quantifiers as a Complexity Measure
Fan, Jing	Approximation algorithms for covering vertices by long paths
Fernandez, Alexandre	Non-Determinism in Lindenmayer Systems and Global Transformations
Flum, Jörg	On Algorithms Based on Finitely Many Homomorphism Counts
Fratani, Severine	A robust class of languages of 2-nested words
G
Galby, Esther	Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Galesi, Nicola	On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Gervens, Timo	Graph Similarity Based on Matrix Norms
Glaßer, Christian	Oracle with P = NP ∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
Gong, Mingyang	Approximation algorithms for covering vertices by long paths
Gotfryd, Karol	Tree exploration in dual-memory model
Gregor, Petr	The Hamilton compression of highly symmetric graphs
Grohe, Martin	Graph Similarity Based on Matrix Norms
Gusev, Vladimir	The Complexity of Periodic Energy Minimisation
H
Haase, Christoph	Higher-Order Quantified Boolean Satisfiability
Hadizadeh, Zahra	Higher-Order Quantified Boolean Satisfiability
Hartmann, Tim A.	Dispersing Obnoxious Facilities on Graphs by Rounding Distances
Haviv, Ishay	On the Binary and Boolean Rank of Regular Matrices
Heeger, Klaus	Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Hemaspaandra, Lane A.	Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Heurtel, Nicolas	LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Holm, Jacob	On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
I
Ito, Takehiro	Independent set reconfiguration on directed graphs
Itsykson, Dmitry	Automating OBDD proofs is NP-hard
Iwamasa, Yuni	Independent set reconfiguration on directed graphs
J
Jaakkola, Reijo	Towards a Model Theory of Ordered Logics: Expressivity and Interpolation
Jaquard, Arthur	A Complexity Approach to Tree Algebras: the Polynomial Case
Juvekar, Mandar	Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
K
Kalyanasundaram, Subrahmanyam	Conflict-free Coloring on Claw-free graphs and Interval graphs
Kanellopoulos, Panagiotis	Not all Strangers are the Same: The Impact of Tolerance in Schelling Games
Karimov, Toghrul	The Pseudo-Reachability Problem for Affine Dynamical Systems
Katheder, Julia	RAC Drawings of Graphs with Low Degree
Kaufmann, Michael	RAC Drawings of Graphs with Low Degree
Kenison, George	On the Skolem Problem for Reversible Sequences
Khazaliya, Liana	Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Kissinger, Aleks	Higher-order causal theories are models of BV-logic
Klin, Bartek	Countdown mu-calculus
Klobas, Nina	The complexity of computing optimum labelings for temporal connectivity
Kobayashi, Yasuaki	Independent set reconfiguration on directed graphs Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Koh, Zhuan Khye	Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
Komarath, Balagopal	Rabbits approximate, cows compute exactly!
Komusiewicz, Christian	Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard
Kowalski, Dariusz	Tree exploration in dual-memory model
Kozma, Laszlo	Fixed-point cycles and approximate EFX allocations
Kołodziejski, Jędrzej	Countdown mu-calculus
Kulikov, Alexander	SAT-based Circuit Local Improvement CNF Encodings of Parity
Kyropoulou, Maria	Not all Strangers are the Same: The Impact of Tolerance in Schelling Games
L
Lauria, Massimo	On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Le, Hoang-Oanh	Complexity of the Cluster Vertex Deletion problem on H-free graphs
Le, Van Bang	Complexity of the Cluster Vertex Deletion problem on H-free graphs
Lefaucheux, Engel	Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Lenchner, Jonathan	On the Number of Quantifiers as a Complexity Measure
Lendl, Stefan	Dispersing Obnoxious Facilities on Graphs by Rounding Distances
Lima, Paloma T.	Reducing the Vertex Cover Number via Edge Contractions
Lin, Guohui	Approximation algorithms for covering vertices by long paths
Liu, Mingjun	On Algorithms Based on Finitely Many Homomorphism Counts
Liu, Mo	Generalized Bundled Fragments of First-order Modal Logic
Loho, Georg	Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
Lohrey, Markus	Streaming word problems Membership problems in finite groups
Luca, Florian	A Universal Skolem Set of Positive Lower Density Skolem Meets Schanuel
Lück, Lukas	Streaming word problems
M
Maignan, Luidnel	Non-Determinism in Lindenmayer Systems and Global Transformations
Majumdar, Rupak	The Pseudo-Reachability Problem for Affine Dynamical Systems
Mansfield, Shane	LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Mansutti, Alessio	Higher-Order Quantified Boolean Satisfiability
Marsden, Dan	Comonadic semantics for hybrid logic
Mathew, Rogers	Conflict-free Coloring on Claw-free graphs and Interval graphs
Maurras, Guillaume	A robust class of languages of 2-nested words
Mc Inerney, Fionn	Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters Sample compression schemes for balls in graphs
Merino, Arturo	The Hamilton compression of highly symmetric graphs
Mertzios, George	The complexity of computing optimum labelings for temporal connectivity
Michaliszyn, Jakub	Learning Deterministic Visibly Pushdown Automata under Accessible Stack
Mihajlin, Ivan	CNF Encodings of Parity
Miyano, Eiji	Approximation algorithms for covering vertices by long paths
Molter, Hendrik	The complexity of computing optimum labelings for temporal connectivity
Monet, Mikaël	Weighted counting of matchings in unbounded-treewidth graph families
Morawietz, Nils	Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard
Mütze, Torsten	The Hamilton compression of highly symmetric graphs
N
Nadjimzadah, Arian	Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Nagano, Shunsuke	Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Nakahata, Yu	Independent set reconfiguration on directed graphs
Neumann, Eike	Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Niedermeier, Rolf	Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Nieuwveld, Joris	Skolem Meets Schanuel
O
Otachi, Yota	Independent set reconfiguration on directed graphs Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Otop, Jan	Learning Deterministic Visibly Pushdown Automata under Accessible Stack
Ouaknine, Joel	Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set A Universal Skolem Set of Positive Lower Density The Pseudo-Reachability Problem for Affine Dynamical Systems Skolem Meets Schanuel
P
Padmanabha, Anantha	Generalized Bundled Fragments of First-order Modal Logic
Pajak, Dominik	Tree exploration in dual-memory model
Pandey, Anurag	Rabbits approximate, cows compute exactly!
Parnas, Michal	On the Binary and Boolean Rank of Regular Matrices
Pechenev, Danila	SAT-based Circuit Local Improvement
Peleg, David	On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph Graph Realization of Distance Sets
Perdrix, Simon	Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Perry, Mor	Graph Realization of Distance Sets
Peteler, Dominik	Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order
Pfister, Maximilian	RAC Drawings of Graphs with Low Degree
Phillips, Patrick A.	Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Potapov, Igor	The Complexity of Periodic Energy Minimisation
Purser, David	Skolem Meets Schanuel
Q
Quaas, Karin	Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order
R
Rabinovich, Alexander	On Uniformization in the Full Binary Tree
Ramanujam, R.	Generalized Bundled Fragments of First-order Modal Logic
Ramanujan, M. S.	An exact algorithm for Knot-free Vertex Deletion
Ratel, Sébastien	Sample compression schemes for balls in graphs
Rawitz, Dror	On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph Graph Realization of Distance Sets
Reynier, Pierre-Alain	A robust class of languages of 2-nested words
Riazanov, Artur	Automating OBDD proofs is NP-hard
Rigo, Michel	On extended boundary sequences of morphic and Sturmian words
Rosowski, Andreas	Membership problems in finite groups
Rotenberg, Eva	On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
Rutter, Ignaz	Extending Partial Representations of Circle Graphs in Near-Linear Time
S
Sahu, Abhishek	An exact algorithm for Knot-free Vertex Deletion
Salamati, Mahmoud	The Pseudo-Reachability Problem for Affine Dynamical Systems
Sau, Ignasi	Reducing the Vertex Cover Number via Edge Contractions
Saurabh, Nitin	Rabbits approximate, cows compute exactly!
Saurabh, Saket	An exact algorithm for Knot-free Vertex Deletion Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Saxena, Nitin	Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
Sharma, Roohani	Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Simmons, Will	Higher-order causal theories are models of BV-logic
Slezkin, Nikita	SAT-based Circuit Local Improvement CNF Encodings of Parity
Sobociński, Paweł	Regular Monoidal Languages
Souza, Uéverton S.	Reducing the Vertex Cover Number via Edge Contractions
Spicher, Antoine	Non-Determinism in Lindenmayer Systems and Global Transformations
Spirakis, Paul	The complexity of computing optimum labelings for temporal connectivity
Steiner, Raphael	Exact Matching in Graphs of Bounded Independence Number
Stipulanti, Manon	On extended boundary sequences of morphic and Sturmian words
Stumpf, Peter	Extending Partial Representations of Circle Graphs in Near-Linear Time
Suchý, Ondřej	On Kernels for d-Path Vertex Cover
Szabo, Daniel	Bounded Degree Nonnegative Counting CSP
T
Takahashi, Masahiro	Independent set reconfiguration on directed graphs
Tale, Prafullkumar	Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters Reducing the Vertex Cover Number via Edge Contractions
Tani, Seiichiro	Space-Bounded Unitary Quantum Computation with Postselection
Thomassen, Carsten	On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
V
Valiron, Benoît	LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Vassilevska Williams, Virginia	New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Vaxès, Yann	Sample compression schemes for balls in graphs
Verma, Shaily	An exact algorithm for Knot-free Vertex Deletion
Vollmer, Heribert	Enumeration Classes Defined by Circuits
Voudouris, Alexandros	Not all Strangers are the Same: The Impact of Tolerance in Schelling Games
Vyas, Nikhil	On the Number of Quantifiers as a Complexity Measure
W
Wang, Haitao	Computing the Minimum Bottleneck Moving Spanning Tree
Wang, Yanjing	Generalized Bundled Fragments of First-order Modal Logic
Wasa, Kunihiro	Independent set reconfiguration on directed graphs
Whiteland, Markus	On extended boundary sequences of morphic and Sturmian words
Williams, Ryan	On the Number of Quantifiers as a Complexity Measure
Worrell, James	Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set A Universal Skolem Set of Positive Lower Density The Pseudo-Reachability Problem for Affine Dynamical Systems Skolem Meets Schanuel
Wrosz, Izajasz	Constant-factor approximation algorithm for binary search in trees with monotonic query times
X
Xiao, Mingyu	Improved Approximation Algorithms for the Traveling Tournament Problem
Xu, Chao	Improved Approximation Algorithms for the Traveling Tournament Problem
Xun, Zhiyang	On Algorithms Based on Finitely Many Homomorphism Counts
Z
Zetzsche, Georg	Membership problems in finite groups
Zhao, Jingyang	Improved Approximation Algorithms for the Traveling Tournament Problem
Zhao, Yiming	Computing the Minimum Bottleneck Moving Spanning Tree
Zhong, Ziqian	New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Ó
Ó Conghaile, Adam	Cohomology in Constraint Satisfaction and Structure Isomorphism
Č
Červený, Radovan	On Kernels for d-Path Vertex Cover

Disclaimer | Powered by EasyChair Smart Program