27. STACS 2010: Nancy, France

• Jean-Yves Marion, Thomas Schwentick:
  Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science. 1-6
  
• Jean-Yves Marion, Thomas Schwentick:
  Table of Contents - 27th International Symposium on Theoretical Aspects of Computer Science. 7-10
  

Invited Talks

• Mikolaj Bojanczyk:
  Beyond omega-Regular Languages. 11-16
  
• Rolf Niedermeier:
  Reflections on Multivariate Algorithmics and Problem Parameterization. 17-32
  
• Jacques Stern:
  Mathematics, Cryptology, Security. 33-34
  

Contributed Papers

• Anna Adamaszek, Michal Adamaszek:
  Large-Girth Roots of Graphs. 35-46
  
• Xavier Allamigeon, Stéphane Gaubert, Eric Goubault:
  The Tropical Double Description Method. 47-58
  
• Vikraman Arvind, Srikanth Srinivasan:
  The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets. 59-70
  
• László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik:
  Evasiveness and the Distribution of Prime Numbers. 71-82
  
• Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski:
  Dynamic Sharing of a Multiple Access Channel. 83-94
  
• Andreas Björklund:
  Exact Covers via Determinants. 95-106
  
• Felix Brandt, Felix A. Fischer, Markus Holzer:
  On Iterated Dominance, Matrix Elimination, and Matched Paths. 107-118
  
• Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky:
  AMS Without 4-Wise Independence on Product Domains. 119-130
  
• Sergey Bravyi, Aram Wettroth Harrow, Avinatan Hassidim:
  Quantum Algorithms for Testing Properties of Distributions. 131-142
  
• Nader H. Bshouty, Hanna Mazzawi:
  Optimal Query Complexity for Reconstructing Hypergraphs. 143-154
  
• Julien Cervelle, Enrico Formenti, Pierre Guillon:
  Ultimate Traces of Cellular Automata. 155-166
  
• Sourav Chakraborty, Eldar Fischer, Oded Lachish, Raphael Yuster:
  Two-phase Algorithms for the Parametric Shortest Path Problem. 167-178
  
• Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee, Hing-Fung Ting:
  Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window. 179-190
  
• Shiri Chechik, David Peleg:
  Robust Fault Tolerant Uncapacitated Facility Location. 191-202
  
• Victor Chen, Elena Grigorescu, Ronald de Wolf:
  Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. 203-214
  
• Bireswar Das, Samir Datta, Prajakta Nimbhorkar:
  Log-space Algorithms for Paths and Matchings in k-trees. 215-226
  
• Bireswar Das, Jacobo Torán, Fabian Wagner:
  Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. 227-238
  
• Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, Mark de Berg:
  The Traveling Salesman Problem under Squared Euclidean Distances. 239-250
  
• Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh:
  Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. 251-262
  
• Frederic Dorn:
  Planar Subgraph Isomorphism Revisited. 263-274
  
• David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, Damien Woods:
  Intrinsic Universality in Self-Assembly. 275-286
  
• Paul Dütting, Monika Henzinger, Ingmar Weber:
  Sponsored Search, Market Equilibria, and the Hungarian Method. 287-298
  
• Adrian Dumitrescu, Minghui Jiang:
  Dispersion in Unit Disks. 299-310
  
• Adrian Dumitrescu, Csaba D. Tóth:
  Long Non-crossing Configurations in the Plane. 311-322
  
• Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
  The Complexity of Approximating Bounded-Degree Boolean #CSP. 323-334
  
• László Egri, Andrei A. Krokhin, Benoit Larose, Pascal Tesson:
  The Complexity of the List Homomorphism Problem for Graphs. 335-346
  
• Leah Epstein, Asaf Levin, Julián Mestre, Danny Segev:
  Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. 347-358
  
• Javier Esparza, Andreas Gaiser, Stefan Kiefer:
  Computing Least Fixed Points of Probabilistic Systems of Polynomials. 359-370
  
• Jirí Fiala, Marcin Kaminski, Bernard Lidický, Daniël Paulusma:
  The k-in-a-path Problem for Claw-free Graphs. 371-382
  
• Fedor V. Fomin, Yngve Villanger:
  Finding Induced Subgraphs via Minimal Triangulations. 383-394
  
• Lance Fortnow, Jack H. Lutz, Elvira Mayordomo:
  Inseparability and Strong Hypotheses for Disjoint NP Pairs. 395-404
  
• Stefan Göller, Markus Lohrey:
  Branching-time Model Checking of One-counter Processes. 405-416
  
• Serge Grigorieff, Pierre Valarcher:
  Evolving Multialgebras Unify All Usual Sequential Computation Models. 417-428
  
• Xiaoyang Gu, John M. Hitchcock, Aduri Pavan:
  Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. 429-440
  
• Pierre Guillon, Gaétan Richard:
  Revisiting the Rice Theorem of Cellular Automata. 441-452
  
• Edward A. Hirsch, Dmitry Itsykson:
  On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity. 453-464
  
• Maurice J. Jansen:
  Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion. 465-476
  
• Artur Jez, Alexander Okhotin:
  On Equations over Sets of Integers. 477-488
  
• Lukasz Jez:
  Randomized Algorithm for Agreeable Deadlines Packet Scheduling. 489-500
  
• Alexander Kartzow:
  Collapsible Pushdown Graphs of Level 2 are Tree-Automatic. 501-512
  
• Neelesh Khanna, Surender Baswana:
  Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs. 513-524
  
• Michael Kowalczyk, Jin-yi Cai:
  Holant Problems for Regular Graphs with Complex Edge Functions. 525-536
  
• Dietrich Kuske:
  Is Ramsey's Theorem omega-automatic?. 537-548
  
• François Le Gall:
  An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem. 549-560
  
• Dániel Marx, Barry O'Sullivan, Igor Razgon:
  Treewidth Reduction for Constrained Separation and Bipartization Problems. 561-572
  
• Claire Mathieu, Ocan Sankur, Warren Schudy:
  Online Correlation Clustering. 573-584
  
• George B. Mertzios, Ignasi Sau, Shmuel Zaks:
  The Recognition of Tolerance and Bounded Tolerance Graphs. 585-596
  
• Angelo Montanari, Gabriele Puppis, Pietro Sala, Guido Sciavicco:
  Decidability of the Interval Temporal Logic ABB over the Natural Numbers. 597-608
  
• David Peleg, Liam Roditty:
  Relaxed Spanners for Directed Disk Graphs. 609-620
  
• Dominik Scheder:
  Unsatisfiable Linear CNF Formulas Are Large and Complex. 621-632
  
• Jens M. Schmidt:
  Construction Sequences and Certifying 3-Connectedness. 633-644
  
• Lutz Schröder, Dirk Pattinson:
  Named Models in Coalgebraic Hybrid Logic. 645-656
  
• Rustem Takhanov:
  A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem. 657-668
  
• Ryan Williams:
  Alternation-Trading Proofs, Linear Programming, and Lower Bounds. 669-680
  

Last update Thu May 24 04:44:46 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page