STACS 2015 March 4-7, 2015 - Garching, Germany

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)



Ernst W. Mayr and Nicolas Ollinger (Eds.)
ISBN 978-3-939897-78-1, LIPICS Vol. 30 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 29 MB)
Search Publication Server

Authors
  • Akhoondian Amiri, Saeed
  • Allender, Eric
  • Arora, Sanjeev
  • Austrin, Per
  • Avanzini, Martin
  • Beyersdorff, Olaf
  • Bhattacharya, Sayan
  • Bodirsky, Manuel
  • Boros, Endre
  • Boyar, Joan
  • Brandt, Felix
  • Brattka, Vasco
  • Brault-Baron, Johann
  • Bringmann, Karl
  • Brunsch, Tobias
  • Bus, Norbert
  • Capelli, Florent
  • Cardinal, Jean
  • Castro, Pablo
  • Chattopadhyay, Arkadev
  • Chew, Leroy
  • Chimani, Markus
  • Colcombet, Thomas
  • Dal Lago, Ugo
  • Delacourt, Martin
  • Dinur, Irit
  • Dvorák, Wolfgang
  • Elbassioni, Khaled
  • Elmasry, Amr
  • Favrholdt, Lene M.
  • Fernau, Henning
  • Fukunaga, Takuro
  • Galby, Esther
  • Garg, Shashwat
  • Gärtner, Bernd
  • Gherardi, Guido
  • Giannopoulou, Archontia C.
  • Goldberg, Andrew V.
  • Goldberg, Paul W.
  • Grandjean, Anaël
  • Grigoriev, Dima
  • Großwendt, Anna
  • Gurvich, Vladimir
  • Hagerup, Torben
  • Harsha, Prahladh
  • Hazla, Jan
  • Hed, Sagi
  • Hellouin de Ménibus, Benjamin
  • Henzinger, Monika
  • Hermelin, Danny
  • Hoffmann, Michael
  • Holden, Dhiraj
  • Holenstein, Thomas
  • Holm, Jacob
  • Hölzl, Rupert
  • Hoyrup, Mathieu
  • Huang, Zengfeng
  • Im, Sungjin
  • Jain, Sanjay
  • Janota, Mikolás
  • Jansson, Jesper
  • Kabanets, Valentine
  • Kaiser, Lukasz
  • Kammer, Frank
  • Kanj, Iyad
  • Kaplan, Haim
  • Kaski, Petteri
  • Kavitha, Telikepalli
  • Kayal, Neeraj
  • Kilmurray, Cecilia
  • Klavík­, Pavel
  • Klein, Philip N.
  • Koivisto, Mikko
  • Kolliopoulos, Stavros G.
  • Kosolobov, Dmitry
  • Krebs, Andreas
  • Kreutzer, Stephan
  • Kudahl, Christian
  • Kusters, Vincent
  • Lacki, Jakub
  • Lange, Klaus-Jörn
  • Li, Angsheng
  • Li, Zhaoxian
  • López-Ortiz, Alejandro
  • Ludwig, Michael
  • Makino, Kazuhisa
  • Manea, Florin
  • Manuel, Amaldev
  • Mathieu, Claire
  • Mayr, Ernst W.
  • Mengel, Stefan
  • Mercas, Robert
  • Mertzios, George B.
  • Mikkelsen, Jesper W.
  • Mnich, Matthias
  • Moseley, Benjamin
  • Moysoglou, Yannis
  • Mukhopadhyay, Sagnik
  • Mustafa, Nabil H.
  • Neary, Turlough
  • Nederlof, Jesper
  • Ollinger, Nicolas
  • Ouaknine, Joël
  • Peng, Pan
  • Piterman, Nir
  • Place, Thomas
  • Podolskii, Vladimir V.
  • Poupet, Victor
  • Pruhs, Kirk
  • Rabinovich, Roman
  • Radunovic, Bozidar
  • Ray, Saurabh
  • Renault, Marc P.
  • Röglin, Heiko
  • Rojas, Cristóbal
  • Rosén, Adi
  • Rotenberg, Eva
  • Saha, Chandan
  • Sanders, Peter
  • Sankowski, Piotr
  • Schmid, Andreas
  • Schmid, Markus L.
  • Schmidt, Jens M.
  • Schweitzer, Pascal
  • Siebertz, Sebastian
  • Spoerhase, Joachim
  • Srinivasan, Srikanth
  • Starnberger, Martin
  • Stephan, Frank
  • Sung, Wing-Kin
  • Tantau, Till
  • Tarjan, Robert E.
  • Thomas, Antonis
  • Tóth, Csaba D.
  • van Leeuwen, Erik Jan
  • Vardi, Shai
  • Varma, Girish
  • Vojnovic, Milan
  • Wettstein, Manuel
  • Worrell, James
  • Wrochna, Marcin
  • Xia, Ge
  • Zeitoun, Marc
  • Zeman, Peter
  • Zetzsche, Georg
  • Zhang, Qin
  • Zhou, Hang
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Mayr, Ernst W. ; Ollinger, Nicolas

    Abstract | Document (538 KB) | BibTeX

    Overcoming Intractability in Unsupervised Learning (Invited Talk)
    Authors: Arora, Sanjeev

    Abstract | Document (355 KB) | BibTeX

    The Complexity of Constraint Satisfaction Problems (Invited Talk)
    Authors: Bodirsky, Manuel

    Abstract | Document (550 KB) | BibTeX

    Parallel Algorithms Reconsidered (Invited Talk)
    Authors: Sanders, Peter

    Abstract | Document (497 KB) | BibTeX

    Computational Social Choice (Tutorial)
    Authors: Brandt, Felix

    Abstract | Document (404 KB) | BibTeX

    Algorithmic Game Theory (Tutorial)
    Authors: Goldberg, Paul W.

    Abstract | Document (406 KB) | BibTeX

    The Minimum Oracle Circuit Size Problem
    Authors: Allender, Eric ; Holden, Dhiraj ; Kabanets, Valentine

    Abstract | Document (679 KB) | BibTeX

    Graph Searching Games and Width Measures for Directed Graphs
    Authors: Akhoondian Amiri, Saeed ; Kaiser, Lukasz ; Kreutzer, Stephan ; Rabinovich, Roman ; Siebertz, Sebastian

    Abstract | Document (684 KB) | BibTeX

    Subset Sum in the Absence of Concentration
    Authors: Austrin, Per ; Kaski, Petteri ; Koivisto, Mikko ; Nederlof, Jesper

    Abstract | Document (687 KB) | BibTeX

    On Sharing, Memoization, and Polynomial Time
    Authors: Avanzini, Martin ; Dal Lago, Ugo

    Abstract | Document (786 KB) | BibTeX

    Proof Complexity of Resolution-based QBF Calculi
    Authors: Beyersdorff, Olaf ; Chew, Leroy ; Janota, Mikolás

    Abstract | Document (746 KB) | BibTeX

    Welfare Maximization with Friends-of-Friends Network Externalities
    Authors: Bhattacharya, Sayan ; Dvorák, Wolfgang ; Henzinger, Monika ; Starnberger, Martin

    Abstract | Document (678 KB) | BibTeX

    Markov Decision Processes and Stochastic Games with Total Effective Payoff
    Authors: Boros, Endre ; Elbassioni, Khaled ; Gurvich, Vladimir ; Makino, Kazuhisa

    Abstract | Document (666 KB) | BibTeX

    Advice Complexity for a Class of Online Problems
    Authors: Boyar, Joan ; Favrholdt, Lene M. ; Kudahl, Christian ; Mikkelsen, Jesper W.

    Abstract | Document (682 KB) | BibTeX

    Las Vegas Computability and Algorithmic Randomness
    Authors: Brattka, Vasco ; Gherardi, Guido ; Hölzl, Rupert

    Abstract | Document (659 KB) | BibTeX

    Understanding Model Counting for beta-acyclic CNF-formulas
    Authors: Brault-Baron, Johann ; Capelli, Florent ; Mengel, Stefan

    Abstract | Document (613 KB) | BibTeX

    Parameterized Complexity Dichotomy for Steiner Multicut
    Authors: Bringmann, Karl ; Hermelin, Danny ; Mnich, Matthias ; van Leeuwen, Erik Jan

    Abstract | Document (733 KB) | BibTeX

    Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
    Authors: Brunsch, Tobias ; Großwendt, Anna ; Röglin, Heiko

    Abstract | Document (645 KB) | BibTeX

    Improved Local Search for Geometric Hitting Set
    Authors: Bus, Norbert ; Garg, Shashwat ; Mustafa, Nabil H. ; Ray, Saurabh

    Abstract | Document (784 KB) | BibTeX

    Arc Diagrams, Flip Distances, and Hamiltonian Triangulations
    Authors: Cardinal, Jean ; Hoffmann, Michael ; Kusters, Vincent ; Tóth, Csaba D. ; Wettstein, Manuel

    Abstract | Document (694 KB) | BibTeX

    Tractable Probabilistic mu-Calculus That Expresses Probabilistic Temporal Logics
    Authors: Castro, Pablo ; Kilmurray, Cecilia ; Piterman, Nir

    Abstract | Document (686 KB) | BibTeX

    Tribes Is Hard in the Message Passing Model
    Authors: Chattopadhyay, Arkadev ; Mukhopadhyay, Sagnik

    Abstract | Document (700 KB) | BibTeX

    Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees
    Authors: Chimani, Markus ; Spoerhase, Joachim

    Abstract | Document (636 KB) | BibTeX

    Combinatorial Expressions and Lower Bounds
    Authors: Colcombet, Thomas ; Manuel, Amaldev

    Abstract | Document (611 KB) | BibTeX

    Construction of mu-Limit Sets of Two-dimensional Cellular Automata
    Authors: Delacourt, Martin ; Hellouin de Ménibus, Benjamin

    Abstract | Document (664 KB) | BibTeX

    Derandomized Graph Product Results Using the Low Degree Long Code
    Authors: Dinur, Irit ; Harsha, Prahladh ; Srinivasan, Srikanth ; Varma, Girish

    Abstract | Document (699 KB) | BibTeX

    Space-efficient Basic Graph Algorithms
    Authors: Elmasry, Amr ; Hagerup, Torben ; Kammer, Frank

    Abstract | Document (521 KB) | BibTeX

    Pattern Matching with Variables: Fast Algorithms and New Hardness Results
    Authors: Fernau, Henning ; Manea, Florin ; Mercas, Robert ; Schmid, Markus L.

    Abstract | Document (703 KB) | BibTeX

    Approximating the Generalized Terminal Backup Problem via Half-integral Multiflow Relaxation
    Authors: Fukunaga, Takuro

    Abstract | Document (632 KB) | BibTeX

    On Matrix Powering in Low Dimensions
    Authors: Galby, Esther ; Ouaknine, Joël ; Worrell, James

    Abstract | Document (638 KB) | BibTeX

    The Complexity of Recognizing Unique Sink Orientations
    Authors: Gärtner, Bernd ; Thomas, Antonis

    Abstract | Document (690 KB) | BibTeX

    New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
    Authors: Giannopoulou, Archontia C. ; Mertzios, George B.

    Abstract | Document (749 KB) | BibTeX

    Comparing 1D and 2D Real Time on Cellular Automata
    Authors: Grandjean, Anaël ; Poupet, Victor

    Abstract | Document (3,108 KB) | BibTeX

    Tropical Effective Primary and Dual Nullstellens"atze
    Authors: Grigoriev, Dima ; Podolskii, Vladimir V.

    Abstract | Document (595 KB) | BibTeX

    Upper Tail Estimates with Combinatorial Proofs
    Authors: Hazla, Jan ; Holenstein, Thomas

    Abstract | Document (614 KB) | BibTeX

    Minimum Cost Flows in Graphs with Unit Capacities
    Authors: Goldberg, Andrew V. ; Kaplan, Haim ; Hed, Sagi ; Tarjan, Robert E.

    Abstract | Document (692 KB) | BibTeX

    Inductive Inference and Reverse Mathematics
    Authors: Hölzl, Rupert ; Jain, Sanjay ; Stephan, Frank

    Abstract | Document (581 KB) | BibTeX

    Dynamic Planar Embeddings of Dynamic Graphs
    Authors: Holm, Jacob ; Rotenberg, Eva

    Abstract | Document (701 KB) | BibTeX

    On the Information Carried by Programs about the Objects They Compute
    Authors: Hoyrup, Mathieu ; Rojas, Cristóbal

    Abstract | Document (647 KB) | BibTeX

    Communication Complexity of Approximate Matching in Distributed Graphs
    Authors: Huang, Zengfeng ; Radunovic, Bozidar ; Vojnovic, Milan ; Zhang, Qin

    Abstract | Document (724 KB) | BibTeX

    Stochastic Scheduling of Heavy-tailed Jobs
    Authors: Im, Sungjin ; Moseley, Benjamin ; Pruhs, Kirk

    Abstract | Document (667 KB) | BibTeX

    On Finding the Adams Consensus Tree
    Authors: Jansson, Jesper ; Li, Zhaoxian ; Sung, Wing-Kin

    Abstract | Document (667 KB) | BibTeX

    Flip Distance Is in FPT Time O(n+ k * c^k)
    Authors: Kanj, Iyad ; Xia, Ge

    Abstract | Document (646 KB) | BibTeX

    New Pairwise Spanners
    Authors: Kavitha, Telikepalli

    Abstract | Document (637 KB) | BibTeX

    Multi-k-ic Depth Three Circuit Lower Bound
    Authors: Kayal, Neeraj ; Saha, Chandan

    Abstract | Document (682 KB) | BibTeX

    Automorphism Groups of Geometrically Represented Graphs
    Authors: Klavík­, Pavel ; Zeman, Peter

    Abstract | Document (708 KB) | BibTeX

    Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs
    Authors: Klein, Philip N. ; Mathieu, Claire ; Zhou, Hang

    Abstract | Document (802 KB) | BibTeX

    Extended Formulation Lower Bounds via Hypergraph Coloring?
    Authors: Kolliopoulos, Stavros G. ; Moysoglou, Yannis

    Abstract | Document (664 KB) | BibTeX

    Lempel-Ziv Factorization May Be Harder Than Computing All Runs
    Authors: Kosolobov, Dmitry

    Abstract | Document (625 KB) | BibTeX

    Visibly Counter Languages and Constant Depth Circuits
    Authors: Krebs, Andreas ; Lange, Klaus-Jörn ; Ludwig, Michael

    Abstract | Document (639 KB) | BibTeX

    Optimal Decremental Connectivity in Planar Graphs
    Authors: Lacki, Jakub ; Sankowski, Piotr

    Abstract | Document (624 KB) | BibTeX

    Testing Small Set Expansion in General Graphs
    Authors: Li, Angsheng ; Peng, Pan

    Abstract | Document (776 KB) | BibTeX

    Paid Exchanges are Worth the Price
    Authors: López-Ortiz, Alejandro ; Renault, Marc P. ; Rosén, Adi

    Abstract | Document (635 KB) | BibTeX

    Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
    Authors: Neary, Turlough

    Abstract | Document (621 KB) | BibTeX

    Separation and the Successor Relation
    Authors: Place, Thomas ; Zeitoun, Marc

    Abstract | Document (605 KB) | BibTeX

    Computing 2-Walks in Polynomial Time
    Authors: Schmid, Andreas ; Schmidt, Jens M.

    Abstract | Document (1,307 KB) | BibTeX

    Towards an Isomorphism Dichotomy for Hereditary Graph Classes
    Authors: Schweitzer, Pascal

    Abstract | Document (521 KB) | BibTeX

    Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification
    Authors: Tantau, Till

    Abstract | Document (656 KB) | BibTeX

    The Returning Secretary
    Authors: Vardi, Shai

    Abstract | Document (616 KB) | BibTeX

    Homomorphism Reconfiguration via Homotopy
    Authors: Wrochna, Marcin

    Abstract | Document (696 KB) | BibTeX

    Computing Downward Closures for Stacked Counter Automata
    Authors: Zetzsche, Georg

    Abstract | Document (610 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI