The following papers have been accepted for presentation at STACS 2011 and are given without any particular order.
Bruno Grenet, Erich L Kaltofen, Pascal Koiran and Natacha Portier |
| Symmetric Determinantal Representation of Formulas and Weakly-Skew Circuits |
| Petr Kolman and Christian Scheideler |
| Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing |
| George B. Mertzios |
| The Recognition of Triangle Graphs |
| Andrew Childs and Robin Kothari |
| Quantum query complexity of minor-closed graph properties |
| Jakub Kallas, Manfred Kufleitner and Alexander Lauser |
| First-order Fragments with Successor over Infinite Words |
| Stefan Gulan |
| Graphs Encoded by Regular Expressions |
| Alex Levin and Jonathan Kelner |
| Spectral Sparsification in the Semi-Streaming Setting |
| Balder ten Cate and Luc Segoufin |
| Unary negation |
| Pawel Parys |
| Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata |
| Saverio Caminiti, Irene Finocchi and Emanuele Guido Fusco |
| Local dependency dynamic programming in the presence of memory faults |
| Dariusz Dereniowski |
| From Pathwidth to Connected Pathwidth |
| Denis Kuperberg |
| Linear temporal logic for regular cost functions |
| Luc Segoufin and Szymon Torunczyk |
| Automata based verification over linearly ordered data domains |
| Liah Kor, Amos Korman and David Peleg |
| Tight Bounds For Distributed MST Verification |
| Orna Kupferman, Yoad Lustig, Moshe Vardi and Mihalis Yannakakis |
| Temporal Synthesis for Bounded Systems and Environments |
| Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze and Christian Sohler |
| Analysis of Agglomerative Clustering |
| Dominik D. Freydenberger, Hossein Nevisi and Daniel Reidenbach |
| Weakly Unambiguous Morphisms |
| Andrey Rumyantsev |
| Everywhere complex sequences and probabilistic method |
| Timo Kötzing and John Case |
| Measuring learning complexity with criteria epitomizers |
| George Giakkoupis |
| Tight upper bounds for rumor spreading in graphs of a given conductance |
| Nazim Fates |
| Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision |
| Hans L. Bodlaender and Bart M.P. Jansen |
| Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter |
| Haim Kaplan and Yahav Nussbaum |
| Minimum s-t cut in undirected planar graphs when the source and the sink are close |
| Maxim Babenko and Alexey Gusakov |
| New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs |
| Youming Qiao, Jayalal Sarma M.N. and Bangsheng Tang |
| On isomorphism testing of groups with normal hall subgroups |
| Diego Figueira and Luc Segoufin |
| Bottom-up automata on data trees and vertical XPath |
| Howard Karloff, Flip Korn, Konstantin Makarychev and Yuval Rabani |
| On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data |
| Ana Busic, Jean Mairesse and Irene Marcovici |
| Probabilistic cellular automata, invariant measures, and perfect sampling |
| Antonios Antoniadis, Falk Hüffner, Pascal Lenzner, Carsten Moldenhauer and Alexander Souza |
| Balanced Interval Coloring |
| Christian Eggermont, Alexander Schrijver and Gerhard Woeginger |
| Analysis of multi-stage open shop processing systems |
| Alex Borello, Gaétan Richard and Véronique Terrier |
| A speed-up of oblivious multi-head finite automata by cellular automata |
| Laurent Bienvenu, Wolfgang Merkle and André Nies |
| Solovay functions and K-triviality |
| Magnus M. Halldorsson, Boaz Patt-Shamir and Dror Rawitz |
| Online Scheduling with Interval Conflicts |
| Alejandro López-Ortiz and Claude-Guy Quimper |
| A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times |
| Samir Datta, Raghav Kulkarni, Raghunath Tewari and N.V. Vinodchandran |
| Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs |
| Jiun-Jie Wang and Xin He |
| Compact visibility representation of plane graphs |
| Timon Hertli, Robin Moser and Dominik Scheder |
| Improving PPSZ for 3-SAT using Crtitical Variables |
| Felix Weiß and Martin Mundhenk |
| The model checking problem for propositional intuitionistic logic with one variable is AC1-complete |
| Dominik Freydenberger |
| Extended Regular Expressions: Succinctness and Decidability |
| Robert Ganian, Petr Hlineny and Jan Obdrzalek |
| Clique-width: When Hard Does Not Mean Impossible |
| Andrew McGregor, Atri Rudra and Steve Uurtamo |
| Polynomial Fitting of Data Streams with Applications to Codeword Testing |
| Sze-Hang Chan, Tak-Wah Lam and Lap-Kei Lee |
| Scheduling for Weighted Flow Time and Energy with Rejection Penalty |
| Christian Engels and Markus Bläser |
| Randomness Efficient Testing of Sparse Blackbox Identities of Unbounded Degree over the Reals |
| Martin Dyer and David Richerby |
| The #CSP Dichotomy is Decidable |
| Anna Gal and Andrew Mills |
| Three query locally decodable codes with higher correctness require exponential length |
| Scott Summers, Matthew Patitz, Robert Schweller and Erik Demaine |
| Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound With Small Scale Factor (Extended Abstract) |
| Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia |
| The Complexity of Weighted Boolean #CSP Modulo k |
| Jérémie Chalopin, Shantanu Das, Yann Disser, Matus Mihalak and Peter Widmayer |
| Telling convex from reflex allows to map a polygon |
| Mikolaj Bojanczyk |
| Data Monoids |
| Christian Knauer, Hans Raj Tiwary and Daniel Werner |
| On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems |
| Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip and Saket Saurabh |
| Hitting forbidden minors: Approximation and Kernelization |
| Hans L. Bodlaender, Bart M.P. Jansen and Stefan Kratsch |
| Cross-Composition: A New Technique for Kernelization Lower Bounds |
| Francine Blanchet-Sadri and John Lensmire |
| On Minimal Sturmian Partial Words |
| Adrian Dumitrescu, Andre Schulz, Adam Sheffer and CSABA D. Toth |
| Bounds on the Maximum Multiplicity of some Common Geometric Graphs |