40. MFCS 2015: Milan, Italy
- Giuseppe F. Italiano, Giovanni Pighizzini, Donald Sannella:
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II. Lecture Notes in Computer Science 9235, Springer 2015, ISBN 978-3-662-48053-3 - Fidaa Abed, Ioannis Caragiannis, Alexandros A. Voudouris:
Near-Optimal Asymmetric Binary Matrix Partitions. 1-13 - Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky:
On Tinhofer's Linear Programming Approach to Isomorphism Testing. 26-37 - Vikraman Arvind, Gaurav Rattan, Pushkar S. Joglekar:
On the Complexity of Noncommutative Polynomial Factorization. 38-49 - Maxim A. Babenko, Andrew V. Goldberg, Haim Kaplan, Ruslan Savchenko, Mathias Weller:
On the Complexity of Hub Labeling (Extended Abstract). 62-74 - Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato:
On the Complexity of Speed Scaling. 75-89 - Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato:
Almost All Functions Require Exponential Energy. 90-101 - Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan:
Metric Dimension of Bounded Width Graphs. 115-126 - Andreas Brandstädt, Konrad Dabrowski, Shenwei Huang, Daniël Paulusma:
Bounding the Clique-Width of H-free Chordal Graphs. 139-150 - Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, Lin F. Yang:
New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory. 151-162 - Cafer Caferov, Baris Kaya, Ryan O'Donnell, A. C. Cem Say:
Optimal Bounds for Estimating Entropy with PMF Queries. 187-198 - Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie, José Verschae:
Optimal Algorithms and a PTAS for Cost-Aware Scheduling. 211-222 - Ruiwen Chen:
Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases. 223-234 - Daniyar Chumbalov, Andrei E. Romashchenko:
Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem. 235-247 - Claude Crépeau, Raza Ali Kazmi:
Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem. 261-273 - Giovanni Di Crescenzo, Brian A. Coan, Jonathan Kirsch:
Efficient Computations over Encrypted Data Blocks. 274-286 - Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
Polynomial Kernels for Weighted Problems. 287-298 - Stefan Fafianie, Stefan Kratsch:
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. 299-310 - Diodato Ferraioli, Carmine Ventre:
Metastability of Asymptotically Well-Behaved Potential Games - (Extended Abstract). 311-323 - Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan:
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. 324-335 - Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak:
Parameterized Algorithms for Parity Games. 336-347 - Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas:
Log-Concavity and Lower Bounds for Arithmetic Circuits. 361-371 - Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig:
Visibly Counter Languages and the Structure of NC1. 384-394 - Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma:
The Price of Connectivity for Cycle Transversals. 395-406 - Udo Hoffmann, Linda Kleist, Tillmann Miltzow:
Upper and Lower Bounds on Long Dual Paths in Line Arrangements. 407-419 - Daniel König, Markus Lohrey:
Parallel Identity Testing for Skew Circuits with Big Powers and Applications. 445-458 - Debasis Mandal, Aduri Pavan, N. V. Vinodchandran:
On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape. 459-471 - Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu:
Densest Subgraph in Dynamic Graph Streams. 472-482 - Sandro Montanari, Paolo Penna:
On Sampling Simple Paths in Planar Graphs According to Their Lengths. 493-504 - Geevarghese Philip, Ashutosh Rai, Saket Saurabh:
Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel. 517-528 - Markus L. Schmid:
Finding Consensus Strings with Small Length Difference Between Input and Solution Strings. 542-554 - Xiaowei Wu, Chenzi Zhang:
Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs. 577-588