29. STACS 2012: Paris, France

• Christoph Dürr, Thomas Wilke:
  Frontmatter, Foreword, Conference Organization, External Reviewers, Table of Contents.
  
• Thomas Colcombet:
  Forms of Determinism for Automata (Invited Talk). 1-23
  
• R. Ravi:
  Iterative Methods in Combinatorial Optimization (Invited Talk). 24-24
  
• Martin Dietzfelbinger:
  On Randomness in Hash Functions (Invited Talk). 25-28
  
• Shafi Goldwasser:
  Pseudo-deterministic Algorithms (Invited Talk). 29-29
  
• Marcin Mucha:
  13/9-approximation for Graphic TSP. 30-41
  
• Justin Ward:
  A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. 42-53
  
• Pawel Parys:
  A Pumping Lemma for Pushdown Graphs of Any Level. 54-65
  
• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. 66-77
  
• Marc Thurley:
  An Approximation Algorithm for #k-SAT. 78-87
  
• Frédérique Bassino, Julien David, Andrea Sportiello:
  Asymptotic enumeration of Minimal Automata. 88-99
  
• Andreas Emil Feldmann, Luca Foschini:
  Balanced Partitions of Trees and Applications. 100-111
  
• Gerth Stølting Brodal, Casper Kejlberg-Rasmussen:
  Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property. 112-123
  
• Kai-Min Chung, Henry Lam, Zhenming Liu, Michael Mitzenmacher:
  Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified. 124-135
  
• Artur Jez:
  Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P). 136-147
  
• Stefan Göller, Anthony Widjaja Lin:
  Concurrency Makes Simple Theories Hard. 148-159
  
• Andreas Bärtschi, Subhash Suri:
  Conflict-free Chromatic Art Gallery Coverage. 160-171
  
• Wolfgang Merkle, Jason Teutsch:
  Constant compression and random weights. 172-181
  
• Marcin Kaminski, Dimitrios M. Thilikos:
  Contraction checking in graphs on surfaces. 182-193
  
• Arnaud Carayol, Cyril Nicaud:
  Distribution of the number of accessible states in a random deterministic automaton. 194-205
  
• Ken-ichi Kawarabayashi, Yusuke Kobayashi:
  Edge-disjoint Odd Cycles in 4-edge-connected Graphs. 206-217
  
• Volker Diekert, Jürn Laun, Alexander Ushakov:
  Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P. 218-229
  
• Hung Q. Ngo, Ely Porat, Atri Rudra:
  Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion. 230-241
  
• Antoine Durand-Gasselin, Peter Habermehl:
  Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree. 242-253
  
• Samir Datta, Arjun Gopalan, Raghav Kulkarni, Raghunath Tewari:
  Improved Bounds for Bipartite Matching on Surfaces. 254-265
  
• Ioannis Koutis, Alex Levin, Richard Peng:
  Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices. 266-277
  
• Ken-ichi Kawarabayashi, Yusuke Kobayashi:
  Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. 278-289
  
• Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson:
  Linear-Space Data Structures for Range Mode Query in Arrays. 290-301
  
• Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
  Log-supermodular functions, functional clones and counting CSPs. 302-313
  
• George Giakkoupis, Thomas Sauerwald, He Sun, Philipp Woelfel:
  Low Randomness Rumor Spreading via Hashing. 314-325
  
• Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar:
  Lower Bounds on the Complexity of MSO_1 Model-Checking. 326-337
  
• N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh:
  LP can be a cure for Parameterized Problems. 338-349
  
• Sanjay Jain, Efim B. Kinber:
  Mind Change Speed-up for Learning Languages from Positive Data. 350-361
  
• Hervé Fournier, Guillaume Malod, Stefan Mengel:
  Monomials in arithmetic circuits: Complete problems in the counting hierarchy. 362-373
  
• Christian Eggermont, Gerhard J. Woeginger:
  Motion planning with pulley, rope, and baskets. 374-383
  
• Ning Chen:
  On Computing Pareto Stable Assignments. 384-395
  
• André Arnold, Henryk Michalewski, Damian Niwinski:
  On the separation question for tree languages. 396-407
  
• Dieter Mitsche, Guillem Perarnau:
  On the treewidth and related parameters of random geometric graphs. 408-419
  
• Carsten Witt:
  Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. 420-431
  
• Fedor V. Fomin, Petr A. Golovach:
  Parameterized Complexity of Connected Even/Odd Subgraph Problems. 432-440
  
• Benjamin Doerr, Carola Winzen:
  Playing Mastermind With Constant-Size Memory. 441-452
  
• László Babai, Youming Qiao:
  Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. 453-464
  
• Sungjin Im, Maxim Sviridenko, Ruben van der Zwaan:
  Preemptive and Non-Preemptive Generalized Min Sum Set Cover. 465-476
  
• Xiaoming Sun, Chengu Wang:
  Randomized Communication Complexity for Linear Algebra Problems over Finite Fields. 477-488
  
• Frederik Harwath, Nicole Schweikardt:
  Regular tree languages, cardinality predicates, and addition-invariant FO. 489-500
  
• Katarzyna E. Paluch, Khaled M. Elbassioni, Anke van Zuylen:
  Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. 501-506
  
• Tomás Brázdil, Stefan Kiefer:
  Stabilization of Branching Queueing Networks. 507-518
  
• Maurice J. Jansen, Rahul Santhanam:
  Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. 519-530
  
• Paul Bonsma:
  Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces. 531-542
  
• Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, André Nies:
  The Denjoy alternative for computable functions. 543-554
  
• Olivier Finkel:
  The Determinacy of Context-Free Games. 555-566
  
• Mathieu Hoyrup:
  The dimension of ergodic random sequences. 567-576
  
• Faried Abu Zaid, Erich Grädel, Lukasz Kaiser:
  The Field of Reals is not omega-Automatic. 577-588
  
• Christopher H. Broadbent:
  The Limits of Decidability for First Order Logic on CPDA Graphs. 589-600
  
• Yuval Filmus, Justin Ward:
  The Power of Local Search: Maximum Coverage over a Matroid. 601-612
  
• Kei Kimura, Kazuhisa Makino:
  Trichotomy for Integer Linear Systems Based on Their Sign Patterns. 613-623
  
• Pawel Gawrychowski:
  Tying up the loose ends in fully LZW-compressed pattern matching. 624-635
  
• Andris Ambainis:
  Variable time amplitude amplification and quantum algorithms for linear algebra problems. 636-647
  
• Mikolaj Bojanczyk, Szymon Torunczyk:
  Weak MSO+U over infinite trees. 648-660
  

Last update Sun May 19 23:37:37 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page