| Monday |
|---|
| 8:00-10:00 | welcome breakfast & registration |
| 10:00-10:15 | opening |
| 10:15-11:15 | J. Hopcroft: New research directions in the information age |
| 11:30-14:00 | lunch break |
| | room S3 | room S4 |
| 14:00-14:30 | Xin He and Huaming Zhang. Schnyder Greedy Routing Algorithm |
Klaus Ambos-Spies and Timur Bakibayev. Nontriviality for Exponential Time w.r.t. Weak Reducibilities |
| 14:30-15:00 | Amit Dvir, Boaz Ben-Moshe, Michael Segal and Arie Tamir. Centdian Computation for Sensor Networks |
Ajesh Babu, Nutan Limaye and Girish Varma. Streaming algorithms for some problems in log-space |
| 15:00-15:30 | Petr Golovach, Bernard Lidicky and Daniel Paulusma. L(2,1,1)-Labeling Is NP-Complete for Trees |
Rongquan Feng, Menglong Nie and Hongfeng Wu. Twisted Jacobi Intersections Curves |
| 15:30-16:00 | coffee break |
| 16:00-16:30 | Robert Brijder and Hendrik Jan Hoogeboom. Pivot and Loop Complementation on Graphs and Set Systems |
Laurent Gourves and Jerome Monnot. The Max k-Cut Game and its Strong Equilibria |
| 16:30-17:00 | Bingbing Zhuang and Hiroshi Nagamochi. Generating Internally Triconnected Rooted Graphs |
Jan Kyncl, Josef Cibulka, Viola Meszaros, Rudolf Stolar and Pavel Valtr. Graph sharing games: complexity and connectivity |
| 17:00-17:30 | Martin Birks and Stanley Fung. Temperature Aware Online Scheduling with a Low Cooling Factor |
Peter Biro, Walter Kern and Daniel Paulusma. On solution concepts for matching games |
| Tuesday |
|---|
| Excursion |
| Wednesday |
|---|
| | room S3 | room S4 |
| 9:00-9:30 | Liaoruo Wang and John Hopcroft. Community Structure in Large Complex Networks |
Guillaume Bonfante and Florian Deloup. Complexity invariance of real interpretations |
| 9:30-10:00 | Laurent Gourves, Adria Lyra, Carlos Martinhon and jerome monnot. Complexity of paths, trails and circuits in arc-colored digraphs |
Charles Jordan and Thomas Zeugmann. A Note on the Testability of Ramsey's Class |
| 10:00-10:30 | coffee break |
| 10:30-11:00 | Nicholas Korpelainen, Vadim Lozin and Alexander Tiskin. Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult |
Francine Blanchet-Sadri, Jarett Schwartz, Slater Stich and Benjamin Wyatt. Binary De Bruijn Partial Words with One Hole |
| 11:00-11:30 | Christophe Crespelle and Ioan Todinca. An O(n^2)-time algorithm for the minimal interval completion problem |
Ming-Yang Kao, Henry C. M. Leung, He Sun and Yong Zhang. Deterministic Polynomial-Time Algorithms for Designing Short DNA Words |
| 11:30-12:00 | Sucheta Soundarajan and John Hopcroft. Recovering Social Networks from Contagion Information |
Laurent Bulteau, Guillaume Fertin and Irena Rusu. Revisiting the Minimum Breakpoint Linearization Problem |
| 12:00-14:00 | lunch break |
| Special Session: Proof Complexity |
|---|
| 14:00-14:45 | Stefan Dantchev: Approximate Randomised Proofs. |
| 14:45-15:30 | Edward A. Hirsch: Optimal acceptors and optimal proof systems. |
| 15:30-16:00 | coffee break |
| 16:00-16:45 | Olaf Beyersdorff: Proof complexity of non-classical logics. |
| 16:45-17:30 | Sebastian Muller: Different Approaches to Proof Systems |
| 17:30-18:15 | Iddo Tzameret: Notes on Algebraic Proofs over Noncommutative Formulas. |
| Thursday |
|---|
| 9:30-10:30 | Shang-Hua Teng: The Laplacian
paradigm: Emerging algorithms for massive graphs |
| 10:30-11:00 | coffee break |
| | room S3 | room S4 |
| 11:00-11:30 | Sadish Sadasivam and Huaming Zhang. Closed rectangle-of-influence drawings for irreducible triangulations |
Irina Virbitskaite and Natalya Gribovskaya. A Categorical View of Timed Weak Bisimulation |
| 11:30-12:00 | Johannes Uhlmann and Mathias Weller. Two-Layer Planarization Parameterized by Feedback Edge Set |
G. Michele Pinna and Andrea Saba. Simultaneity in event structures |
| 12:00-14:00 | lunch break |
| Special Session: Computational Geometry |
|---|
| 14:00-14:45 | Christian Knauer: The Complexity of Geometric Problems in High Dimension |
| 14:45-15:30 | Takeshi Tokuyama: Zone diagram and geometric equilibrium |
| 15:30-16:15 | Xavier Goaoc: Basis theorems for smallest enclosing cylinders |
| 16:15-17:00 | Anastasios Sidiropoulos: Metric embeddings for topological graphs |
|
| 18:00-21:00 | Concert and banquet |
| Friday |
|---|
| | room S3 | room S4 |
| 9:00-9:30 | Michael Kowalczyk and Jin-Yi Cai. A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions |
Stefan Ratschan. Safety Verification of Non-linear Hybrid Systems is Quasi-Semidecidable |
| 9:30-10:00 | Pinar Heggernes, Daniel Meister and Udi Rotics. Exploiting restricted linear structure to cope with the hardness of clique-width |
Ian Mackie. A visual model of computation |
| 10:00-10:30 | coffee break |
| 10:30-11:00 | Bourgeois Nicolas, Bruno Escoffier, Vangelis Th. Paschos and Johan M. M. van Rooij. Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n) |
Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov and Alexander Rivosh. Nonlocal quantum XOR games for large number of players |
| 11:00-11:30 | Sylvain Guillemot and Matthias Mnich. Kernel and Fast Algorithm for Dense Triplet Inconsistency |
Benedek Nagy. An automata-theoretic characterization of the Chomsky-hierarchy |
| 11:30-12:00 | Sepp Hartung and Rolf Niedermeier. Incremental List Coloring of Graphs, Parameterized by Conservation | |
