Portal - STACS 2011

STACS 2011	March 10-12, 2011, Dortmund, Germany
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) Thomas Schwentick and Christoph Dürr (Eds.)
ISBN 978-3-939897-25-5, LIPICS Vol. 9	ISSN 1868-8969

Additional Information

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

Authors

Blanchet-Sadri, Francine

Eggermont, Christian E.J.

Freydenberger, Dominik D.

Halldorsson, Magnus M.

Lopez-Ortiz, Alejandro

Lu, Pinyan

Lustig, Yoad

Mairesse, Jean

Makarychev, Konstantin

Rumyantsev, Andrey Yu.

Sarma M.N., Jayalal

Saurabh, Saket

Scheder, Dominik

Scheideler, Christian

Vinodchandran, N. Variyam

Woeginger, Gerhard J.

Xia, Mingji

Yannakakis, Mihalis

Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Schwentick, Thomas ; Dürr, Christoph

Abstract | Document (526 KB) | BibTeX

Algorithms for Dynamic Speed Scaling

Authors: Albers, Susanne

Abstract | Document (531 KB) | BibTeX

Structural Decomposition Methods and What They are Good For

Authors: Aschinger, Markus ; Drescher, Conrad ; Gottlob, Georg ; Jeavons, Peter ; Thorstensen, Evgenij

Abstract | Document (815 KB) | BibTeX

How to prove security of communication protocols? A discussion on the soundness of formal models w.r.t. computational ones.

Authors: Comon-Lundh, Hubert ; Cortier, Véronique

Abstract | Document (618 KB) | BibTeX

Local dependency dynamic programming in the presence of memory faults

Authors: Caminiti, Saverio ; Finocchi, Irene ; Fusco, Emanuele G.

Abstract | Document (694 KB) | BibTeX

Tight bounds for rumor spreading in graphs of a given conductance

Authors: Giakkoupis, George

Abstract | Document (627 KB) | BibTeX

Tight Bounds For Distributed MST Verification

Authors: Kor, Liah ; Korman, Amos ; Peleg, David

Abstract | Document (685 KB) | BibTeX

Automata based verification over linearly ordered data domains

Authors: Segoufin, Luc ; Torunczyk, Szymon

Abstract | Document (613 KB) | BibTeX

Bottom-up automata on data trees and vertical XPath

Authors: Figueira, Diego ; Segoufin, Luc

Abstract | Document (2,056 KB) | BibTeX

Data Monoids

Authors: Bojanczyk, Mikolaj

Abstract | Document (550 KB) | BibTeX

Minimum s-t cut in undirected planar graphs when the source and the sink are close

Authors: Kaplan, Haim ; Nussbaum, Yahav

Abstract | Document (680 KB) | BibTeX

Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing

Authors: Kolman, Petr ; Scheideler, Christian

Abstract | Document (629 KB) | BibTeX

Compact Visibility Representation of Plane Graphs

Authors: Wang, Jiun-Jie ; He, Xin

Abstract | Document (661 KB) | BibTeX

Telling convex from reflex allows to map a polygon

Authors: Chalopin, Jeremie ; Das, Shantanu ; Disser, Yann ; Mihalak, Matus ; Widmayer, Peter

Abstract | Document (726 KB) | BibTeX

Cross-Composition: A New Technique for Kernelization Lower Bounds

Authors: Bodlaender, Hans L. ; Jansen, Bart M. P. ; Kratsch, Stefan

Abstract | Document (653 KB) | BibTeX

Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter

Authors: Jansen, Bart M. P. ; Bodlaender, Hans L.

Abstract | Document (648 KB) | BibTeX

Hitting forbidden minors: Approximation and Kernelization

Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Misra, Neeldhara ; Philip, Geevarghese ; Saurabh, Saket

Abstract | Document (3,041 KB) | BibTeX

Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)

Authors: Demaine, Erik D. ; Patitz, Matthew J. ; Schweller, Robert T. ; Summers, Scott M.

Abstract | Document (834 KB) | BibTeX

Weakly Unambiguous Morphisms

Authors: Freydenberger, Dominik D. ; Nevisi, Hossein ; Reidenbach, Daniel

Abstract | Document (644 KB) | BibTeX

On Minimal Sturmian Partial Words

Authors: Blanchet-Sadri, Francine ; Lensmire, John

Abstract | Document (760 KB) | BibTeX

Improving PPSZ for 3-SAT using Critical Variables

Authors: Hertli, Timon ; Moser, Robin A. ; Scheder, Dominik

Abstract | Document (704 KB) | BibTeX

The Complexity of Weighted Boolean #CSP Modulo k

Authors: Guo, Heng ; Huang, Sangxia ; Lu, Pinyan ; Xia, Mingji

Abstract | Document (696 KB) | BibTeX

The #CSP Dichotomy is Decidable

Authors: Dyer, Martin ; Richerby, David

Abstract | Document (622 KB) | BibTeX

A speed-up of oblivious multi-head finite automata by cellular automata

Authors: Borelllo, Alex ; Richard, Gaetan ; Terrier, Veronique

Abstract | Document (1,238 KB) | BibTeX

Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision

Authors: Fates, Nazim

Abstract | Document (681 KB) | BibTeX

Probabilistic cellular automata, invariant measures, and perfect sampling

Authors: Busic, Ana ; Mairesse, Jean ; Marcovici, Irene

Abstract | Document (819 KB) | BibTeX

Analysis of Agglomerative Clustering

