Portal - MFCS 2018

MFCS 2018	August 27-31, 2018 - Liverpool, GB
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) Igor Potapov and Paul Spirakis and James Worrell (Eds.)
ISBN 978-3-95977-086-6, LIPICS Vol. 117	ISSN 1868-8969

Additional Information

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

Authors

Berlinkov, Mikhail V.

Bilò, Vittorio

Bodirsky, Manuel

Bottesch, Ralph Christian

D'Angelo, Gianlorenzo

Dietzfelbinger, Martin

Fichtenberger, Hendrik

Frederiksen, Søren Kristoffer Stiil

Hansen, Kristoffer Arnsfelt

Hemaspaandra, Lane A.

Katsikarelis, Ioannis

Kozachinskiy, Alexander

Lagodzinski, J. A. Gregor

Madelaine, Florent R.

Pérez del Pozo, Angel

Pourmoradnasseri, Mozhgan

Scheideler, Christian

Seelbach Benkner, Louisa

Starikovskaya, Tatiana

van Leeuwen, Erik Jan

Woeginger, Gerhard J.

Zissimopoulos, Vassilis

Zschoche, Philipp

Zwick, Uri

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Potapov, Igor ; Spirakis, Paul ; Worrell, James

Abstract | Document (423 KB) | BibTeX

Consensus Strings with Small Maximum Distance and Small Distance Sum

Authors: Bulteau, Laurent ; Schmid, Markus L.

Abstract | Document (634 KB) | BibTeX

Plain Stopping Time and Conditional Complexities Revisited

Authors: Andreev, Mikhail ; Posobin, Gleb ; Shen, Alexander

Abstract | Document (407 KB) | BibTeX

Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph

Authors: Abasi, Hasan

Abstract | Document (517 KB) | BibTeX

From Expanders to Hitting Distributions and Simulation Theorems

Authors: Kozachinskiy, Alexander

Abstract | Document (430 KB) | BibTeX

Balance Problems for Integer Circuits

Authors: Dose, Titus

Abstract | Document (454 KB) | BibTeX

On Hadamard Series and Rotating Q-Automata

Authors: Dando, Louis-Marie ; Lombardy, Sylvain

Abstract | Document (465 KB) | BibTeX

One-Sided Error Communication Complexity of Gap Hamming Distance

Authors: Klenin, Egor ; Kozachinskiy, Alexander

Abstract | Document (410 KB) | BibTeX

Online Maximum Matching with Recourse

Authors: Angelopoulos, Spyros ; Dürr, Christoph ; Jin, Shendan

Abstract | Document (464 KB) | BibTeX

Linking Focusing and Resolution with Selection

Authors: Burel, Guillaume

Abstract | Document (435 KB) | BibTeX

Team Semantics for the Specification and Verification of Hyperproperties

Authors: Krebs, Andreas ; Meier, Arne ; Virtema, Jonni ; Zimmermann, Martin

Abstract | Document (477 KB) | BibTeX

Consistency for Counting Quantifiers

Authors: Madelaine, Florent R. ; Martin, Barnaby

Abstract | Document (454 KB) | BibTeX

The b-Branching Problem in Digraphs

Authors: Kakimura, Naonori ; Kamiyama, Naoyuki ; Takazawa, Kenjiro

Abstract | Document (485 KB) | BibTeX

Pairing heaps: the forward variant

Authors: Dorfman, Dani ; Kaplan, Haim ; Kozma, László ; Zwick, Uri

Abstract | Document (553 KB) | BibTeX

Simultaneous Multiparty Communication Protocols for Composed Functions

Authors: Hamoudi, Yassine

Abstract | Document (557 KB) | BibTeX

Sliding Windows over Context-Free Languages

Authors: Ganardi, Moses ; Jez, Artur ; Lohrey, Markus

Abstract | Document (411 KB) | BibTeX

Average Case Analysis of Leaf-Centric Binary Tree Sources

Authors: Seelbach Benkner, Louisa ; Lohrey, Markus

Abstract | Document (473 KB) | BibTeX

Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras

Authors: Idziak, Pawel M. ; Kawalek, Piotr ; Krzaczkowski, Jacek

Abstract | Document (492 KB) | BibTeX

Lagrange's Theorem for Binary Squares

Authors: Madhusudan, P. ; Nowotka, Dirk ; Rajasekaran, Aayush ; Shallit, Jeffrey

