Mathematical Foundations of Computer Science 2015
August 24-28 2015 – Milano (Italy)

ProgramMonday 24
Room A

Room B
Opening
Invited Talk: Yishay Mansour
Robust Inference and Local algorithms
Coffee Break
11:00
11:30 Arvind, Köbler, Rattan, Verbitsky
Hannula, Kontinen, Virtema, Vollmer
On Tinhofer's Linear Programming Approach toComplexity of Propositional Independence andIsomorphism Testing
Inclusion Logic
11:55 Hartinger, Johnson, Milanič, Paulusma
Pauly
The Price of Connectivity for Cycle Transversals Computability on the countable ordinals and theHausdorff-Kuratowski theorem
12:20 Braverman, Liu, Singh, Vinodchandran, Yang
Hella, Kuusisto, Meier, Vollmer
New Bounds for the CLIQUE-GAP Problem using Modal Inclusion Logic: Being Lax is Simpler thanGraph Decomposition Theory
Being Strict

9.45
10:00

Lunch
12:45
14:10 van Ee, Sitters
Perrot, Remila
On the complexity of master problems
Emergence on decreasing sandpile models
14:35 Kosolobov
Durand, Romashchenko
Faster lightweight Lempel-Ziv parsing
Quasiperiodicity and non-computability in tilings
15:00 Fournier, Limaye, Mahajan, Srinivasan
Hoffmann, Kleist, Miltzow
The shifted partial derivative complexity ofUpper and Lower Bounds on Long Dual Paths in
Elementary Symmetric Polynomials
Line Arrangements
15:25 Hagerup
SchmidEasy Multiple-Precision Divisors and Word-RAM Finding Consensus Strings With Small LengthConstants
Difference Between Input and Solution Strings
Coffe break
15:50
16:20 Mauro, Zavattaro
Ferraioli, Ventre
On the Complexity of Reconfiguration in Systems Metastability of Asymptotically Well-Behaved
with Legacy Components
Potential Games
16:45 Barcelo, Nugent, Pruhs, Scquizzato
Abed, Caragiannis, Voudouris
Almost All Functions Require Exponential Energy Near-optimal asymmetric binary matrix partitions
17:10 Arvind, Rattan, Joglekar
JakobsenOn the Complexity of Noncommutative Polynomial A numbers-on-foreheads game
Factorization
17:35 Barcelo, Kling, Nugent, Pruhs, Scquizzato
Cord-Landwehr, Lenzner
On the Complexity of Speed Scaling
Network Creation Games: Think Global - Act Local
18:00

Welcome Party

Mathematical Foundations of Computer Science 2015
August 24-28 2015 – Milano (Italy)

Program
Tuesday 25
Room A

Room B
Invited
Talk:
AnindyaBanerjee
9:00
Modular Reasoning for Behavior-Preserving Data Structure Refactorings
Coffee Break
10:00
10:30 Fafianie, KratschDumitran, Manea
A shortcut to (sun)flowers: Kernels in logarithmic Longest Gapped Repeats and Palindromes
space or linear time
10:55 Rahn, Schäfer
Berthé, Cesaratto, Rotondo, Vallée, Viola
Efficient Equilibria in Polymatrix Coordination
Recurrence function on Sturmian words: aGames
probabilistic study
11:20 Gajarský, Lampis, Makino, Mitsou, Ordyniak
Regnault, Remila
Parameterized Algorithms for Parity Games
Lost in Self-Stabilization
11:45 Etscheid, Kratsch, Mnich, Röglin
Abbes, Mairesse
Polynomial Kernels for Weighted Problems
Uniform generation in trace monoids
Lunch
12:20
13:30 Brandstädt, Dabrowski, Huang, Paulusma
Crépeau, Kazmi
Bounding the Clique-Width of H-free Chordal
Oblivious Transfer from weakly Random SelfGraphs
Reducible Public-Key Cryptosystem
13:55 Belmonte, Fomin, Golovach, Ramanujan
Di Crescenzo, Coan, Kirsch
Metric Dimension of Bounded Width Graphs
Efficient Computations over Encrypted Data
Blocks
14:20 McGregor, Tench, Vorotnikova, Vu
Schnoor, Woizekowski
Densest Subgraph in Dynamic Graph Streams
Active Linking Attacks
Coffe break
14:45
15:10 Chen, Megow, Rischke, Stougie, Verschae
Berlinkov, Szykuła
Optimal Algorithms and a PTAS for Cost-Aware
Algebraic Synchronization Criterion andScheduling
Computing Reset Words
15:35 Mneimneh, Farhat
Kisielewicz, Szykuła
The Offline Carpool Problem Revisited
Synchronizing Automata with Extremal Properties
16:00 Baartse, MeerAn algebraic proof of the real number PCP
theoremCadilhac, Krebs, Ludwig, Paperman
A Circuit Complexity Approach to Transductions

