Mathematical Foundations of Computer Science 2014

1. Front Matter

   PDF

2. Algorithms, Complexity and Games

   1. On r-Simple k-Path

      • Hasan Abasi, Nader H. Bshouty, Ariel Gabizon, Elad Haramaty

      Pages 1-12

   2. Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

      • Eric Allender, Nikhil Balaji, Samir Datta

      Pages 13-24

   3. Zero Knowledge and Circuit Minimization

      • Eric Allender, Bireswar Das

      Pages 25-32

   4. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

      • Andris Ambainis, Krišjānis Prūsis

      Pages 33-44

   5. \(\widetilde{O}(\sqrt{n})\)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability

      • Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

      Pages 45-56

   6. Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set

      • Rémy Belmonte, Pim van ’t Hof, Marcin Kamiński, Daniël Paulusma

      Pages 57-68

   7. Network-Based Dissolution

      • René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger

      Pages 69-80

   8. On Unification of QBF Resolution-Based Calculi

      • Olaf Beyersdorff, Leroy Chew, Mikoláš Janota

      Pages 81-93

   9. Minimum Planar Multi-sink Cuts with Connectivity Priors

      • Ivona Bezáková, Zachary Langley

      Pages 94-105

   10. The Price of Envy-Freeness in Machine Scheduling

       • Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli

       Pages 106-117

   11. On the Complexity of Some Ordering Problems

       • Beate Bollig

       Pages 118-129

   12. The Relationship between Multiplicative Complexity and Nonlinearity

       • Joan Boyar, Magnus Gausdal Find

       Pages 130-140

   13. Dual Connectedness of Edge-Bicolored Graphs and Beyond

       • Leizhen Cai, Junjie Ye

       Pages 141-152

   14. Combinatorial Voter Control in Elections

       • Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon

       Pages 153-164

   15. An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

       • Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

       Pages 165-176

   16. On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields

       • Suryajith Chillara, Partha Mukhopadhyay

       Pages 177-188

   17. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth

       • Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk

       Pages 189-200

   18. Probabilistic Analysis of Power Assignments

       • Maurits de Graaf, Bodo Manthey

       Pages 201-212

   19. Existence of Secure Equilibrium in Multi-player Games with Perfect Information

       • Julie De Pril, János Flesch, Jeroen Kuipers, Gijs Schoenmakers, Koos Vrieze

       Pages 213-225

This two volume set LNCS 8634 and LNCS 8635 constitutes the refereed conference proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014, held in Budapest, Hungary, in August 2014. The 95 revised full papers presented together with 6 invited talks were carefully selected from 270 submissions. The focus of the conference was on following topics: Logic, Semantics, Automata, Theory of Programming, Algorithms, Complexity, Parallel and Distributed Computing, Quantum Computing, Automata, Grammars and Formal Languages, Combinatorics on Words, Trees and Games.

• algebra and categories in computer science
• algorithmic game theory
• algorithmic learning theory
• algorithms and data structures
• approximation algorithms
• automata
• computational complexity
• concurrency theory
• cryptography and security
• databases and knowledge-based systems
• formal specifications and program development
• foundations of computing
• grammars and formal languages
• lambda-calculus
• linear programming
• logic
• networks
• parallel and distributed computing
• quantum computing
• semantics and verification of programs
• algorithm analysis and problem complexity

• Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary

  Erzsébet Csuhaj-Varjú

• Fakultät für Informatik und Automatisierung, Technische Universität Ilmenau, Ilmenau, Germany

  Martin Dietzfelbinger

• Institute of Informatics, Szeged University, Szeged, Hungary

  Zoltán Ésik

Policies and ethics