default search action
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 für 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 - Hasan Abasi:
Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph. 3:1-3:15 - Alexander Kozachinskiy:
From Expanders to Hitting Distributions and Simulation Theorems. 4:1-4:15 - Titus Dose:
Balance Problems for Integer Circuits. 5:1-5:16 - Louis-Marie Dando, Sylvain Lombardy:
On Hadamard Series and Rotating Q-Automata. 6:1-6:14 - Egor Klenin, Alexander Kozachinskiy:
One-Sided Error Communication Complexity of Gap Hamming Distance. 7:1-7:15 - Spyros Angelopoulos, Christoph Dürr, Shendan Jin:
Online Maximum Matching with Recourse. 8:1-8:15 - Guillaume Burel:
Linking Focusing and Resolution with Selection. 9:1-9:14 - Andreas Krebs, Arne Meier
Team Semantics for the Specification and Verification of Hyperproperties. 10:1-10:16 - Florent R. Madelaine
Consistency for Counting Quantifiers. 11:1-11:13 - Naonori Kakimura, Naoyuki Kamiyama, Kenjiro Takazawa:
The b-Branching Problem in Digraphs. 12:1-12:15 - Dani Dorfman, Haim Kaplan, László Kozma
Pairing heaps: the forward variant. 13:1-13:14 - Yassine Hamoudi
Simultaneous Multiparty Communication Protocols for Composed Functions. 14:1-14:15 - Moses Ganardi, Artur Jez
Sliding Windows over Context-Free Languages. 15:1-15: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 O. Shallit:
Lagrange's Theorem for Binary Squares. 18:1-18:14 - Hendrik Fichtenberger
A Two-Sided Error Distributed Property Tester For Conductance. 19:1-19:15 - Martin Grohe, Gaurav Rattan
Graph Similarity and Approximate Isomorphism. 20:1-20:16 - Andrew Ryzhikov
Finding Short Synchronizing Words for Prefix Codes. 21:1-21:14 - Bill Fefferman, Shelby Kimmel:
Quantum vs. Classical Proofs and Subset Verification. 22:1-22:23 - Guy Avni
Timed Network Games with Clocks. 23:1-23:18 - Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg
Hardness Results for Consensus-Halving. 24:1-24:16 - Ioannis Lamprou, Russell Martin, Sven Schewe
Maximum Rooted Connected Expansion. 25:1-25:14 - François Le Gall, Tomoyuki Morimae, Harumichi Nishimura
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups. 26:1-26:13 - Martin Lück:
On the Complexity of Team Logic and Its Two-Variable Fragment. 27:1-27:22 - Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. 28:1-28:15 - Jakub Gajarský, Daniel Král
Recovering Sparse Graphs. 29:1-29:15 - Akitoshi Kawamura, Holger Thies
Average-Case Polynomial-Time Computability of Hamiltonian Dynamics. 30:1-30:17 - Francesco Cellinese, Gianlorenzo D'Angelo
Generalized Budgeted Submodular Set Function Maximization. 31:1-31:14 - Mikhail V. Berlinkov
Complexity of Preimage Problems for Deterministic Finite Automata. 32:1-32:14 - Manuel Bodirsky
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 - Dan Hefetz
Spanning-Tree Games. 35:1-35:16 - Thomas Erlebach, Jakob T. Spooner:
Faster Exploration of Degree-Bounded Temporal Graphs. 36:1-36:13 - 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
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 - Stéphane Le Roux:
Concurrent Games and Semi-Random Determinacy. 40:1-40:15 - Chen Dan, Kristoffer Arnsfelt Hansen
Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations. 41:1-41:16 - Arnaud Carayol, Matthew Hague
Optimal Strategies in Pushdown Reachability Games. 42:1-42:14 - Peter Jonsson, Victor Lagerkvist:
Why are CSPs Based on Partition Schemes Computationally Hard?. 43:1-43:15 - Argyrios Deligkas
Directed Graph Minors and Serial-Parallel Width. 44:1-44:14 - 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
The Complexity of Transducer Synthesis from Multi-Sequential Specifications. 46:1-46:16 - Vittorio Bilò
Pricing Problems with Buyer Preselection. 47:1-47:16 - Costanza Catalano
On Randomized Generation of Slowly Synchronizing Automata. 48:1-48:16 - Andreas Göbel, J. A. Gregor Lagodzinski
Counting Homomorphisms to Trees Modulo a Prime. 49:1-49:13 - Kelin Luo
Car-Sharing between Two Locations: Online Scheduling with Two Servers. 50:1-50:14 - Edith Hemaspaandra, Lane A. Hemaspaandra
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. 51:1-51:14 - Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna
Shape Recognition by a Finite Automaton Robot. 52:1-52:15 - Akanksha Agrawal
Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. 53:1-53:15 - Andre Droschinsky, Nils M. Kriege
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
Collective Fast Delivery by Energy-Efficient Agents. 56:1-56:16 - Matthew Hague
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 - Martin Dietzfelbinger
A Subquadratic Algorithm for 3XOR. 59:1-59:15 - Christian Doczkal, Damien Pous:
Treewidth-Two Graphs as a Free Algebra. 60:1-60:15 - Peter Dixon, Aduri Pavan, N. V. Vinodchandran:
On Pseudodeterministic Approximation Algorithms. 61:1-61:11 - Lukas Fleischer, Manfred Kufleitner:
Testing Simon's congruence. 62:1-62:13 - Konrad K. Dabrowski, Matthew Johnson
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
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
Fast Entropy-Bounded String Dictionary Look-Up with Mismatches. 66:1-66:15 - Rémy Belmonte, Tesshu Hanaka
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 - Jenish C. Mehta:
Tree Tribes and Lower Bounds for Switching Lemmas. 70:1-70:11 - Neil Lutz, Donald M. Stull:
Projection Theorems Using Effective Dimension. 71:1-71:15 - Andrzej S. Murawski, Steven J. Ramsay
Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata. 72:1-72:14 - Ralph Christian Bottesch:
On W[1]-Hardness as Evidence for Intractability. 73:1-73:15 - Christian Konrad:
A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms. 74:1-74:16 - Benjamin R. Moore, Naomi Nishimura, Vijay Subramanya:
Reconfiguration of Graph Minors. 75:1-75:15 - 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
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds. 78:1-78:15 - Donald M. Stull:
Results on the Dimension Spectra of Planar Lines. 79:1-79:15 - Aris Pagourtzis, Tomasz Radzik
Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks. 80:1-80:13 - Kazuyuki Amano:
Depth Two Majority Circuits for Majority and List Expanders. 81:1-81:13 - Mareike Dressler, Adam Kurpisz
Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials. 82:1-82:17 - Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima
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
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.
last updated on 2024-11-30 00:02 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: