MFCS (2)

Publications

2015

Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin
Polynomial Kernels for Weighted Problems. MFCS (2) (2015)
Sandro Montanari, Paolo Penna
On Sampling Simple Paths in Planar Graphs According to Their Lengths. MFCS (2) (2015)
Andrei A. Bulatov, Evgeny S. Skvortsov
Phase Transition for Local Search on Planted SAT. MFCS (2) (2015)
Torben Hagerup
Easy Multiple-Precision Divisors and Word-RAM Constants. MFCS (2) (2015)
Daniel König, Markus Lohrey
Parallel Identity Testing for Skew Circuits with Big Powers and Applications. MFCS (2) (2015)
Mona Rahn, Guido Schäfer
Efficient Equilibria in Polymatrix Coordination Games. MFCS (2) (2015)
Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
Almost All Functions Require Exponential Energy. MFCS (2) (2015)
Andreas Cord-Landwehr, Pascal Lenzner
Network Creation Games: Think Global - Act Local. MFCS (2) (2015)
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
On Tinhofer's Linear Programming Approach to Isomorphism Testing. MFCS (2) (2015)
Cafer Caferov, Baris Kaya, Ryan O'Donnell, A. C. Cem Say
Optimal Bounds for Estimating Entropy with PMF Queries. MFCS (2) (2015)
Xiaowei Wu, Chenzi Zhang
Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs. MFCS (2) (2015)
Udo Hoffmann, Linda Kleist, Tillmann Miltzow
Upper and Lower Bounds on Long Dual Paths in Line Arrangements. MFCS (2) (2015)
Moritz Mühlenthaler
Degree-Constrained Subgraph Reconfiguration is in P. MFCS (2) (2015)
Ruiwen Chen
Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases. MFCS (2) (2015)
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
Equality, Revisited. MFCS (2) (2015)
Martijn Baartse, Klaus Meer
An Algebraic Proof of the Real Number PCP Theorem. MFCS (2) (2015)
Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma
The Price of Connectivity for Cycle Transversals. MFCS (2) (2015)
Maxim A. Babenko, Andrew V. Goldberg, Haim Kaplan, Ruslan Savchenko, Mathias Weller
On the Complexity of Hub Labeling (Extended Abstract). MFCS (2) (2015)
Dmitry Kosolobov
Faster Lightweight Lempel-Ziv Parsing. MFCS (2) (2015)
Martijn van Ee, René Sitters
On the Complexity of Master Problems. MFCS (2) (2015)
Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato
On the Complexity of Speed Scaling. MFCS (2) (2015)
Meirav Zehavi
Maximum Minimal Vertex Cover Parameterized by Vertex Cover. MFCS (2) (2015)
Fidaa Abed, Ioannis Caragiannis, Alexandros A. Voudouris
Near-Optimal Asymmetric Binary Matrix Partitions. MFCS (2) (2015)
Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma
Bounding the Clique-Width of H-free Chordal Graphs. MFCS (2) (2015)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. MFCS (2) (2015)
Adam Case, Jack H. Lutz
Mutual Dimension and Random Sequences. MFCS (2) (2015)
Saad Mneimneh, Saman Farhat
The Offline Carpool Problem Revisited. MFCS (2) (2015)
Quan Zu, Miaomiao Zhang, Bin Yu
Fast Dynamic Weight Matchings in Convex Bipartite Graphs. MFCS (2) (2015)
Markus L. Schmid
Finding Consensus Strings with Small Length Difference Between Input and Solution Strings. MFCS (2) (2015)
Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
. MFCS (2) (2015)
Debasis Mandal, Aduri Pavan, N. V. Vinodchandran
On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape. MFCS (2) (2015)
Henning Schnoor, Oliver Woizekowski
Active Linking Attacks. MFCS (2) (2015)
Stefan Fafianie, Stefan Kratsch
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. MFCS (2) (2015)
Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak
Parameterized Algorithms for Parity Games. MFCS (2) (2015)
Daniyar Chumbalov, Andrei E. Romashchenko
Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem. MFCS (2) (2015)
Claude Crépeau, Raza Ali Kazmi
Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem. MFCS (2) (2015)
Diodato Ferraioli, Carmine Ventre
Metastability of Asymptotically Well-Behaved Potential Games - (Extended Abstract). MFCS (2) (2015)
Eric Allender, Anna Gál, Ian Mertz
Dual VP Classes. MFCS (2) (2015)
Robert Ganian, Eun Jung Kim, Stefan Szeider
Algorithmic Applications of Tree-Cut Width. MFCS (2) (2015)
Surender Baswana, Keerti Choudhary
On Dynamic DFS Tree in Directed Graphs. MFCS (2) (2015)
Geevarghese Philip, Ashutosh Rai, Saket Saurabh
Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel. MFCS (2) (2015)
Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas
Log-Concavity and Lower Bounds for Arithmetic Circuits. MFCS (2) (2015)
Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie, José Verschae
Optimal Algorithms and a PTAS for Cost-Aware Scheduling. MFCS (2) (2015)
Vikraman Arvind, Gaurav Rattan, Pushkar S. Joglekar
On the Complexity of Noncommutative Polynomial Factorization. MFCS (2) (2015)
Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu
Densest Subgraph in Dynamic Graph Streams. MFCS (2) (2015)
Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, Lin F. Yang
New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory. MFCS (2) (2015)
Giovanni Di Crescenzo, Brian A. Coan, Jonathan Kirsch
Efficient Computations over Encrypted Data Blocks. MFCS (2) (2015)
Alex Bredariol Grilo, Iordanis Kerenidis, Jamie Sikora
QMA with Subset State Witnesses. MFCS (2) (2015)
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
Metric Dimension of Bounded Width Graphs. MFCS (2) (2015)

volume 9235, 2015

Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II MFCS (2) 9235 (2015)