Authors: Ackermann, Marcel R. ; Bloemer, Johannes ; Kuntze, Daniel ; Sohler, Christian

Abstract | Document (757 KB) | BibTeX

Measuring Learning Complexity with Criteria Epitomizers

Authors: Case, John ; Koetzing, Timo

Abstract | Document (741 KB) | BibTeX

On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data

Authors: Karloff, Howard ; Korn, Flip ; Makarychev, Konstantin ; Rabani, Yuval

Abstract | Document (621 KB) | BibTeX

Unary negation

Authors: ten Cate, Balder ; Segoufin, Luc

Abstract | Document (686 KB) | BibTeX

First-order Fragments with Successor over Infinite Words

Authors: Kallas, Jakub ; Kufleitner, Manfred ; Lauser, Alexander

Abstract | Document (720 KB) | BibTeX

The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete

Authors: Mundhenk, Martin ; Weiß, Felix

Abstract | Document (817 KB) | BibTeX

A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times

Authors: Lopez-Ortiz, Alejandro ; Quimper, Claude-Guy

Abstract | Document (788 KB) | BibTeX

Scheduling for Weighted Flow Time and Energy with Rejection Penalty

Authors: Chan, Sze-Hang ; Lam, Tak-Wah ; Lee, Lap-Kei

Abstract | Document (656 KB) | BibTeX

Clique-width: When Hard Does Not Mean Impossible

Authors: Ganian, Robert ; Hlineny, Petr ; Obdrzalek, Jan

Abstract | Document (739 KB) | BibTeX

From Pathwidth to Connected Pathwidth

Authors: Dereniowski, Dariusz

Abstract | Document (772 KB) | BibTeX

Polynomial Fitting of Data Streams with Applications to Codeword Testing

Authors: McGregor, Andrew ; Rudra, Atri ; Uurtamo, Steve

Abstract | Document (626 KB) | BibTeX

Spectral Sparsification in the Semi-Streaming Setting

Authors: Kelner, Jonathan A. ; Levin, Alex

Abstract | Document (573 KB) | BibTeX

Solovay functions and K-triviality

Authors: Bienvenu, Laurent ; Merkle, Wolfgang ; Nies, Andre

Abstract | Document (619 KB) | BibTeX

Everywhere complex sequences and the probabilistic method

Authors: Rumyantsev, Andrey Yu.

Abstract | Document (542 KB) | BibTeX

Online Scheduling with Interval Conflicts

Authors: Halldorsson, Magnus M. ; Patt-Shamir, Boaz ; Rawitz, Dror

Abstract | Document (669 KB) | BibTeX

Analysis of multi-stage open shop processing systems

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

Abstract | Document (556 KB) | BibTeX

Graphs Encoded by Regular Expressions

Authors: Gulan, Stefan

Abstract | Document (688 KB) | BibTeX

Extended Regular Expressions: Succinctness and Decidability

Authors: Freydenberger, Dominik D.

Abstract | Document (646 KB) | BibTeX

New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs

Authors: Babenko, Maxim ; Gusakov, Alexey

Abstract | Document (612 KB) | BibTeX

Balanced Interval Coloring

Authors: Antoniadis, Antonios ; Hueffner, Falk ; Lenzner, Pascal ; Moldenhauer, Carsten ; Souza, Alexander

Abstract | Document (565 KB) | BibTeX

Symmetric Determinantal Representation of Weakly-Skew Circuits

Authors: Grenet, Bruno ; Kaltofen, Erich L. ; Koiran, Pascal ; Portier, Natacha

Abstract | Document (721 KB) | BibTeX

Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals

Authors: Blaeser, Markus ; Engels, Christian

Abstract | Document (620 KB) | BibTeX

On Isomorphism Testing of Groups with Normal Hall Subgroups

Authors: Qiao, Youming ; Sarma M.N., Jayalal ; Tang, Bangsheng

Abstract | Document (691 KB) | BibTeX

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

Authors: Datta, Samir ; Kulkarni, Raghav ; Tewari, Raghunath ; Vinodchandran, N. Variyam

Abstract | Document (703 KB) | BibTeX

The Recognition of Triangle Graphs

Authors: Mertzios, George B.

Abstract | Document (744 KB) | BibTeX

Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata

Authors: Parys, Pawel

Abstract | Document (568 KB) | BibTeX

Temporal Synthesis for Bounded Systems and Environments

Authors: Kupferman, Orna ; Lustig, Yoad ; Vardi, Moshe Y. ; Yannakakis, Mihalis

Abstract | Document (448 KB) | BibTeX

Linear temporal logic for regular cost functions

Authors: Kuperberg, Denis

Abstract | Document (146 KB) | BibTeX

Bounds on the maximum multiplicity of some common geometric graphs

Authors: Dumitrescu, Adrian ; Schulz, Andre ; Sheffer, Adam ; Toth, Csaba D.

Abstract | Document (813 KB) | BibTeX

On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems

Authors: Knauer, Christian ; Tiwary, Hans Raj ; Werner, Daniel

Abstract | Document (661 KB) | BibTeX

Quantum query complexity of minor-closed graph properties

Authors: Childs, Andrew M. ; Kothari, Robin

Abstract | Document (843 KB) | BibTeX

Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Authors: Gal, Anna ; Mills, Andrew

Abstract | Document (584 KB) | BibTeX

Index of Authors

Authors: Schwentick, Thomas ; Dürr, Christoph

Abstract | Document (66 KB) | BibTeX

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

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)