43rd MFCS 2018: Liverpool, UK
- Igor Potapov, Paul G. Spirakis, James Worrell:
43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK. LIPIcs 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2018, ISBN 978-3-95977-086-6 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xx
- Laurent Bulteau, Markus L. Schmid:
Consensus Strings with Small Maximum Distance and Small Distance Sum. 1:1-1:15 - Mikhail Andreev, Gleb Posobin, Alexander Shen:
Plain Stopping Time and Conditional Complexities Revisited. 2:1-2:12 - Egor Klenin, Alexander Kozachinskiy:
One-Sided Error Communication Complexity of Gap Hamming Distance. 7:1-7:15 - Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann:
Team Semantics for the Specification and Verification of Hyperproperties. 10:1-10:16 - Naonori Kakimura, Naoyuki Kamiyama, Kenjiro Takazawa:
The b-Branching Problem in Digraphs. 12:1-12:15 - Louisa Seelbach Benkner, Markus Lohrey:
Average Case Analysis of Leaf-Centric Binary Tree Sources. 16:1-16:15 - Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski:
Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras. 17:1-17:15 - P. Madhusudan, Dirk Nowotka, Aayush Rajasekaran, Jeffrey Shallit:
Lagrange's Theorem for Binary Squares. 18:1-18:14 - Hendrik Fichtenberger, Yadu Vasudev:
A Two-Sided Error Distributed Property Tester For Conductance. 19:1-19:15 - Martin Grohe, Gaurav Rattan, Gerhard J. Woeginger:
Graph Similarity and Approximate Isomorphism. 20:1-20:16 - Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang:
Hardness Results for Consensus-Halving. 24:1-24:16 - Ioannis Lamprou, Russell Martin, Sven Schewe, Ioannis Sigalas, Vassilis Zissimopoulos:
Maximum Rooted Connected Expansion. 25:1-25:14 - François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi:
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups. 26:1-26:13 - Andrea E. F. Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca:
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. 28:1-28:15 - Akitoshi Kawamura, Holger Thies, Martin Ziegler:
Average-Case Polynomial-Time Computability of Hamiltonian Dynamics. 30:1-30:17 - Francesco Cellinese, Gianlorenzo D'Angelo, Gianpiero Monaco, Yllka Velaj:
Generalized Budgeted Submodular Set Function Maximization. 31:1-31:14 - Mikhail V. Berlinkov, Robert Ferens, Marek Szykula:
Complexity of Preimage Problems for Deterministic Finite Automata. 32:1-32:14 - Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet:
The Complexity of Disjunctive Linear Diophantine Constraints. 33:1-33:16 - Ran Ben-Basat, Gil Einziger, Roy Friedman:
Give Me Some Slack: Efficient Network Measurements. 34:1-34:16 - Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, Subhash Suri:
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames. 37:1-37:15 - Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi:
On Efficiently Solvable Cases of Quantum k-SAT. 38:1-38:16 - Cedric Berenger, Peter Niebert, Kévin Perrot:
Balanced Connected Partitioning of Unweighted Grid Graphs. 39:1-39:18 - Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, Yuchen Zhou:
Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations. 41:1-41:16 - Peter Jonsson, Victor Lagerkvist:
Why are CSPs Based on Partition Schemes Computationally Hard?. 43:1-43:15 - Philipp Zschoche, Till Fluschnik, Hendrik Molter, Rolf Niedermeier:
The Complexity of Finding Small Separators in Temporal Graphs. 45:1-45:17 - Léo Exibard, Emmanuel Filiot, Ismaël Jecker:
The Complexity of Transducer Synthesis from Multi-Sequential Specifications. 46:1-46:16 - Vittorio Bilò, Michele Flammini, Gianpiero Monaco, Luca Moscardelli:
Pricing Problems with Buyer Preselection. 47:1-47:16 - Costanza Catalano, Raphaël M. Jungers:
On Randomized Generation of Slowly Synchronizing Automata. 48:1-48:16 - Andreas Göbel, J. A. Gregor Lagodzinski, Karen Seidel:
Counting Homomorphisms to Trees Modulo a Prime. 49:1-49:13 - Kelin Luo, Thomas Erlebach, Yinfeng Xu:
Car-Sharing between Two Locations: Online Scheduling with Two Servers. 50:1-50:14 - Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe:
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. 51:1-51:14 - Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler:
Shape Recognition by a Finite Automaton Robot. 52:1-52:15 - Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, Saket Saurabh:
Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. 53:1-53:15 - Andre Droschinsky, Nils M. Kriege, Petra Mutzel:
Largest Weight Common Subtree Embeddings with Distance Penalties. 54:1-54:15 - Mamadou Moustapha Kanté, Kaveh Khoshkhah, Mozhgan Pourmoradnasseri:
Enumerating Minimal Transversals of Hypergraphs without Small Holes. 55:1-55:15 - Andreas Bärtschi, Daniel Graf, Matús Mihalák:
Collective Fast Delivery by Energy-Efficient Agents. 56:1-56:16 - Matthew Hague, Roland Meyer, Sebastian Muskalla, Martin Zimmermann:
Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems. 57:1-57:15 - Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka:
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). 58:1-58:16 - Peter Dixon, Aduri Pavan, N. V. Vinodchandran:
On Pseudodeterministic Approximation Algorithms. 61:1-61:11 - Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev:
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. 63:1-63:15 - Paolo D'Arco, Roberto De Prisco, Alfredo De Santis, Angel L. Pérez del Pozo, Ugo Vaccaro:
Probabilistic Secret Sharing. 64:1-64:16 - Frank Kammer, Andrej Sajenko:
Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. 65:1-65:16 - Pawel Gawrychowski, Gad M. Landau, Tatiana A. Starikovskaya:
Fast Entropy-Bounded String Dictionary Look-Up with Mismatches. 66:1-66:15 - Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, Michael Lampis:
New Results on Directed Edge Dominating Set. 67:1-67:16 - Pavol Hell, Jing Huang, Ross M. McConnell, Arash Rafiey:
Interval-Like Graphs and Digraphs. 68:1-68:13 - Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, Zhisheng Xu:
Double Threshold Digraphs. 69:1-69:12 - Andrzej S. Murawski, Steven J. Ramsay, Nikos Tzevelekos:
Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata. 72:1-72:14 - Christian Konrad:
A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms. 74:1-74:16 - Manfred Droste, Erik Paul:
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. 76:1-76:15 - Hugo A. Akitaya, Matthew D. Jones, David Stalfa, Csaba D. Tóth:
Maximum Area Axis-Aligned Square Packings. 77:1-77:15 - Ninad Rajgopal, Rahul Santhanam, Srikanth Srinivasan:
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds. 78:1-78:15 - Aris Pagourtzis, Tomasz Radzik:
Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks. 80:1-80:13 - Mareike Dressler, Adam Kurpisz, Timo de Wolff:
Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials. 82:1-82:17 - Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, Erik Jan van Leeuwen:
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. 83:1-83:13 - Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Luca Versari:
Listing Subgraphs by Cartesian Decomposition. 84:1-84:16