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