Portal - MFCS 2020

MFCS 2020	August 24-28, 2020, Prague, Czech Republic
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) Javier Esparza and Daniel Kráľ (Eds.)
ISBN 978-3-95977-159-7, LIPICS Vol. 170	ISSN 1868-8969

Additional Information

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

Authors

Ahn, Jungho

Akhoondian Amiri, Saeed

Chatterjee, Krishnendu

de Oliveira Oliveira, Mateus

Deligkas, Argyrios

Dey, Palash

dos Santos, Vinicius F.

Douéneau-Tabot, Gaëtan

Hansen, Kristoffer Arnsfelt

Hell, Pavol

Herrera-Poyatos, Andrés

Kļevickis, Vladislavs

Lindermayr, Alexander

Montecchiani, Fabrizio

Rabinovich, Alexander

Radhakrishnan, Jaikumar

Raftopoulou, Chrysanthi

Souza, Uéverton dos Santos

Sølvsten, Steffan Christ

van der Wegen, Marieke

van Leeuwen, Erik Jan

Veldt, Nate

Velusamy, Santhoshini

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Esparza, Javier ; Král', Daniel

Abstract | Document (348 KB) | BibTeX

Concurrent Games with Arbitrarily Many Players (Invited Talk)

Authors: Bertrand, Nathalie

Abstract | Document (447 KB) | BibTeX

Some Open Problems in Computational Geometry (Invited Talk)

Authors: Cabello, Sergio

Abstract | Document (470 KB) | BibTeX

List-Decodability of Structured Ensembles of Codes (Invited Talk)

Authors: Wootters, Mary

Abstract | Document (365 KB) | BibTeX

Isomorphism Problem for S_d-Graphs

Authors: Ağaoğlu, Deniz ; Hliněný, Petr

Abstract | Document (542 KB) | BibTeX

A Polynomial Kernel for 3-Leaf Power Deletion

Authors: Ahn, Jungho ; Eiben, Eduard ; Kwon, O-joung ; Oum, Sang-il

Abstract | Document (556 KB) | BibTeX

Complexity of Computing the Anti-Ramsey Numbers for Paths

Authors: Akhoondian Amiri, Saeed ; Popa, Alexandru ; Roghani, Mohammad ; Shahkarami, Golnoosh ; Soltani, Reza ; Vahidi, Hossein

Abstract | Document (975 KB) | BibTeX

Best Fit Bin Packing with Random Order Revisited

Authors: Albers, Susanne ; Khan, Arindam ; Ladewig, Leon

Abstract | Document (626 KB) | BibTeX

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Authors: Ambainis, Andris ; Balodis, Kaspars ; Iraids, Jānis ; Khadiev, Kamil ; Kļevickis, Vladislavs ; Prūsis, Krišjānis ; Shen, Yixin ; Smotrovs, Juris ; Vihrovs, Jevgēnijs

Abstract | Document (598 KB) | BibTeX

Dynamic Time Warping-Based Proximity Problems

Authors: Aronov, Boris ; Katz, Matthew J. ; Sulami, Elad

Abstract | Document (4,743 KB) | BibTeX

A Special Case of Rational Identity Testing and the Brešar-Klep Theorem

Authors: Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

Abstract | Document (506 KB) | BibTeX

Solving Packing Problems with Few Small Items Using Rainbow Matchings

Authors: Bannach, Max ; Berndt, Sebastian ; Maack, Marten ; Mnich, Matthias ; Lassota, Alexandra ; Rau, Malin ; Skambath, Malte

Abstract | Document (523 KB) | BibTeX

Decidability in Group Shifts and Group Cellular Automata

Authors: Béaur, Pierre ; Kari, Jarkko

Abstract | Document (458 KB) | BibTeX

Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain

Authors: Bharathi, Arpitha P. ; Mastrolilli, Monaldo

Abstract | Document (692 KB) | BibTeX

Layered Fan-Planar Graph Drawings

Authors: Biedl, Therese ; Chaplick, Steven ; Kaufmann, Michael ; Montecchiani, Fabrizio ; Nöllenburg, Martin ; Raftopoulou, Chrysanthi

Abstract | Document (745 KB) | BibTeX

Topological Influence and Locality in Swap Schelling Games

Authors: Bilò, Davide ; Bilò, Vittorio ; Lenzner, Pascal ; Molitor, Louise

Abstract | Document (684 KB) | BibTeX

Approximation in (Poly-) Logarithmic Space

Authors: Biswas, Arindam ; Raman, Venkatesh ; Saurabh, Saket

Abstract | Document (563 KB) | BibTeX

Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras

Authors: Bläser, Markus ; Lysikov, Vladimir

Abstract | Document (495 KB) | BibTeX

Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics

Authors: Böhm, Martin ; Hoeksma, Ruben ; Megow, Nicole ; Nölke, Lukas ; Simon, Bertrand

Abstract | Document (571 KB) | BibTeX

Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers

Authors: Bojańczyk, Mikołaj ; Schmude, Janusz

Abstract | Document (1,590 KB) | BibTeX

List Homomorphism Problems for Signed Graphs

Authors: Bok, Jan ; Brewster, Richard ; Feder, Tomás ; Hell, Pavol ; Jedličková, Nikola

Abstract | Document (585 KB) | BibTeX

On a Temporal Logic of Prefixes and Infixes

Authors: Bozzelli, Laura ; Montanari, Angelo ; Peron, Adriano ; Sala, Pietro

Abstract | Document (523 KB) | BibTeX

Simplified Game of Life: Algorithms and Complexity

Authors: Chatterjee, Krishnendu ; Ibsen-Jensen, Rasmus ; Jecker, Ismaël ; Svoboda, Jakub

Abstract | Document (480 KB) | BibTeX

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming

Authors: Chia, Nai-Hui ; Li, Tongyang ; Lin, Han-Hsuan ; Wang, Chunhao

Abstract | Document (620 KB) | BibTeX

PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations

Authors: Clément, Alexandre ; Perdrix, Simon

Abstract | Document (516 KB) | BibTeX

Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs

Authors: Conte, Alessio ; Crescenzi, Pierluigi ; Marino, Andrea ; Punzi, Giulia

Abstract | Document (699 KB) | BibTeX

Span Programs and Quantum Time Complexity

Authors: Cornelissen, Arjan ; Jeffery, Stacey ; Ozols, Maris ; Piedrafita, Alvaro

Abstract | Document (491 KB) | BibTeX

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

Authors: Deligkas, Argyrios ; Mertzios, George B. ; Spirakis, Paul G. ; Zamaraev, Viktor

Abstract | Document (512 KB) | BibTeX

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

Authors: Dey, Palash ; Radhakrishnan, Jaikumar ; Velusamy, Santhoshini

Abstract | Document (529 KB) | BibTeX

Register Transducers Are Marble Transducers

Authors: Douéneau-Tabot, Gaëtan ; Filiot, Emmanuel ; Gastin, Paul

Abstract | Document (541 KB) | BibTeX

Randomization in Non-Uniform Finite Automata

Authors: Ďuriš, Pavol ; Královič, Rastislav ; Královič, Richard ; Pardubská, Dana ; Pašen, Martin ; Rossmanith, Peter

Abstract | Document (526 KB) | BibTeX

Extending Nearly Complete 1-Planar Drawings in Polynomial Time

Authors: Eiben, Eduard ; Ganian, Robert ; Hamm, Thekla ; Klute, Fabian ; Nöllenburg, Martin

Abstract | Document (689 KB) | BibTeX

The Mergegram of a Dendrogram and Its Stability

Authors: Elkin, Yury ; Kurlin, Vitaliy

Abstract | Document (594 KB) | BibTeX

Synchronizing Deterministic Push-Down Automata Can Be Really Hard

Authors: Fernau, Henning ; Wolf, Petra ; Yamakami, Tomoyuki

Abstract | Document (585 KB) | BibTeX

Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

Authors: Fijalkow, Nathanaël ; Gawrychowski, Paweł ; Ohlmann, Pierre

Abstract | Document (550 KB) | BibTeX

Building Large k-Cores from Sparse Graphs

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

Abstract | Document (549 KB) | BibTeX

The Complexity of Approximating the Complex-Valued Potts Model

Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Herrera-Poyatos, Andrés

Abstract | Document (550 KB) | BibTeX

Fast Algorithms for General Spin Systems on Bipartite Expanders

Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Stewart, James

Abstract | Document (586 KB) | BibTeX

