Portal - STACS 2010

STACS 2010	March 4-6, 2010, Nancy, France
27th International Symposium on Theoretical Aspects of Computer Science Jean-Yves Marion and Thomas Schwentick (Eds.)
ISBN 978-3-939897-16-3, LIPICS Vol. 5	ISSN 1868-8969

Additional Information

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

Authors

Korzeniowski, Miroslaw

Mitzenmacher, Michael

Woeginger, Gerhard J.

Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science

Authors: Marion, Jean-Yves ; Schwentick, Thomas

Abstract | Document (67 KB) | BibTeX

Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science

Authors: Marion, Jean-Yves ; Schwentick, Thomas

Abstract | Document (134 KB) | BibTeX

Beyond omega-Regular Languages

Authors: Bojanczyk, Mikolaj

Abstract | Document (232 KB) | BibTeX

Reflections on Multivariate Algorithmics and Problem Parameterization

Authors: Niedermeier, Rolf

Abstract | Document (310 KB) | BibTeX

Mathematics, Cryptology, Security

Authors: Stern, Jacques

Abstract | Document (156 KB) | BibTeX

Large-Girth Roots of Graphs

Authors: Adamaszek, Anna ; Adamaszek, Michal

Abstract | Document (295 KB) | BibTeX

The Tropical Double Description Method

Authors: Allamigeon, Xavier ; Gaubert, Stéphane ; Goubault, Éric

Abstract | Document (297 KB) | BibTeX

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

Authors: Arvind, Vikraman ; Srinivasan, Srikanth

Abstract | Document (305 KB) | BibTeX

Evasiveness and the Distribution of Prime Numbers

Authors: Babai, László ; Banerjee, Anandam ; Kulkarni, Raghav ; Naik, Vipul

Abstract | Document (311 KB) | BibTeX

Dynamic Sharing of a Multiple Access Channel

Authors: Bienkowski, Marcin ; Klonowski, Marek ; Korzeniowski, Miroslaw ; Kowalski, Dariusz R.

Abstract | Document (292 KB) | BibTeX

Exact Covers via Determinants

Authors: Björklund, Andreas

Abstract | Document (299 KB) | BibTeX

On Iterated Dominance, Matrix Elimination, and Matched Paths

Authors: Brandt, Felix ; Fischer, Felix ; Holzer, Markus

Abstract | Document (300 KB) | BibTeX

AMS Without 4-Wise Independence on Product Domains

Authors: Braverman, Vladimir ; Chung, Kai-Min ; Liu, Zhenming ; Mitzenmacher, Michael ; Ostrovsky, Rafail

Abstract | Document (273 KB) | BibTeX

Quantum Algorithms for Testing Properties of Distributions

Authors: Bravyi, Sergey ; Harrow, Aram W. ; Hassidim, Avinatan

Abstract | Document (300 KB) | BibTeX

Optimal Query Complexity for Reconstructing Hypergraphs

Authors: Bshouty, Nader H. ; Mazzawi, Hanna

Abstract | Document (306 KB) | BibTeX

Ultimate Traces of Cellular Automata

Authors: Cervelle, Julien ; Formenti, Enrico ; Guillon, Pierre

Abstract | Document (326 KB) | BibTeX

Two-phase Algorithms for the Parametric Shortest Path Problem

Authors: Chakraborty, Sourav ; Fischer, Eldar ; Lachish, Oded ; Yuster, Raphael

Abstract | Document (255 KB) | BibTeX

Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window

Authors: Chan, Ho-Leung ; Lam, Tak-Wah ; Lee, Lap-Kei ; Ting, Hing-Fung

Abstract | Document (317 KB) | BibTeX

Robust Fault Tolerant Uncapacitated Facility Location

Authors: Chechik, Shiri ; Peleg, David

Abstract | Document (298 KB) | BibTeX

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Authors: Chen, Victor ; Grigorescu, Elena ; de Wolf, Ronald

Abstract | Document (131 KB) | BibTeX

Log-space Algorithms for Paths and Matchings in k-trees

Authors: Das, Bireswar ; Datta, Samir ; Nimbhorkar, Prajakta

Abstract | Document (304 KB) | BibTeX

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

Authors: Das, Bireswar ; Torán, Jacobo ; Wagner, Fabian

Abstract | Document (311 KB) | BibTeX

The Traveling Salesman Problem under Squared Euclidean Distances

Authors: van Nijnatten, Fred ; Sitters, René ; Woeginger, Gerhard J. ; Wolff, Alexander ; de Berg, Mark

Abstract | Document (329 KB) | BibTeX

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Authors: Dorn, Frederic ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket

Abstract | Document (316 KB) | BibTeX

Planar Subgraph Isomorphism Revisited

Authors: Dorn, Frederic

Abstract | Document (321 KB) | BibTeX

Intrinsic Universality in Self-Assembly

Authors: Doty, David ; Lutz, Jack H. ; Patitz, Matthew J. ; Summers, Scott M. ; Woods, Damien

Abstract | Document (317 KB) | BibTeX

Sponsored Search, Market Equilibria, and the Hungarian Method

Authors: Dütting, Paul ; Henzinger, Monika ; Weber, Ingmar

Abstract | Document (303 KB) | BibTeX

Dispersion in Unit Disks

