7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic, June 7-11, 2010
After six successful conferences held in 2004-2009 in China (Bejing, Kunming, Shanghai, Xi'an, ChangSha)
TAMC is leaving Asia for this year, aiming at the heart of Europe!


8:00-10:00welcome breakfast & registration
10:15-11:15J. Hopcroft: New research directions in the information age
11:30-14:00lunch break
 room S3room S4
14:00-14:30Xin 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:00Amit 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:30Petr 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:00coffee break
16:00-16:30Robert 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:00Bingbing 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:30Martin 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
 room S3room S4
9:00-9:30Liaoruo Wang and John Hopcroft. Community Structure in Large Complex Networks Guillaume Bonfante and Florian Deloup. Complexity invariance of real interpretations
9:30-10:00Laurent 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:30coffee break
10:30-11:00Nicholas 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:30Christophe 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:00Sucheta 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:00lunch break
Special Session: Proof Complexity
14:00-14:45Stefan Dantchev: Approximate Randomised Proofs.
14:45-15:30Edward A. Hirsch: Optimal acceptors and optimal proof systems.
15:30-16:00coffee break
16:00-16:45Olaf Beyersdorff: Proof complexity of non-classical logics.
16:45-17:30Sebastian Muller: Different Approaches to Proof Systems
17:30-18:15Iddo Tzameret: Notes on Algebraic Proofs over Noncommutative Formulas.
9:30-10:30Shang-Hua Teng: The Laplacian paradigm: Emerging algorithms for massive graphs
10:30-11:00coffee break
 room S3room S4
11:00-11:30Sadish 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:00Johannes 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:00lunch break
Special Session: Computational Geometry
14:00-14:45Christian Knauer: The Complexity of Geometric Problems in High Dimension
14:45-15:30Takeshi Tokuyama: Zone diagram and geometric equilibrium
15:30-16:15Xavier Goaoc: Basis theorems for smallest enclosing cylinders
16:15-17:00Anastasios Sidiropoulos: Metric embeddings for topological graphs
18:00-21:00 Concert and banquet
 room S3room S4
9:00-9:30Michael 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:00Pinar 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:30coffee break
10:30-11:00Bourgeois 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:30Sylvain 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:00Sepp Hartung and Rolf Niedermeier. Incremental List Coloring of Graphs, Parameterized by Conservation