![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
45th MFCS 2020: Prague, Czech Republic
- Javier Esparza
, Daniel Král'
:
45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic. LIPIcs 170, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-159-7 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:18
- Nathalie Bertrand
:
Concurrent Games with Arbitrarily Many Players (Invited Talk). 1:1-1:8 - Sergio Cabello
:
Some Open Problems in Computational Geometry (Invited Talk). 2:1-2:6 - Mary Wootters:
List-Decodability of Structured Ensembles of Codes (Invited Talk). 3:1-3:5 - Deniz Agaoglu
, Petr Hlinený
:
Isomorphism Problem for S_d-Graphs. 4:1-4:14 - Jungho Ahn, Eduard Eiben
, O-joung Kwon
, Sang-il Oum
:
A Polynomial Kernel for 3-Leaf Power Deletion. 5:1-5:14 - Saeed Akhoondian Amiri
, Alexandru Popa
, Mohammad Roghani
, Golnoosh Shahkarami
, Reza Soltani
, Hossein Vahidi
:
Complexity of Computing the Anti-Ramsey Numbers for Paths. 6:1-6:14 - Susanne Albers, Arindam Khan, Leon Ladewig:
Best Fit Bin Packing with Random Order Revisited. 7:1-7:15 - Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev
, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen
, Juris Smotrovs
, Jevgenijs Vihrovs:
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. 8:1-8:14 - Boris Aronov
, Matthew J. Katz, Elad Sulami:
Dynamic Time Warping-Based Proximity Problems. 9:1-9:12 - Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay:
A Special Case of Rational Identity Testing and the Brešar-Klep Theorem. 10:1-10:14 - Max Bannach
, Sebastian Berndt
, Marten Maack
, Matthias Mnich
, Alexandra Lassota
, Malin Rau
, Malte Skambath
:
Solving Packing Problems with Few Small Items Using Rainbow Matchings. 11:1-11:14 - Pierre Béaur, Jarkko Kari
:
Decidability in Group Shifts and Group Cellular Automata. 12:1-12:13 - Arpitha P. Bharathi, Monaldo Mastrolilli:
Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain. 13:1-13:13 - Therese Biedl
, Steven Chaplick
, Michael Kaufmann
, Fabrizio Montecchiani
, Martin Nöllenburg
, Chrysanthi N. Raftopoulou
:
Layered Fan-Planar Graph Drawings. 14:1-14:13 - Davide Bilò
, Vittorio Bilò
, Pascal Lenzner
, Louise Molitor
:
Topological Influence and Locality in Swap Schelling Games. 15:1-15:15 - Arindam Biswas
, Venkatesh Raman
, Saket Saurabh
:
Approximation in (Poly-) Logarithmic Space. 16:1-16:15 - Markus Bläser, Vladimir Lysikov
:
Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. 17:1-17:15 - Martin Böhm, Ruben Hoeksma
, Nicole Megow
, Lukas Nölke
, Bertrand Simon
:
Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics. 18:1-18:15 - Mikolaj Bojanczyk, Janusz Schmude
:
Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers. 19:1-19:14 - Jan Bok
, Richard C. Brewster
, Tomás Feder, Pavol Hell
, Nikola Jedlicková
:
List Homomorphism Problems for Signed Graphs. 20:1-20:14 - Laura Bozzelli, Angelo Montanari, Adriano Peron, Pietro Sala
:
On a Temporal Logic of Prefixes and Infixes. 21:1-21:14 - Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker, Jakub Svoboda
:
Simplified Game of Life: Algorithms and Complexity. 22:1-22:13 - Nai-Hui Chia, Tongyang Li
, Han-Hsuan Lin, Chunhao Wang:
Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming. 23:1-23:15 - Alexandre Clément
, Simon Perdrix
:
PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations. 24:1-24:14 - Alessio Conte, Pierluigi Crescenzi
, Andrea Marino, Giulia Punzi:
Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs. 25:1-25:14 - Arjan Cornelissen, Stacey Jeffery, Maris Ozols
, Alvaro Piedrafita:
Span Programs and Quantum Time Complexity. 26:1-26:14 - Argyrios Deligkas, George B. Mertzios
, Paul G. Spirakis
, Viktor Zamaraev
:
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. 27:1-27:13 - Palash Dey, Jaikumar Radhakrishnan, Santhoshini Velusamy
:
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. 28:1-28:12 - Gaëtan Douéneau-Tabot, Emmanuel Filiot
, Paul Gastin
:
Register Transducers Are Marble Transducers. 29:1-29:14 - Pavol Duris, Rastislav Královic, Richard Královic, Dana Pardubská, Martin Pasen
, Peter Rossmanith:
Randomization in Non-Uniform Finite Automata. 30:1-30:13 - Eduard Eiben
, Robert Ganian
, Thekla Hamm
, Fabian Klute
, Martin Nöllenburg
:
Extending Nearly Complete 1-Planar Drawings in Polynomial Time. 31:1-31:16 - Yury Elkin, Vitaliy Kurlin
:
The Mergegram of a Dendrogram and Its Stability. 32:1-32:13 - Henning Fernau
, Petra Wolf
, Tomoyuki Yamakami:
Synchronizing Deterministic Push-Down Automata Can Be Really Hard. 33:1-33:15 - Nathanaël Fijalkow
, Pawel Gawrychowski
, Pierre Ohlmann:
Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. 34:1-34:15 - Fedor V. Fomin
, Danil Sagunov
, Kirill Simonov
:
Building Large k-Cores from Sparse Graphs. 35:1-35:14 - Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos:
The Complexity of Approximating the Complex-Valued Potts Model. 36:1-36:14 - Andreas Galanis, Leslie Ann Goldberg, James Stewart:
Fast Algorithms for General Spin Systems on Bipartite Expanders. 37:1-37:14 - Paul Gallot, Aurélien Lemay, Sylvain Salvati:
Linear High-Order Deterministic Tree Transducers with Regular Look-Ahead. 38:1-38:13 - Junhao Gan
, David F. Gleich
, Nate Veldt
, Anthony Wirth
, Xin Zhang:
Graph Clustering in All Parameter Regimes. 39:1-39:15 - Pierre Ganty
, Elena Gutiérrez, Pedro Valero
:
A Quasiorder-Based Perspective on Residual Automata. 40:1-40:14 - Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon:
Fractional Covers of Hypergraphs with Bounded Multi-Intersection. 41:1-41:14 - Zeyu Guo
:
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach. 42:1-42:14 - Chetan Gupta
, Vimal Raj Sharma, Raghunath Tewari:
Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs. 43:1-43:13 - Emirhan Gürpinar, Andrei E. Romashchenko
:
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. 44:1-44:14 - Kristoffer Arnsfelt Hansen
, Steffan Christ Sølvsten
:
∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games. 45:1-45:15 - Hiroshi Hirai
, Ryuhei Mizutani
:
Minimum 0-Extension Problems on Directed Metrics. 46:1-46:13 - Svein Høgemo, Christophe Paul, Jan Arne Telle:
Hierarchical Clusterings of Unweighted Graphs. 47:1-47:13 - Stefan Jaax, Stefan Kiefer:
On Affine Reachability Problems. 48:1-48:14 - Lars Jaffke
, Paloma T. Lima, Geevarghese Philip
:
Structural Parameterizations of Clique Coloring. 49:1-49:15 - Lars Jaffke
, Mateus de Oliveira Oliveira
, Hans Raj Tiwary:
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. 50:1-50:15 - Ismaël Jecker, Orna Kupferman, Nicolas Mazzocchi
:
Unary Prime Languages. 51:1-51:12 - Vít Jelínek
, Michal Opler
, Jakub Pekárek
:
A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes. 52:1-52:18 - Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh
:
Quantum-Inspired Classical Algorithms for Singular Value Transformation. 53:1-53:14 - Toghrul Karimov
, Joël Ouaknine, James Worrell:
On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems. 54:1-54:14 - Piotr Kawalek, Jacek Krzaczkowski
:
Even Faster Algorithms for CSAT Over supernilpotent Algebras. 55:1-55:13 - Michal Konecný
, Florian Steinberg, Holger Thies
:
Continuous and Monotone Machines. 56:1-56:16 - Jan Kratochvíl
, Tomás Masarík
, Jana Novotná
:
U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. 57:1-57:14 - Denis Kuperberg
, Jan Martens:
Regular Resynchronizability of Origin Transducers Is Undecidable. 58:1-58:14 - Orna Kupferman, Ofer Leshkowitz:
On Repetition Languages. 59:1-59:14 - Kazuhiro Kurita
, Yasuaki Kobayashi
:
Efficient Enumerations for Minimal Multicuts and Multiway Cuts. 60:1-60:14 - Dietrich Kuske, Christian Schwarz:
Complexity of Counting First-Order Logic for the Subword Order. 61:1-61:12 - Sophie Laplante, Reza Naserasr, Anupa Sunny:
Sensitivity Lower Bounds from Linear Dependencies. 62:1-62:14 - Paloma T. Lima, Erik Jan van Leeuwen, Marieke van der Wegen
:
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes. 63:1-63:13 - Paloma T. Lima, Vinícius Fernandes dos Santos, Ignasi Sau
, Uéverton S. Souza
:
Reducing Graph Transversals via Edge Contractions. 64:1-64:15 - Alexander Lindermayr
, Sebastian Siebertz
, Alexandre Vigny
:
Elimination Distance to Bounded Degree on Planar Graphs. 65:1-65:12 - Sven Linker
, Fabio Papacchini
, Michele Sevegnani
:
Analysing Spatial Properties on Neighbourhood Spaces. 66:1-66:14 - Markus Lohrey
, Georg Zetzsche
:
Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups. 67:1-67:15 - Raul Lopes
, Ignasi Sau
:
A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. 68:1-68:15 - Vincent Michielini, Michal Skrzypczak
:
Regular Choice Functions and Uniformisations For countable Domains. 69:1-69:13 - Pranabendu Misra, Fahad Panolan
, Ashutosh Rai
, Saket Saurabh, Roohani Sharma:
Quick Separation in Chordal and Split Graphs. 70:1-70:14 - Nils Morawietz, Carolin Rehs
, Mathias Weller
:
A Timecop's Work Is Harder Than You Think. 71:1-71:14 - Janaky Murthy, Vineet Nair, Chandan Saha:
Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests. 72:1-72:16 - Satyadev Nandakumar, Prateek Vishnoi
:
Randomness and Effective Dimension of Continued Fractions. 73:1-73:13 - Daniel Neider
, Patrick Totzke
, Martin Zimmermann
:
Optimally Resilient Strategies in Pushdown Safety Games. 74:1-74:15 - Rian Neogi, M. S. Ramanujan, Saket Saurabh, Roohani Sharma:
On the Parameterized Complexity of Deletion to ℋ-Free Strong Components. 75:1-75:13 - Mitsunori Ogihara
, Kei Uchizawa:
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions. 76:1-76:13 - Louis Parlant, Jurriaan Rot, Alexandra Silva, Bas Westerbaan
:
Preservation of Equations by Monoidal Monads. 77:1-77:14 - Adam Paszke, Michal Pilipczuk:
VC Density of Set Systems Definable in Tree-Like Graphs. 78:1-78:13 - Jarkko Peltomäki
, Markus A. Whiteland
:
All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words. 79:1-79:10 - Alexander Rabinovich
, Doron Tiferet:
Ambiguity Hierarchy of Regular Infinite Tree Languages. 80:1-80:14 - Mikhail Rubinchik, Arseny M. Shur:
Palindromic k-Factorization in Pure Linear Time. 81:1-81:14 - Ignasi Sau
, Uéverton dos Santos Souza
:
Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. 82:1-82:15 - Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani
:
Classically Simulating Quantum Circuits with Local Depolarizing Noise. 83:1-83:13 - Kim Thang Nguyen
:
An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints. 84:1-84:12 - Caterina Viola
, Stanislav Zivný
:
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. 85:1-85:15
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.