Authors: Dumitrescu, Adrian ; Jiang, Minghui

Abstract | Document (425 KB) | BibTeX

Long Non-crossing Configurations in the Plane

Authors: Dumitrescu, Adrian ; Tóth, Csaba D.

Abstract | Document (317 KB) | BibTeX

The Complexity of Approximating Bounded-Degree Boolean #CSP

Authors: Dyer, Martin ; Goldberg, Leslie Ann ; Jalsenius, Markus ; Richerby, David

Abstract | Document (314 KB) | BibTeX

The Complexity of the List Homomorphism Problem for Graphs

Authors: Egri, László ; Krokhin, Andrei ; Larose, Benoit ; Tesson, Pascal

Abstract | Document (306 KB) | BibTeX

Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model

Authors: Epstein, Leah ; Levin, Asaf ; Mestre, Julián ; Segev, Danny

Abstract | Document (124 KB) | BibTeX

Computing Least Fixed Points of Probabilistic Systems of Polynomials

Authors: Esparza, Javier ; Gaiser, Andreas ; Kiefer, Stefan

Abstract | Document (183 KB) | BibTeX

The k-in-a-path Problem for Claw-free Graphs

Authors: Fiala, Jiri ; Kaminski, Marcin ; Lidický, Bernard ; Paulusma, Daniël

Abstract | Document (304 KB) | BibTeX

Finding Induced Subgraphs via Minimal Triangulations

Authors: Fomin, Fedor V. ; Villanger, Yngve

Abstract | Document (306 KB) | BibTeX

Inseparability and Strong Hypotheses for Disjoint NP Pairs

Authors: Fortnow, Lance ; Lutz, Jack H. ; Mayordomo, Elvira

Abstract | Document (285 KB) | BibTeX

Branching-time Model Checking of One-counter Processes

Authors: Göller, Stefan ; Lohrey, Markus

Abstract | Document (150 KB) | BibTeX

Evolving Multialgebras Unify All Usual Sequential Computation Models

Authors: Grigorieff, Serge ; Valarcher, Pierre

Abstract | Document (317 KB) | BibTeX

Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Authors: Gu, Xiaoyang ; Hitchcock, John M. ; Pavan, Aduri

Abstract | Document (301 KB) | BibTeX

Revisiting the Rice Theorem of Cellular Automata

Authors: Guillon, Pierre ; Richard, Gaétan

Abstract | Document (299 KB) | BibTeX

On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity

Authors: Hirsch, Edward A. ; Itsykson, Dmitry

Abstract | Document (287 KB) | BibTeX

Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Authors: Jansen, Maurice

Abstract | Document (325 KB) | BibTeX

On Equations over Sets of Integers

Authors: Jez, Artur ; Okhotin, Alexander

Abstract | Document (310 KB) | BibTeX

Randomized Algorithm for Agreeable Deadlines Packet Scheduling

Authors: Jez, Lukasz

Abstract | Document (301 KB) | BibTeX

Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

Authors: Kartzow, Alexander

Abstract | Document (301 KB) | BibTeX

Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs

Authors: Khanna, Neelesh ; Baswana, Surender

Abstract | Document (330 KB) | BibTeX

Holant Problems for Regular Graphs with Complex Edge Functions

Authors: Kowalczyk, Michael ; Cai, Jin-Yi

Abstract | Document (331 KB) | BibTeX

Is Ramsey's Theorem omega-automatic?

Authors: Kuske, Dietrich

Abstract | Document (315 KB) | BibTeX

An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem

Authors: Le Gall, François

Abstract | Document (316 KB) | BibTeX

Treewidth Reduction for Constrained Separation and Bipartization Problems

Authors: Marx, Dániel ; O'Sullivan, Barry ; Razgon, Igor

Abstract | Document (127 KB) | BibTeX

Online Correlation Clustering

Authors: Mathieu, Claire ; Sankur, Ocan ; Schudy, Warren

Abstract | Document (306 KB) | BibTeX

The Recognition of Tolerance and Bounded Tolerance Graphs

Authors: Mertzios, George B. ; Sau, Ignasi ; Zaks, Shmuel

Abstract | Document (317 KB) | BibTeX

Decidability of the Interval Temporal Logic ABB over the Natural Numbers

Authors: Montanari, Angelo ; Puppis, Gabriele ; Sala, Pietro ; Sciavicco, Guido

Abstract | Document (321 KB) | BibTeX

Relaxed Spanners for Directed Disk Graphs

Authors: Peleg, David ; Roditty, Liam

Abstract | Document (284 KB) | BibTeX

Unsatisfiable Linear CNF Formulas Are Large and Complex

Authors: Scheder, Dominik

Abstract | Document (319 KB) | BibTeX

Construction Sequences and Certifying 3-Connectedness

Authors: Schmidt, Jens M.

Abstract | Document (315 KB) | BibTeX

Named Models in Coalgebraic Hybrid Logic

Authors: Schröder, Lutz ; Pattinson, Dirk

Abstract | Document (130 KB) | BibTeX

A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem

Authors: Takhanov, Rustem

Abstract | Document (312 KB) | BibTeX

Alternation-Trading Proofs, Linear Programming, and Lower Bounds

Authors: Williams, Ryan

Abstract | Document (314 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint Published by LZI