Linear High-Order Deterministic Tree Transducers with Regular Look-Ahead

Authors: Gallot, Paul D. ; Lemay, Aurélien ; Salvati, Sylvain

Abstract | Document (461 KB) | BibTeX

Graph Clustering in All Parameter Regimes

Authors: Gan, Junhao ; Gleich, David F. ; Veldt, Nate ; Wirth, Anthony ; Zhang, Xin

Abstract | Document (673 KB) | BibTeX

A Quasiorder-Based Perspective on Residual Automata

Authors: Ganty, Pierre ; Gutiérrez, Elena ; Valero, Pedro

Abstract | Document (529 KB) | BibTeX

Fractional Covers of Hypergraphs with Bounded Multi-Intersection

Authors: Gottlob, Georg ; Lanzinger, Matthias ; Pichler, Reinhard ; Razgon, Igor

Abstract | Document (494 KB) | BibTeX

Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach

Authors: Guo, Zeyu

Abstract | Document (607 KB) | BibTeX

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

Authors: Gupta, Chetan ; Sharma, Vimal Raj ; Tewari, Raghunath

Abstract | Document (498 KB) | BibTeX

Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

Authors: Gürpınar, Emirhan ; Romashchenko, Andrei

Abstract | Document (422 KB) | BibTeX

∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

Authors: Hansen, Kristoffer Arnsfelt ; Sølvsten, Steffan Christ

Abstract | Document (553 KB) | BibTeX

Minimum 0-Extension Problems on Directed Metrics

Authors: Hirai, Hiroshi ; Mizutani, Ryuhei

Abstract | Document (653 KB) | BibTeX

Hierarchical Clusterings of Unweighted Graphs

Authors: Høgemo, Svein ; Paul, Christophe ; Telle, Jan Arne

Abstract | Document (505 KB) | BibTeX

On Affine Reachability Problems

Authors: Jaax, Stefan ; Kiefer, Stefan

Abstract | Document (479 KB) | BibTeX

Structural Parameterizations of Clique Coloring

Authors: Jaffke, Lars ; Lima, Paloma T. ; Philip, Geevarghese

Abstract | Document (741 KB) | BibTeX

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Authors: Jaffke, Lars ; de Oliveira Oliveira, Mateus ; Tiwary, Hans Raj

Abstract | Document (555 KB) | BibTeX

Unary Prime Languages

Authors: Jecker, Ismaël ; Kupferman, Orna ; Mazzocchi, Nicolas

Abstract | Document (584 KB) | BibTeX

A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes

Authors: Jelínek, Vít ; Opler, Michal ; Pekárek, Jakub

Abstract | Document (696 KB) | BibTeX

Quantum-Inspired Classical Algorithms for Singular Value Transformation

Authors: Jethwani, Dhawal ; Le Gall, François ; Singh, Sanjay K.

Abstract | Document (539 KB) | BibTeX

On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems

Authors: Karimov, Toghrul ; Ouaknine, Joël ; Worrell, James

Abstract | Document (518 KB) | BibTeX

Even Faster Algorithms for CSAT Over supernilpotent Algebras

Authors: Kawałek, Piotr ; Krzaczkowski, Jacek

Abstract | Document (484 KB) | BibTeX

Continuous and Monotone Machines

Authors: Konečný, Michal ; Steinberg, Florian ; Thies, Holger

Abstract | Document (584 KB) | BibTeX

U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited

Authors: Kratochvíl, Jan ; Masařík, Tomáš ; Novotná, Jana

Abstract | Document (680 KB) | BibTeX

Regular Resynchronizability of Origin Transducers Is Undecidable

Authors: Kuperberg, Denis ; Martens, Jan

Abstract | Document (526 KB) | BibTeX

On Repetition Languages

Authors: Kupferman, Orna ; Leshkowitz, Ofer

Abstract | Document (524 KB) | BibTeX

Efficient Enumerations for Minimal Multicuts and Multiway Cuts

Authors: Kurita, Kazuhiro ; Kobayashi, Yasuaki

Abstract | Document (1,124 KB) | BibTeX

Complexity of Counting First-Order Logic for the Subword Order

Authors: Kuske, Dietrich ; Schwarz, Christian

Abstract | Document (438 KB) | BibTeX

