Portal - STACS 2012

STACS 2012	February 29th - March 3rd, 2012, Paris, France
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) Christoph Dürr and Thomas Wilke (Eds.)
ISBN 978-3-939897-35-4, LIPICS Vol. 14	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 28 MB)
Search Publication Server

Authors

Broadbent, Christopher H.

Dietzfelbinger, Martin

Doerr, Benjamin

Durand-Gasselin, Antoine

Durocher, Stephane

Dürr, Christoph

Dyer, Martin

Eggermont, Christian E.J.

Elbassioni, Khaled

Elberfeld, Michael

Feldmann, Andreas Emil

Kawarabayashi, Ken-ichi

Kejlberg-Rasmussen, Casper

Mitzenmacher, Michael

Stølting Brodal, Gerth

Thilikos, Dimitrios M.

Woeginger, Gerhard J.

Woelfel, Philipp

Frontmatter, Foreword, Conference Organization, External Reviewers, Table of Contents

Authors: Dürr, Christoph ; Wilke, Thomas

Abstract | Document (477 KB) | BibTeX

Forms of Determinism for Automata (Invited Talk)

Authors: Colcombet, Thomas

Abstract | Document (966 KB) | BibTeX

Iterative Methods in Combinatorial Optimization (Invited Talk)

Authors: Ravi, R.

Abstract | Document (335 KB) | BibTeX

On Randomness in Hash Functions (Invited Talk)

Authors: Dietzfelbinger, Martin

Abstract | Document (355 KB) | BibTeX

Pseudo-deterministic Algorithms (Invited Talk)

Authors: Goldwasser, Shafi

Abstract | Document (384 KB) | BibTeX

13/9-approximation for Graphic TSP

Authors: Mucha, Marcin

Abstract | Document (587 KB) | BibTeX

A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

Authors: Ward, Justin

Abstract | Document (562 KB) | BibTeX

A Pumping Lemma for Pushdown Graphs of Any Level

Authors: Parys, Pawel

Abstract | Document (583 KB) | BibTeX

Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

Authors: Elberfeld, Michael ; Jakoby, Andreas ; Tantau, Till

Abstract | Document (587 KB) | BibTeX

An Approximation Algorithm for #k-SAT

Authors: Thurley, Marc

Abstract | Document (539 KB) | BibTeX

Asymptotic enumeration of Minimal Automata

Authors: Bassino, Frédérique ; David, Julien ; Sportiello, Andrea

Abstract | Document (670 KB) | BibTeX

Balanced Partitions of Trees and Applications

Authors: Feldmann, Andreas Emil ; Foschini, Luca

Abstract | Document (782 KB) | BibTeX

Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property

Authors: Stølting Brodal, Gerth ; Kejlberg-Rasmussen, Casper

Abstract | Document (757 KB) | BibTeX

Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified

Authors: Chung, Kai-Min ; Lam, Henry ; Liu, Zhenming ; Mitzenmacher, Michael

Abstract | Document (649 KB) | BibTeX

Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)

Authors: Jez, Artur

Abstract | Document (855 KB) | BibTeX

Concurrency Makes Simple Theories Hard

Authors: Göller, Stefan ; Widjaja Lin, Anthony

Abstract | Document (592 KB) | BibTeX

Conflict-free Chromatic Art Gallery Coverage

Authors: Bärtschi, Andreas ; Suri, Subhash

Abstract | Document (622 KB) | BibTeX

Constant compression and random weights

Authors: Merkle, Wolfgang ; Teutsch, Jason

Abstract | Document (473 KB) | BibTeX

Contraction checking in graphs on surfaces

Authors: Kaminski, Marcin ; Thilikos, Dimitrios M.

Abstract | Document (2,362 KB) | BibTeX

Distribution of the number of accessible states in a random deterministic automaton

Authors: Carayol, Arnaud ; Nicaud, Cyril

Abstract | Document (784 KB) | BibTeX

Edge-disjoint Odd Cycles in 4-edge-connected Graphs

Authors: Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke

Abstract | Document (947 KB) | BibTeX

Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P

Authors: Diekert, Volker ; Laun, Jürn ; Ushakov, Alexander

Abstract | Document (745 KB) | BibTeX

Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion

Authors: Ngo, Hung Q. ; Porat, Ely ; Rudra, Atri

Abstract | Document (646 KB) | BibTeX

Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree

Authors: Durand-Gasselin, Antoine ; Habermehl, Peter

Abstract | Document (839 KB) | BibTeX

Improved Bounds for Bipartite Matching on Surfaces

Authors: Datta, Samir ; Gopalan, Arjun ; Kulkarni, Raghav ; Tewari, Raghunath

Abstract | Document (609 KB) | BibTeX

Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices

Authors: Koutis, Ioannis ; Levin, Alex ; Peng, Richard

Abstract | Document (638 KB) | BibTeX

Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid

Authors: Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke

Abstract | Document (747 KB) | BibTeX

Linear-Space Data Structures for Range Mode Query in Arrays

Authors: Chan, Timothy M. ; Durocher, Stephane ; Larsen, Kasper Green ; Morrison, Jason ; Wilkinson, Bryan T.

Abstract | Document (610 KB) | BibTeX

Log-supermodular functions, functional clones and counting CSPs

