The series of MFCS symposia, organized since 1972, has a long and well-established tradition (see history). The MFCS symposia encourage high-quality research in all branches of theoretical computer science. Their broad scope provides an opportunity to bring together researchers who do not usually meet at specialized conferences. Quality papers presenting original research on theoretical aspects of computer science are solicited.
Abstract: A properly encapsulated data structure can be revised for refactoring without affecting the behaviors of clients of the data structure. Encapsulation ensures that clients are "representation independent", that is, they are independent of particular choices of data structure representations. Modular reasoning about data structure revisions in heap-manipulating programs, however, is a challenge because encapsulation in the presence of shared mutable objects is difficult to ensure for a variety of reasons.
Pointer aliasing can break encapsulation and invalidate data structure invariants.
Representation independence (RI) is nontrivial to guarantee in a generic manner, without recourse to specialized disciplines such as ownership.
Mechanical verification of RI using theorem provers is nontrivial because it requires relational reasoning between two different data structure representations. Such reasoning lies outside the scope of most modern verification tools.
We address the challenge by reasoning in Region Logic (RL), a Hoare logic augmented with state dependent “modifies” specifications based on simple notations for object sets, termed "regions". RL uses ordinary first order logic assertions to support local reasoning and also the hiding of invariants on encapsulated state, in ways suited to verification using SMT solvers. By using relational assertions, the logic can reason about behavior-preservation of data structure refactorings even in settings where full functional pre/post specifications are absent. The key ingredient behind such reasoning is a new proof rule that embodies representation independence.
This work is in collaboration with David A. Naumann and Mohammad Nikouei (Stevens Institute of Technology).
Abstract: Given a set S of n strings, a minimal perfect hash function (MPHF) is a data structure that associates bijectively with each element of S a natural number smaller than n; it is monotone (MMPHF) [SODA2009] if it respects the lexicographic ordering. The function is allowed to return an arbitrary answer when evaluated on elements outside of S. In the spectrum of perfect hash functions, MMPHFs (Monotone Minimal Perfect Hash Functions) represent a compromise between arbitrary minimal perfect hashing (where any bijective map is allowed) and order-preserving minimal perfect hashing (where a specific bijection is to be represented). MMPHFs have a wide range of practical applications (dictionaries of search engines, list of URLs of web graphs, etc.) and are becoming an object of interest of many researchers.
In this talk, I will first introduce some basic algorithmic techniques to build (static) MPHFs (inspired by the classical work by Majewski, Wormald, Havas and Czech on sparse functions). Then, I will discuss the problem of building MMPHFs both from a theoretical and a practical viewpoint, offering a spectrum of solutions with different tradeoffs between construction complexity, required space and lookup time.
Abstract: Computing models that have a read-only input tape, may be equipped with further resources, and evolve in discrete time are considered from the viewpoint of logical reversibility. Since such abstract models may serve as prototypes of machines which can be physically constructed, and by the observation that loss of information results in heat dissipation, it is interesting to study computations without loss of information, that is, reversible computations. In essence, the reversibility of a deterministic computation means that every configuration has a unique successor configuration and a unique predecessor configuration.
The talk covers the notion of reversibility and its possible definitions. In which way is the predecessor configuration computed? Do we have to consider all possible configurations as potential predecessors? Or only configurations that are reachable from some initial configurations? We present some selected aspects as gradual reversibility, time-symmetry, and decidability as well as results on the computational and descriptional capacity of several logical reversible devices.
Abstract: Robust inference is an extension of probabilistic inference, where some of the observations may be adversarially corrupted. We limit the adversarial corruption to a finite set of modification rules. We model robust inference as a zero-sum game between an adversary, who selects a modification rule, and a predictor, who wants to accurately predict the state of nature.
There are two variants of the model, one where the adversary needs to pick the modification rule in advance and one where the adversary can select the modification rule after observing the realized uncorrupted input. For both settings we derive efficient near optimal policy runs in polynomial time. Our efficient algorithms are based on methodologies for developing local computation algorithms.
We also consider a learning setting where the predictor receives a set of uncorrupted inputs and their classification. The predictor needs to select a hypothesis, from a known set of hypotheses, and is tested on inputs which the adversary corrupts. We show how to utilize an ERM oracle to derive a near optimal predictor strategy, namely, picking a hypothesis that minimizes the error on the corrupted test inputs.
Based on joint works with Uriel Feige, Aviad Rubinstein, Robert Schapira, Moshe Tennenholtz, and Shai Vardi.
Abstract: Most fixed point models commonly used in computer science share the same equational properties. We provide several complete axiomatic descriptions of these properties using equations or quasi-equations.
Some of the fixed point models have an additional structure such as an additive structure. We show that it is often possible to describe the interaction between the basic fixed point structure and the additional structure by a finite number of equations.
Hee-Kap Ahn - POSTECH, Korea
Andris Ambainis - University of Latvia, Latvia
Marie-Pierre Béal - Université Paris-Est Marne-la-Vallée, France
Lars Birkedal - Aarhus University, Denmark
Jarek Byrka - University of Wrocław, Poland
Luis Caires - Universidade Nova de Lisboa, Portugal
Bruno Codenotti - CNR Pisa, Italy
Adriana Compagnoni - Stevens Institute of Technology, United States
Erzsébet Csuhaj-Varjú - Eötvös Loránd University, Budpest, Hungary
Artur Czumaj - University of Warwick, United Kingdom
Rocco de Nicola - IMT Lucca, Italy
Martin Dietzfelbinger - Technische Universität Ilmenau, Germany
Devdatt Dubashi - Chalmers, Sweden
Amos Fiat - Tel-Aviv University, Israel
Enrico Formenti - Université de Nice-Sophia Antipolis, France
Pierre Fraigniaud - CNRS and University Paris Diderot, France
Matt Franklin - UC Davis, United States
Loukas Georgiadis - University of Ioannina, Greece
Jan Holub - Czech Technical University, Prague, Czech Republic
Markus Holzer - Giessen Universitat, Germany
Giuseppe F. Italiano - Università di Roma “Tor Vergata”, Italy — co-chair
Martin Lange - Universität Kassel, Germany
Massimo Lauria - KTH Royal Institute of Technology, Sweden
Inge Li Gørtz - Technical University of Denmark, Denmark
Alberto Marchetti-Spaccamela - Università di Roma “Sapienza”, Italy
Elvira Mayordomo - Universidad de Zaragoza, Spain
Pierre McKenzie - Université de Montréal, Canada
Friedhelm Meyer auf der Heide - University of Paderborn, Germany
Prakash Panangaden - McGill University, Canada
Dana Pardubska - Comenius University, Bratislava, Slovakia
Kunsoo Park - Seoul National University, Korea
Giovanni Pighizzini - Università degli Studi di Milano, Italy — chair
Alexander Rabinovich - Tel Aviv University, Israel
Rajeev Raman - University of Leicester, United Kingdom
Jean-Francois Raskin - Université Libre de Bruxelles, Belgium
Liam Roditty - Bar-Ilan University, Israel
Marie-France Sagot - Université Claude Bernard, France
Piotr Sankowski - University of Warsaw, Poland
Don Sannella - University of Edinburgh, United Kingdom — co-chair
Philippe Schnoebelen - LSV, CNRS & ENS de Cachan, France
Marinella Sciortino - Università degli Studi di Palermo, Italy
Jiří Sgall - Charles University, Czech Republic
Arseny Shur - Ural Federal University, Russia
Mariya I. Soskova - Sofia University, Bulgaria
Tarmo Uustalu - Tallinn University of Technology, Estonia
Peter van Emde Boas - University of Amsterdam, The Netherlands
Jan van Leeuwen - Universiteit Utrecht, The Netherlands
Dorothea Wagner - Karlsruhe Institute of Technology, Germany
Peter Widmayer - ETH Zurich, Switzerland
Jiri Wiedermann - Academy of Sciences, Czech Republic
Christos Zaroliagis - University of Patras, Greece
Submissions to MFCS must not exceed 12 pages (in Springer-Verlag's Lecture Notes style and including bibliography). If the authors believe that more details are essential to substantiate the main claims, they may include a clearly marked appendix that will be read at the discretion of the program committee. Simultaneous submissions of papers to any other conference with published proceedings or submitting previously published papers is not allowed. The proceedings will be published in the ARCoSS subline of Lecture Notes in Computer Science by Springer-Verlag. Only electronic submissions in the PDF format are accepted. Submissions will be by the EasyChair conference system. Authors wishing to present a paper are invited to submit a pdf file via EasyChair using the following link: http://www.easychair.org/conferences/?conf=mfcs2015 The submitted article should be in English. Please use the LNCS LaTeX style.
By submitting a paper the authors acknowledge that in case of acceptance at least one of the authors will attend the conference and present the paper.
The European Association for Theoretical Computer Science (EATCS) sponsors a Best Paper and a Best Student Paper award at MFCS 2015. A paper is eligible for the best student paper award if all of its authors are full-time students at the time of submission. This must be indicated in the submission process.
Abstract: The Černý conjecture states that every n-state synchronizing automaton has a reset word of length at most (n-1)2. We study the hardness of finding short reset words. It is known that the exact version of the problem, i.e., finding the shortest reset word, is NP-hard and coNP-hard, and complete for the DP class, and that approximating the length of the shortest reset word within a factor of O(log n) is NP-hard [Gerbush and Heeringa, CIAA’10], even for the binary alphabet [Berlinkov, DLT’13]. We significantly improve on these results by showing that, for every ε>0, it is NP-hard to approximate the length of the shortest reset word within a factor of n1-ε. This is essentially tight since a simple O(n)-approximation algorithm exists.
Best Student Paper
Meirav Zehavi, Department of Computer Science, Technion, Israel Institute of Technology,
Abstract: The parameterized complexity of problems is often studied with respect to the size of their optimal solutions. However, for a maximization problem, the size of the optimal solution can be very large, rendering algorithms parameterized by it inefficient. Therefore, we suggest to study the parameterized complexity of maximization problems with respect to the size of the optimal solutions to their minimization versions. We examine this suggestion by considering the Maximum Minimal Vertex Cover (MMVC) problem, whose minimization version, Vertex Cover, is one of the most studied problems in the field of Parameterized Complexity. Our main contribution is a parameterized approximation algorithm for MMVC, including its weighted variant. We also give conditional lower bounds for the running times of algorithms for MMVC and its weighted variant.
MFCS 2015 Accepted Papers
Pascal Koiran, Sébastien Tavenas and Ignacio Garcia-Marco. Log-concavity and lower bounds for arithmetic circuits
The regular and the student fee include: conference material, electronic access to LNCS proceedings during the conference, 3 lunches, coffee breaks, social events, the use of conference facilities, one year EATCS membership (two years for students).
The regular and the student fee for EATCS members include: conference material, electronic access to LNCS proceedings during the conference, 3 lunches, coffee breaks, social events, the use of conference facilities.
Accompanying person fee covers the social events (welcome party, tour, social dinner).
The Italian Chapter of the EATCS offers a free 1-year membership to the Chapter to regular and student participants (from italian institutions) who have never been members of the Chapter.
EATCS members get a 30 EUR discount (select the EATCS member option) and are required to provide their EATCS ID. The participants who wish to extend their EATCS membership should not select the EATCS member option (does not get the discount) but should still provide their EATCS ID.
Students get a 40 EUR discount (select student as registration type) and are required to provide a student proof document. Failing to provide appropriate ID or ID proof for the concerned lower registration fees (discount) might result in cancellation of the registration without refund.
Accommodation is not included in the fee.
For any question about the registration process, please contact the organizing secretariat .