Sensitivity Lower Bounds from Linear Dependencies

Authors: Laplante, Sophie ; Naserasr, Reza ; Sunny, Anupa

Abstract | Document (463 KB) | BibTeX

Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes

Authors: Lima, Paloma T. ; van Leeuwen, Erik Jan ; van der Wegen, Marieke

Abstract | Document (530 KB) | BibTeX

Reducing Graph Transversals via Edge Contractions

Authors: Lima, Paloma T. ; dos Santos, Vinicius F. ; Sau, Ignasi ; Souza, Uéverton S.

Abstract | Document (854 KB) | BibTeX

Elimination Distance to Bounded Degree on Planar Graphs

Authors: Lindermayr, Alexander ; Siebertz, Sebastian ; Vigny, Alexandre

Abstract | Document (478 KB) | BibTeX

Analysing Spatial Properties on Neighbourhood Spaces

Authors: Linker, Sven ; Papacchini, Fabio ; Sevegnani, Michele

Abstract | Document (496 KB) | BibTeX

Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups

Authors: Lohrey, Markus ; Zetzsche, Georg

Abstract | Document (558 KB) | BibTeX

A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Authors: Lopes, Raul ; Sau, Ignasi

Abstract | Document (621 KB) | BibTeX

Regular Choice Functions and Uniformisations For countable Domains

Authors: Michielini, Vincent ; Skrzypczak, Michał

Abstract | Document (509 KB) | BibTeX

Quick Separation in Chordal and Split Graphs

Authors: Misra, Pranabendu ; Panolan, Fahad ; Rai, Ashutosh ; Saurabh, Saket ; Sharma, Roohani

Abstract | Document (649 KB) | BibTeX

A Timecop’s Work Is Harder Than You Think

Authors: Morawietz, Nils ; Rehs, Carolin ; Weller, Mathias

Abstract | Document (570 KB) | BibTeX

Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests

Authors: Murthy, Janaky ; Nair, Vineet ; Saha, Chandan

Abstract | Document (587 KB) | BibTeX

Randomness and Effective Dimension of Continued Fractions

Authors: Nandakumar, Satyadev ; Vishnoi, Prateek

Abstract | Document (474 KB) | BibTeX

Optimally Resilient Strategies in Pushdown Safety Games

Authors: Neider, Daniel ; Totzke, Patrick ; Zimmermann, Martin

Abstract | Document (508 KB) | BibTeX

On the Parameterized Complexity of Deletion to ℋ-Free Strong Components

Authors: Neogi, Rian ; Ramanujan, M. S. ; Saurabh, Saket ; Sharma, Roohani

Abstract | Document (625 KB) | BibTeX

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

Authors: Ogihara, Mitsunori ; Uchizawa, Kei

Abstract | Document (451 KB) | BibTeX

Preservation of Equations by Monoidal Monads

Authors: Parlant, Louis ; Rot, Jurriaan ; Silva, Alexandra ; Westerbaan, Bas

Abstract | Document (5,718 KB) | BibTeX

VC Density of Set Systems Definable in Tree-Like Graphs

Authors: Paszke, Adam ; Pilipczuk, Michał

Abstract | Document (770 KB) | BibTeX

All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words

Authors: Peltomäki, Jarkko ; Whiteland, Markus A.

Abstract | Document (459 KB) | BibTeX

Ambiguity Hierarchy of Regular Infinite Tree Languages

Authors: Rabinovich, Alexander ; Tiferet, Doron

Abstract | Document (528 KB) | BibTeX

Palindromic k-Factorization in Pure Linear Time

Authors: Rubinchik, Mikhail ; Shur, Arseny M.

Abstract | Document (653 KB) | BibTeX

Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Authors: Sau, Ignasi ; Souza, Uéverton dos Santos

Abstract | Document (980 KB) | BibTeX

Classically Simulating Quantum Circuits with Local Depolarizing Noise

Authors: Takahashi, Yasuhiro ; Takeuchi, Yuki ; Tani, Seiichiro

Abstract | Document (597 KB) | BibTeX

An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints

Authors: Thắng, Nguyễn Kim

Abstract | Document (485 KB) | BibTeX

The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains

Authors: Viola, Caterina ; Živný, Stanislav

Abstract | Document (513 KB) | BibTeX

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

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)