Mini break
16:25
16:35 Chen
Chumbalov, Romashchenko
Satisfiability Algorithms and Lower Bounds forRandomized Polynomial Time Protocol for
Boolean Formulas over Finite Bases
Combinatorial Slepian-Wolf Problem
17:00 Bulatov, Skvortsov
Case, Lutz
Phase transition for Local Search on planted SAT Mutual Dimension and Random Sequences
17:20 Lagerkvist
Precise Upper and Lower Bounds for theMonotone Constraint Satisfaction Problem

Mathematical Foundations of Computer Science 2015
August 24-28 2015 – Milano (Italy)

ProgramWednesday 26
Room AAnniversary
Talk: Zoltan Esik
9:00
Equational properties of fixed point operations in cartesian categories. An overview
Coffee Break
10:30
Presentation of the Best Paper Awards
11:00
Gawrychowski, Straszak
Strong inapproximability of the shortest reset word
11:30 Zehavi
Maximum Minimal Vertex Cover Parameterized by Vertex CoverSocial Activities

Mathematical Foundations of Computer Science 2015
August 24-28 2015 – Milano (Italy)

ProgramThursday 27
Room A

Room B
Invited
Talk:
MartinKutrib
9:00
Reversible and Irreversible Computations of Deterministic Finite-State Devices
Coffee Break
10:00
10:30 Bredariol Grilo, Kerenidis, Sikora
Crespi Reghizzi, Lonati, Mandrioli, Pradella
QMA with subset state witnesses
Locally Chain-Parsable Languages
10:55 Mandal, Pavan, Variyam
Latte, Niewerth
On Probabilistic Space-Bounded Machines with
Definability by Weakly Deterministic Regular
Multiple Access to Random Tape
Expressions with Counters is Decidable
11:20 Caferov, Kaya, O'Donnell, Say
Daviaud, Paperman
Optimal Bounds for Estimating Entropy with PMF Classes of languages generated by the Kleene
Queriesstar of a word
11:45 Bottesch, Gavinsky, Klauck
Gajardo, Ollinger, Torres
Equality, Revisited
The transitivity problem of Turing machines
Lunch
12:20
13:30 García-Marco, Koiran, Tavenas
Kiefer, Schweitzer, Selman
Graphs Identified by Logics with Counting
Log-concavity and lower bounds for arithmetic
circuits
13:55 Allender, Gál, Mertz
Aceto, Della Monica, Fabregas, Ingolfsdottir
Dual VP Classes
When are prime formulae characteristic?
14:20 Hahn, Krebs, Lange, Ludwig
Mazowiecki, Ochremiak, Witkowski
Visibly Counter Languages and the Structure ofEliminating recursion from monadic datalog
NC1
programs on trees
14:45 König, Lohrey
Kaminski, Katoen
Parallel Identity Testing for Skew Circuits with Big On the Hardness of Almost-Sure Termination
Powers and Applications
Coffe break
15:10
15:40 Mühlenthaler
Salamanca, Bonsangue, Rutten
Degree-constrained Subgraph Reconfiguration is Equations and Coequations for Weightedin PAutomata
16:05 Wu, Zhang
Droste, Dück
Efficient Algorithm for Computing All Low s-t Edge Weighted Automata and Logics on Graphs
Connectivities in Directed Graphs
16:30 Montanari, PennaAvni, Kupferman
Stochastization of Weighted Automata
On Sampling Simple Paths in Planar Graphs
According to Their Lengths
16:55 Babenko, Goldberg, Kaplan, Savchenko, Weller
Kraehmann, Schubert, Baier, Dubslaff
On the Complexity of Hub Labeling
Ratio and Weight Quantiles

Social DinnerMathematical Foundations of Computer Science 2015
August 24-28 2015 – Milano (Italy)

ProgramFriday 28
Room A

Room B
InvitedTalk:Paolo
Boldi
9:00
Minimal and Monotone Minimal Perfect Hash Functions
Coffee Break
10:00
10:30 Ganian, Kim, Szeider
Iacobelli, Tribastone, Vandin
Algorithmic Applications of Tree-Cut Width
Differential Bisimulation for a Markovian Process
Algebra10:55 Philip, Rai, Saurabh
Dima, Maubert, Pinchinat
Generalized Pseudoforest Deletion: Algorithms
Relating paths in transition systems: the fall of theand Uniform Kernel
modal mu-calculus
11:20 Zu, Zhang, Yu
BoudouFast Dynamic Weight Matchings in Convex
Exponential-size Model Property for PDL with
Bipartite Graphs
Separating Parallel Composition
11:45 Baswana, Choudhary
Grellois, Melliès
On Dynamic DFS Tree in Directed Graphs
Finitary semantics of linear logic and higher-ordermodel-checking
Closing
12:10