Portal - MFCS 2016

MFCS 2016	August 22-26, 2016 - Kraków, Poland
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier (Eds.)
ISBN 978-3-95977-016-3, LIPICS Vol. 58	ISSN 1868-8969

Additional Information

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

Authors

Agrawal, Manindra

Akshay, S.

Amanatidis, Georgios

Amiri, Saeed Akhoondian

Bouyer-Decitre, Patricia

Bouyer, Patricia

Brunet, Paul

Chandoo, Maurice

Chatterjee, Krishnendu

Chatzidimitriou, Dimitris

Giannopoulou, Archontia C.

Kallampally, Vivek Anand T

Krishna, Shankara Narayanan

Krötzsch, Markus

Kudahl, Christian

Kuhnert, Sebastian

Kulikov, Alexander S.

Loitzenbauer, Veronika

Lokam, Satyanarayana V.

Lysikov, Vladimir

Makowsky, Johann A.

Mallmann-Trenn, Frederik

Meunier, Pierre-Etienne

Narayanan, Anand Kumar

Narayanaswamy, N. S.

Natale, Emanuele

Niedermeier, Rolf

Nikoletseas, Sotiris E.

Raptopoulos, Christoforos L.

Srivastava, Shubham Sahai

Thilikos, Dimitrios M.

van Heuven van Staereling, Irving

Vardi, Gal

Vargas Koch, Laura

Vassilevska Williams, Virginia

Front Matter, Foreword, Conference Organization, External Reviewers, Table of Contents

Authors: Faliszewski, Piotr ; Muscholl, Anca ; Niedermeier, Rolf

Abstract | Document (361 KB) | BibTeX

How Far Are We From Having a Satisfactory Theory of Clustering? (Invited Talk)

Authors: Ben-David, Shai

Abstract | Document (217 KB) | BibTeX

Decidable Extensions of MSO (Invited Talk)

Authors: Bojanczyk, Mikolaj

Abstract | Document (216 KB) | BibTeX

Optimal Reachability in Weighted Timed Automata and Games (Invited Talk)

Authors: Bouyer-Decitre, Patricia

Abstract | Document (309 KB) | BibTeX

Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms (Invited Talk)

Authors: Friedrich, Tobias

Abstract | Document (221 KB) | BibTeX

RNA-Folding - From Hardness to Algorithms (Invited Talk)

Authors: Vassilevska Williams, Virginia

Abstract | Document (209 KB) | BibTeX

Integer Factoring Using Small Algebraic Dependencies

Authors: Agrawal, Manindra ; Saxena, Nitin ; Srivastava, Shubham Sahai

Abstract | Document (521 KB) | BibTeX

Routing with Congestion in Acyclic Digraphs

Authors: Amiri, Saeed Akhoondian ; Kreutzer, Stephan ; Marx, Dániel ; Rabinovich, Roman

Abstract | Document (548 KB) | BibTeX

Stochastic Timed Games Revisited

Authors: Akshay, S. ; Bouyer, Patricia ; Krishna, Shankara Narayanan ; Manasa, Lakshmi ; Trivedi, Ashutosh

Abstract | Document (617 KB) | BibTeX

Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results

Authors: Amanatidis, Georgios ; Markakis, Evangelos ; Sornat, Krzysztof

Abstract | Document (582 KB) | BibTeX

Trading Determinism for Time in Space Bounded Computations

Authors: Kallampally, Vivek Anand T ; Tewari, Raghunath

Abstract | Document (461 KB) | BibTeX

Families of DFAs as Acceptors of omega-Regular Languages

Authors: Angluin, Dana ; Boker, Udi ; Fisman, Dana

Abstract | Document (540 KB) | BibTeX

On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems

Authors: Arad, Itai ; Bouland, Adam ; Grier, Daniel ; Santha, Miklos ; Sundaram, Aarthi ; Zhang, Shengyu

Abstract | Document (546 KB) | BibTeX

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

Authors: Arvind, Vikraman ; Fuhlbrück, Frank ; Köbler, Johannes ; Kuhnert, Sebastian ; Rattan, Gaurav

Abstract | Document (511 KB) | BibTeX

Real Interactive Proofs for VPSPACE

Authors: Baartse, Martijn ; Meer, Klaus

Abstract | Document (453 KB) | BibTeX

Synchronizing Data Words for Register Automata

Authors: Babari, Parvaneh ; Quaas, Karin ; Shirmohammadi, Mahsa

Abstract | Document (569 KB) | BibTeX

On the Sensitivity Conjecture for Read-k Formulas

Authors: Bafna, Mitali ; Lokam, Satyanarayana V. ; Tavenas, Sébastien ; Velingker, Ameya

Abstract | Document (467 KB) | BibTeX

Graph Properties in Node-Query Setting: Effect of Breaking Symmetry

Authors: Balaji, Nikhil ; Datta, Samir ; Kulkarni, Raghav ; Podder, Supartha

Abstract | Document (520 KB) | BibTeX

Stable States of Perturbed Markov Chains

Authors: Betz, Volker ; Le Roux, Stéphane

Abstract | Document (561 KB) | BibTeX

On Degeneration of Tensors and Algebras

Authors: Bläser, Markus ; Lysikov, Vladimir

Abstract | Document (454 KB) | BibTeX

Using Contracted Solution Graphs for Solving Reconfiguration Problems

Authors: Bonsma, Paul ; Paulusma, Daniël

Abstract | Document (636 KB) | BibTeX

Pointer Quantum PCPs and Multi-Prover Games

Authors: Grilo, Alex B. ; Kerenidis, Iordanis ; Pereszlényi, Attila

Abstract | Document (479 KB) | BibTeX

A Formal Exploration of Nominal Kleene Algebra

Authors: Brunet, Paul ; Pous, Damien

Abstract | Document (524 KB) | BibTeX

On the Implicit Graph Conjecture

Authors: Chandoo, Maurice

Abstract | Document (441 KB) | BibTeX

Nested Weighted Limit-Average Automata of Bounded Width

Authors: Chatterjee, Krishnendu ; Henzinger, Thomas A. ; Otop, Jan

Abstract | Document (551 KB) | BibTeX

Conditionally Optimal Algorithms for Generalized Büchi Games

Authors: Chatterjee, Krishnendu ; Dvorák, Wolfgang ; Henzinger, Monika ; Loitzenbauer, Veronika

Abstract | Document (618 KB) | BibTeX

FPT Algorithms for Plane Completion Problems

Authors: Chatzidimitriou, Dimitris ; Giannopoulou, Archontia C. ; Maniatis, Spyridon ; Requilé, Clément ; Thilikos, Dimitrios M. ; Zoros, Dimitris

Abstract | Document (623 KB) | BibTeX

Some Lower Bounds in Parameterized AC^0

Authors: Chen, Yijia ; Flum, Jörg

Abstract | Document (577 KB) | BibTeX

Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs

Authors: Datta, Samir ; Kulkarni, Raghav ; Mukherjee, Anish

Abstract | Document (473 KB) | BibTeX

Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions

Authors: Lee, Matias David ; de Vink, Erik P.

Abstract | Document (573 KB) | BibTeX

Ackermannian Integer Compression and the Word Problem for Hydra Groups

Authors: Dison, Will ; Einstein, Eduard ; Riley, Timothy R.

Abstract | Document (566 KB) | BibTeX

A Note on the Advice Complexity of Multipass Randomized Logspace

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

Abstract | Document (442 KB) | BibTeX

Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Authors: Dose, Titus

Abstract | Document (493 KB) | BibTeX

Faster Algorithms for the Maximum Common Subtree Isomorphism Problem

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

Abstract | Document (555 KB) | BibTeX

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

Authors: Eiben, Eduard ; Ganian, Robert ; Kwon, O-joung

Abstract | Document (525 KB) | BibTeX

Preprocessing Under Uncertainty: Matroid Intersection

Authors: Fafianie, Stefan ; Hols, Eva-Maria C. ; Kratsch, Stefan ; Quyen, Vuong Anh

Abstract | Document (490 KB) | BibTeX

Ride Sharing with a Vehicle of Unlimited Capacity

Authors: Fanelli, Angelo ; Gianluigi, Greco

Abstract | Document (1,331 KB) | BibTeX

On the General Chain Pair Simplification Problem

Authors: Fan, Chenglin ; Filtser, Omrit ; Katz, Matthew J. ; Zhu, Binhai

Abstract | Document (600 KB) | BibTeX

Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets

Authors: Fujishige, Yuta ; Tsujimaru, Yuki ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki

Abstract | Document (883 KB) | BibTeX

On Planar Valued CSPs

Authors: Fulla, Peter ; Zivny, Stanislav

Abstract | Document (510 KB) | BibTeX

Determining Sets of Quasiperiods of Infinite Words

Authors: Gamard, Guilhem ; Richomme, Gwenaël

Abstract | Document (427 KB) | BibTeX

On the Complexity Landscape of Connected f-Factor Problems

Authors: Ganian, Robert ; Narayanaswamy, N. S. ; Ordyniak, Sebastian ; Rahul, C. S. ; Ramanujan, M. S.

Abstract | Document (758 KB) | BibTeX

On Existential MSO and its Relation to ETH

Authors: Ganian, Robert ; de Haan, Ronald ; Kanj, Iyad ; Szeider, Stefan

Abstract | Document (504 KB) | BibTeX

Programming Biomolecules That Fold Greedily During Transcription

Authors: Geary, Cody ; Meunier, Pierre-Etienne ; Schabanel, Nicolas ; Seki, Shinnosuke

Abstract | Document (4,137 KB) | BibTeX

Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups

Authors: Godin, Thibault ; Klimann, Ines

Abstract | Document (587 KB) | BibTeX

Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework

Authors: Golovnev, Alexander ; Kulikov, Alexander S. ; Smal, Alexander V. ; Tamaki, Suguru

Abstract | Document (534 KB) | BibTeX

On the Limits of Gate Elimination

Authors: Golovnev, Alexander ; Hirsch, Edward A. ; Knop, Alexander ; Kulikov, Alexander S.

Abstract | Document (505 KB) | BibTeX

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields

Authors: Guo, Zeyu ; Narayanan, Anand Kumar ; Umans, Chris

Abstract | Document (553 KB) | BibTeX

On Synchronizing Colorings and the Eigenvectors of Digraphs

Authors: Gusev, Vladimir V. ; Pribavkina, Elena V.

Abstract | Document (549 KB) | BibTeX

Competitive Packet Routing with Priority Lists

Authors: Harks, Tobias ; Peis, Britta ; Schmand, Daniel ; Vargas Koch, Laura

Abstract | Document (488 KB) | BibTeX

The Ground-Set-Cost Budgeted Maximum Coverage Problem

Authors: van Heuven van Staereling, Irving ; de Keijzer, Bart ; Schäfer, Guido

Abstract | Document (492 KB) | BibTeX

Computational and Proof Complexity of Partial String Avoidability

Authors: Itsykson, Dmitry ; Okhotin, Alexander ; Oparin, Vsevolod

Abstract | Document (433 KB) | BibTeX

Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence

Authors: Jancar, Petr

Abstract | Document (437 KB) | BibTeX

Minimal Phylogenetic Supertrees and Local Consensus Trees

Authors: Jansson, Jesper ; Sung, Wing-Kin

Abstract | Document (589 KB) | BibTeX

Quantum Communication Complexity of Distributed Set Joins

Authors: Jeffery, Stacey ; Le Gall, François

Abstract | Document (446 KB) | BibTeX

On the Voting Time of the Deterministic Majority Process

Authors: Kaaser, Dominik ; Mallmann-Trenn, Frederik ; Natale, Emanuele

Abstract | Document (613 KB) | BibTeX

Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Authors: Kammer, Frank ; Kratsch, Dieter ; Laudahn, Moritz

Abstract | Document (406 KB) | BibTeX

Multi-Party Protocols, Information Complexity and Privacy

Authors: Kerenidis, Iordanis ; Rosén, Adi ; Urrutia, Florent

Abstract | Document (518 KB) | BibTeX

Dividing by Zero - How Bad Is It, Really?

Authors: Kihara, Takayuki ; Pauly, Arno

Abstract | Document (596 KB) | BibTeX

Advice Complexity of the Online Induced Subgraph Problem

Authors: Komm, Dennis ; Královic, Rastislav ; Královic, Richard ; Kudahl, Christian

Abstract | Document (487 KB) | BibTeX

Decidability of Predicate Logics with Team Semantics

Authors: Kontinen, Juha ; Kuusisto, Antti ; Virtema, Jonni

Abstract | Document (546 KB) | BibTeX

On the Complexity of Universality for Partially Ordered NFAs

Authors: Krötzsch, Markus ; Masopust, Tomás ; Thomazo, Michaël

Abstract | Document (565 KB) | BibTeX

Eulerian Paths with Regular Constraints

Authors: Kupferman, Orna ; Vardi, Gal

Abstract | Document (515 KB) | BibTeX

On the Exact Learnability of Graph Parameters: The Case of Partition Functions

Authors: Labai, Nadia ; Makowsky, Johann A.

Abstract | Document (575 KB) | BibTeX

A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT

Authors: Lagerkvist, Victor ; Roy, Biman

Abstract | Document (583 KB) | BibTeX

Uniformization Problems for Tree-Automatic Relations and Top-Down Tree Transducers

Authors: Löding, Christof ; Winter, Sarah

Abstract | Document (532 KB) | BibTeX

Two-Variable Logic over Countable Linear Orderings

Authors: Manuel, Amaldev ; Sreejith, A. V.

Abstract | Document (447 KB) | BibTeX

Piecewise Testable Languages and Nondeterministic Automata

Authors: Masopust, Tomás

Abstract | Document (507 KB) | BibTeX

Stably Computing Order Statistics with Arithmetic Population Protocols

Authors: Mertzios, George B. ; Nikoletseas, Sotiris E. ; Raptopoulos, Christoforos L. ; Spirakis, Paul G.

Abstract | Document (538 KB) | BibTeX

Shortest Unique Substring Queries on Run-Length Encoded Strings

Authors: Mieno, Takuya ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki

Abstract | Document (708 KB) | BibTeX

Shattered Sets and the Hilbert Function

Authors: Moran, Shay ; Rashtchian, Cyrus

Abstract | Document (870 KB) | BibTeX

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

Authors: Jansen, Bart M. P. ; Pieterse, Astrid

Abstract | Document (588 KB) | BibTeX

Fully Dynamic Data Structure for LCE Queries in Compressed Space

Authors: Nishimoto, Takaaki ; I, Tomohiro ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki

Abstract | Document (641 KB) | BibTeX

Undecidability of Two-dimensional Robot Games

Authors: Niskanen, Reino ; Potapov, Igor ; Reichert, Julien

Abstract | Document (546 KB) | BibTeX

Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits

Authors: Pandey, Anurag ; Saxena, Nitin ; Sinhababu, Amit

Abstract | Document (591 KB) | BibTeX

Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs

Authors: Kolay, Sudeshna ; Panolan, Fahad ; Raman, Venkatesh ; Saurabh, Saket

Abstract | Document (499 KB) | BibTeX

Supplementarity is Necessary for Quantum Diagram Reasoning

Authors: Perdrix, Simon ; Wang, Quanlong

Abstract | Document (548 KB) | BibTeX

The Covering Problem: A Unified Approach for Investigating the Expressive Power of Logics

Authors: Place, Thomas ; Zeitoun, Marc

Abstract | Document (539 KB) | BibTeX

On the Complexity of Branching Games with Regular Conditions

Authors: Przybylko, Marcin ; Skrzypczak, Michal

Abstract | Document (503 KB) | BibTeX

Symbolic Lookaheads for Bottom-up Parsing

Authors: Quaglia, Paola

Abstract | Document (493 KB) | BibTeX

Structural Control in Weighted Voting Games

Authors: Rey, Anja ; Rothe, Jörg

Abstract | Document (569 KB) | BibTeX

Every Binary Pattern of Length Greater Than 14 Is Abelian-2-Avoidable

Authors: Rosenfeld, Matthieu

Abstract | Document (422 KB) | BibTeX

Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

Authors: Sakai, Takayuki ; Seto, Kazuhisa ; Tamaki, Suguru ; Teruyama, Junichi

Abstract | Document (605 KB) | BibTeX

Transducer-Based Rewriting Games for Active XML

Authors: Schuster, Martin

Abstract | Document (487 KB) | BibTeX

Vector Reachability Problem in SL(2, Z)

Authors: Potapov, Igor ; Semukhin, Pavel

Abstract | Document (566 KB) | BibTeX

The Generalised Colouring Numbers on Classes of Bounded Expansion

Authors: Kreutzer, Stephan ; Pilipczuk, Michal ; Rabinovich, Roman ; Siebertz, Sebastian

Abstract | Document (488 KB) | BibTeX

Polynomial Space Randomness in Analysis

Authors: Huang, Xiang ; Stull, Donald M.

Abstract | Document (443 KB) | BibTeX

Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs

Authors: Takazawa, Kenjiro

Abstract | Document (573 KB) | BibTeX

Transformation Between Regular Expressions and omega-Automata

Authors: Löding, Christof ; Tollkötter, Andreas

Abstract | Document (499 KB) | BibTeX

An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two

Authors: Xiao, Mingyu ; Kou, Shaowei

Abstract | Document (586 KB) | BibTeX

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

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)