Abstract | Document (448 KB) | BibTeX

A Two-Sided Error Distributed Property Tester For Conductance

Authors: Fichtenberger, Hendrik ; Vasudev, Yadu

Abstract | Document (488 KB) | BibTeX

Graph Similarity and Approximate Isomorphism

Authors: Grohe, Martin ; Rattan, Gaurav ; Woeginger, Gerhard J.

Abstract | Document (479 KB) | BibTeX

Finding Short Synchronizing Words for Prefix Codes

Authors: Ryzhikov, Andrew ; Szykula, Marek

Abstract | Document (451 KB) | BibTeX

Quantum vs. Classical Proofs and Subset Verification

Authors: Fefferman, Bill ; Kimmel, Shelby

Abstract | Document (628 KB) | BibTeX

Timed Network Games with Clocks

Authors: Avni, Guy ; Guha, Shibashis ; Kupferman, Orna

Abstract | Document (530 KB) | BibTeX

Hardness Results for Consensus-Halving

Authors: Filos-Ratsikas, Aris ; Frederiksen, Søren Kristoffer Stiil ; Goldberg, Paul W. ; Zhang, Jie

Abstract | Document (572 KB) | BibTeX

Maximum Rooted Connected Expansion

Authors: Lamprou, Ioannis ; Martin, Russell ; Schewe, Sven ; Sigalas, Ioannis ; Zissimopoulos, Vassilis

Abstract | Document (481 KB) | BibTeX

Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups

Authors: Le Gall, François ; Morimae, Tomoyuki ; Nishimura, Harumichi ; Takeuchi, Yuki

Abstract | Document (465 KB) | BibTeX

On the Complexity of Team Logic and Its Two-Variable Fragment

Authors: Lück, Martin

Abstract | Document (626 KB) | BibTeX

A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors

Authors: Clementi, Andrea ; Ghaffari, Mohsen ; Gualà, Luciano ; Natale, Emanuele ; Pasquale, Francesco ; Scornavacca, Giacomo

Abstract | Document (628 KB) | BibTeX

Recovering Sparse Graphs

Authors: Gajarský, Jakub ; Král', Daniel

Abstract | Document (462 KB) | BibTeX

Average-Case Polynomial-Time Computability of Hamiltonian Dynamics

Authors: Kawamura, Akitoshi ; Thies, Holger ; Ziegler, Martin

Abstract | Document (488 KB) | BibTeX

Generalized Budgeted Submodular Set Function Maximization

Authors: Cellinese, Francesco ; D'Angelo, Gianlorenzo ; Monaco, Gianpiero ; Velaj, Yllka

Abstract | Document (471 KB) | BibTeX

Complexity of Preimage Problems for Deterministic Finite Automata

Authors: Berlinkov, Mikhail V. ; Ferens, Robert ; Szykula, Marek

Abstract | Document (462 KB) | BibTeX

The Complexity of Disjunctive Linear Diophantine Constraints

Authors: Bodirsky, Manuel ; Martin, Barnaby ; Mamino, Marcello ; Mottet, Antoine

Abstract | Document (488 KB) | BibTeX

Give Me Some Slack: Efficient Network Measurements

Authors: Ben Basat, Ran ; Einziger, Gil ; Friedman, Roy

Abstract | Document (651 KB) | BibTeX

Spanning-Tree Games

Authors: Hefetz, Dan ; Kupferman, Orna ; Lellouche, Amir ; Vardi, Gal

Abstract | Document (721 KB) | BibTeX

Faster Exploration of Degree-Bounded Temporal Graphs

Authors: Erlebach, Thomas ; Spooner, Jakob T.

Abstract | Document (449 KB) | BibTeX

Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

Authors: Bandyapadhyay, Sayan ; Maheshwari, Anil ; Mehrabi, Saeed ; Suri, Subhash

Abstract | Document (742 KB) | BibTeX

On Efficiently Solvable Cases of Quantum k-SAT

Authors: Aldi, Marco ; de Beaudrap, Niel ; Gharibian, Sevag ; Saeedi, Seyran

Abstract | Document (556 KB) | BibTeX

Balanced Connected Partitioning of Unweighted Grid Graphs

Authors: Berenger, Cedric ; Niebert, Peter ; Perrot, Kevin

Abstract | Document (1,051 KB) | BibTeX

Concurrent Games and Semi-Random Determinacy

Authors: Le Roux, Stéphane

Abstract | Document (443 KB) | BibTeX

Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations

Authors: Dan, Chen ; Hansen, Kristoffer Arnsfelt ; Jiang, He ; Wang, Liwei ; Zhou, Yuchen

Abstract | Document (611 KB) | BibTeX

Optimal Strategies in Pushdown Reachability Games

Authors: Carayol, Arnaud ; Hague, Matthew

Abstract | Document (456 KB) | BibTeX

Why are CSPs Based on Partition Schemes Computationally Hard?

Authors: Jonsson, Peter ; Lagerkvist, Victor

Abstract | Document (493 KB) | BibTeX

Directed Graph Minors and Serial-Parallel Width

Authors: Deligkas, Argyrios ; Meir, Reshef

Abstract | Document (536 KB) | BibTeX

The Complexity of Finding Small Separators in Temporal Graphs

Authors: Zschoche, Philipp ; Fluschnik, Till ; Molter, Hendrik ; Niedermeier, Rolf

Abstract | Document (691 KB) | BibTeX

The Complexity of Transducer Synthesis from Multi-Sequential Specifications

Authors: Exibard, Léo ; Filiot, Emmanuel ; Jecker, Ismaël

Abstract | Document (534 KB) | BibTeX

Pricing Problems with Buyer Preselection

Authors: Bilò, Vittorio ; Flammini, Michele ; Monaco, Gianpiero ; Moscardelli, Luca

Abstract | Document (506 KB) | BibTeX

On Randomized Generation of Slowly Synchronizing Automata

Authors: Catalano, Costanza ; Jungers, Raphaël M.

Abstract | Document (616 KB) | BibTeX

Counting Homomorphisms to Trees Modulo a Prime

Authors: Göbel, Andreas ; Lagodzinski, J. A. Gregor ; Seidel, Karen

Abstract | Document (573 KB) | BibTeX

Car-Sharing between Two Locations: Online Scheduling with Two Servers

Authors: Luo, Kelin ; Erlebach, Thomas ; Xu, Yinfeng

Abstract | Document (473 KB) | BibTeX

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction

Authors: Hemaspaandra, Edith ; Hemaspaandra, Lane A. ; Spakowski, Holger ; Watanabe, Osamu

Abstract | Document (419 KB) | BibTeX

Shape Recognition by a Finite Automaton Robot

Authors: Gmyr, Robert ; Hinnenthal, Kristian ; Kostitsyna, Irina ; Kuhn, Fabian ; Rudolph, Dorian ; Scheideler, Christian

Abstract | Document (446 KB) | BibTeX

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy

Authors: Agrawal, Akanksha ; Jain, Pallavi ; Kanesh, Lawqueen ; Lokshtanov, Daniel ; Saurabh, Saket

Abstract | Document (615 KB) | BibTeX

Largest Weight Common Subtree Embeddings with Distance Penalties

Authors: Droschinsky, Andre ; Kriege, Nils M. ; Mutzel, Petra

Abstract | Document (503 KB) | BibTeX

Enumerating Minimal Transversals of Hypergraphs without Small Holes

Authors: Kanté, Mamadou M. ; Khoshkhah, Kaveh ; Pourmoradnasseri, Mozhgan

Abstract | Document (572 KB) | BibTeX

Collective Fast Delivery by Energy-Efficient Agents

Authors: Bärtschi, Andreas ; Graf, Daniel ; Mihalák, Matús

Abstract | Document (835 KB) | BibTeX

Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems

Authors: Hague, Matthew ; Meyer, Roland ; Muskalla, Sebastian ; Zimmermann, Martin

Abstract | Document (466 KB) | BibTeX

Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)

Authors: Gharibian, Sevag ; Santha, Miklos ; Sikora, Jamie ; Sundaram, Aarthi ; Yirka, Justin

Abstract | Document (582 KB) | BibTeX

A Subquadratic Algorithm for 3XOR

Authors: Dietzfelbinger, Martin ; Schlag, Philipp ; Walzer, Stefan

Abstract | Document (577 KB) | BibTeX

Treewidth-Two Graphs as a Free Algebra

Authors: Doczkal, Christian ; Pous, Damien

Abstract | Document (448 KB) | BibTeX