Authors: Bulatov, Andrei A. ; Dyer, Martin ; Goldberg, Leslie Ann ; Jerrum, Mark

Abstract | Document (613 KB) | BibTeX

Low Randomness Rumor Spreading via Hashing

Authors: Giakkoupis, George ; Sauerwald, Thomas ; Sun, He ; Woelfel, Philipp

Abstract | Document (628 KB) | BibTeX

Lower Bounds on the Complexity of MSO_1 Model-Checking

Authors: Ganian, Robert ; Hlineny, Petr ; Langer, Alexander ; Obdržálek, Jan ; Rossmanith, Peter ; Sikdar, Somnath

Abstract | Document (680 KB) | BibTeX

LP can be a cure for Parameterized Problems

Authors: Narayanaswamy, N.S. ; Raman, Venkatesh ; Ramanujan, M.S. ; Saurabh, Saket

Abstract | Document (654 KB) | BibTeX

Mind Change Speed-up for Learning Languages from Positive Data

Authors: Jain, Sanjay ; Kinber, Efim

Abstract | Document (561 KB) | BibTeX

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Authors: Fournier, Hervé ; Malod, Guillaume ; Mengel, Stefan

Abstract | Document (880 KB) | BibTeX

Motion planning with pulley, rope, and baskets

Authors: Eggermont, Christian E.J. ; Woeginger, Gerhard J.

Abstract | Document (499 KB) | BibTeX

On Computing Pareto Stable Assignments

Authors: Chen, Ning

Abstract | Document (656 KB) | BibTeX

On the separation question for tree languages

Authors: Arnold, André ; Michalewski, Henryk ; Niwinski, Damian

Abstract | Document (676 KB) | BibTeX

On the treewidth and related parameters of random geometric graphs

Authors: Mitsche, Dieter ; Perarnau, Guillem

Abstract | Document (871 KB) | BibTeX

Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation

Authors: Witt, Carsten

Abstract | Document (625 KB) | BibTeX

Parameterized Complexity of Connected Even/Odd Subgraph Problems

Authors: Fomin, Fedor V. ; Golovach, Petr A.

Abstract | Document (657 KB) | BibTeX

Playing Mastermind With Constant-Size Memory

Authors: Doerr, Benjamin ; Winzen, Carola

Abstract | Document (584 KB) | BibTeX

Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers

Authors: Babai, László ; Qiao, Youming

Abstract | Document (606 KB) | BibTeX

Preemptive and Non-Preemptive Generalized Min Sum Set Cover

Authors: Im, Sungjin ; Sviridenko, Maxim ; van der Zwaan, Ruben

Abstract | Document (674 KB) | BibTeX

Randomized Communication Complexity for Linear Algebra Problems over Finite Fields

Authors: Sun, Xiaoming ; Wang, Chengu

Abstract | Document (619 KB) | BibTeX

Regular tree languages, cardinality predicates, and addition-invariant FO

Authors: Harwath, Frederik ; Schweikardt, Nicole

Abstract | Document (586 KB) | BibTeX

Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem

Authors: Paluch, Katarzyna ; Elbassioni, Khaled ; van Zuylen, Anke

Abstract | Document (557 KB) | BibTeX

Stabilization of Branching Queueing Networks

Authors: Brázdil, Tomáš ; Kiefer, Stefan

Abstract | Document (676 KB) | BibTeX

Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes

Authors: Jansen, Maurice ; Santhanam, Rahul

Abstract | Document (613 KB) | BibTeX

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

Authors: Bonsma, Paul

Abstract | Document (479 KB) | BibTeX

The Denjoy alternative for computable functions

Authors: Bienvenu, Laurent ; Hölzl, Rupert ; Miller, Joseph S. ; Nies, André

Abstract | Document (630 KB) | BibTeX

The Determinacy of Context-Free Games

Authors: Finkel, Olivier

Abstract | Document (587 KB) | BibTeX

The dimension of ergodic random sequences

Authors: Hoyrup, Mathieu

Abstract | Document (653 KB) | BibTeX

The Field of Reals is not omega-Automatic

Authors: Abu Zaid, Faried ; Grädel, Erich ; Kaiser, Lukasz

Abstract | Document (606 KB) | BibTeX

The Limits of Decidability for First Order Logic on CPDA Graphs

Authors: Broadbent, Christopher H.

Abstract | Document (704 KB) | BibTeX

The Power of Local Search: Maximum Coverage over a Matroid

Authors: Filmus, Yuval ; Ward, Justin

Abstract | Document (528 KB) | BibTeX

Trichotomy for Integer Linear Systems Based on Their Sign Patterns

Authors: Kimura, Kei ; Makino, Kazuhisa

Abstract | Document (544 KB) | BibTeX

Tying up the loose ends in fully LZW-compressed pattern matching

Authors: Gawrychowski, Pawel

Abstract | Document (568 KB) | BibTeX

Variable time amplitude amplification and quantum algorithms for linear algebra problems

Authors: Ambainis, Andris

Abstract | Document (496 KB) | BibTeX

Weak MSO+U over infinite trees

Authors: Bojanczyk, Mikolaj ; Torunczyk, Szymon

Abstract | Document (1,696 KB) | BibTeX

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

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)