On Pseudodeterministic Approximation Algorithms

Authors: Dixon, Peter ; Pavan, A. ; Vinodchandran, N. V.

Abstract | Document (425 KB) | BibTeX

Testing Simon's congruence

Authors: Fleischer, Lukas ; Kufleitner, Manfred

Abstract | Document (423 KB) | BibTeX

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Authors: Dabrowski, Konrad K. ; Johnson, Matthew ; Paesani, Giacomo ; Paulusma, Daniël ; Zamaraev, Viktor

Abstract | Document (441 KB) | BibTeX

Probabilistic Secret Sharing

Authors: D'Arco, Paolo ; De Prisco, Roberto ; De Santis, Alfredo ; Pérez del Pozo, Angel ; Vaccaro, Ugo

Abstract | Document (502 KB) | BibTeX

Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays

Authors: Kammer, Frank ; Sajenko, Andrej

Abstract | Document (477 KB) | BibTeX

Fast Entropy-Bounded String Dictionary Look-Up with Mismatches

Authors: Gawrychowski, Pawel ; Landau, Gad M. ; Starikovskaya, Tatiana

Abstract | Document (395 KB) | BibTeX

New Results on Directed Edge Dominating Set

Authors: Belmonte, Rémy ; Hanaka, Tesshu ; Katsikarelis, Ioannis ; Kim, Eun Jung ; Lampis, Michael

Abstract | Document (561 KB) | BibTeX

Interval-Like Graphs and Digraphs

Authors: Hell, Pavol ; Huang, Jing ; McConnell, Ross M. ; Rafiey, Arash

Abstract | Document (395 KB) | BibTeX

Double Threshold Digraphs

Authors: Hamburger, Peter ; McConnell, Ross M. ; Pór, Attila ; Spinrad, Jeremy P. ; Xu, Zhisheng

Abstract | Document (460 KB) | BibTeX

Tree Tribes and Lower Bounds for Switching Lemmas

Authors: Mehta, Jenish C.

Abstract | Document (436 KB) | BibTeX

Projection Theorems Using Effective Dimension

Authors: Lutz, Neil ; Stull, Donald M.

Abstract | Document (407 KB) | BibTeX

Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata

Authors: Murawski, Andrzej S. ; Ramsay, Steven J. ; Tzevelekos, Nikos

Abstract | Document (564 KB) | BibTeX

On W[1]-Hardness as Evidence for Intractability

Authors: Bottesch, Ralph Christian

Abstract | Document (499 KB) | BibTeX

A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms

Authors: Konrad, Christian

Abstract | Document (492 KB) | BibTeX

Reconfiguration of Graph Minors

Authors: Moore, Benjamin ; Nishimura, Naomi ; Subramanya, Vijay

Abstract | Document (382 KB) | BibTeX

A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic

Authors: Droste, Manfred ; Paul, Erik

Abstract | Document (464 KB) | BibTeX

Maximum Area Axis-Aligned Square Packings

Authors: Akitaya, Hugo A. ; Jones, Matthew D. ; Stalfa, David ; Tóth, Csaba D.

Abstract | Document (852 KB) | BibTeX

Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds

Authors: Rajgopal, Ninad ; Santhanam, Rahul ; Srinivasan, Srikanth

Abstract | Document (580 KB) | BibTeX

Results on the Dimension Spectra of Planar Lines

Authors: Stull, Donald M.

Abstract | Document (412 KB) | BibTeX

Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks

Authors: Pagourtzis, Aris ; Radzik, Tomasz

Abstract | Document (450 KB) | BibTeX

Depth Two Majority Circuits for Majority and List Expanders

Authors: Amano, Kazuyuki

Abstract | Document (533 KB) | BibTeX

Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials

Authors: Dressler, Mareike ; Kurpisz, Adam ; de Wolff, Timo

Abstract | Document (606 KB) | BibTeX

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Authors: Heggernes, Pinar ; Issac, Davis ; Lauri, Juho ; Lima, Paloma T. ; van Leeuwen, Erik Jan

Abstract | Document (495 KB) | BibTeX

Listing Subgraphs by Cartesian Decomposition

Authors: Conte, Alessio ; Grossi, Roberto ; Marino, Andrea ; Rizzi, Romeo ; Versari, Luca

Abstract | Document (514 KB) | BibTeX

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

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)