STACS 2002 - Preliminary Program |
Thursday 14 March |
||
|---|---|---|
| 8:15 9:00 |
Registration | |
| 9:00 9:30 |
Opening | |
| 9:30 10:30 |
Keynote Talk: Hyper-encryption and everlasting security
M.O. Rabin (Harvard University) joint work with Y.Z. Ding Chair : A. Ferreira |
|
| 10:30 | Coffee Break | |
| 11:00 | Session A : Algorithms - Graphs (chair : H. Alt) | Session B : Computational Complexity (chair : P. Gastin) |
| 12:15 |
- Approximate strong separation with application in fractional graph coloring and preemptive scheduling (K. Jansen)
- Balanced coloring: equally easy for all numbers of colors ? (B. Doerr) - The complexity of graph isomorphism for colored graphs with color classes of size 2 and 3 (J. Köbler, J. Torán) |
- Complexity of semi-algebraic proofs (D. Grigoriev, E. A. Hirsch, D. V. Pasechnik)
- A lower bound technique for restricted branching programs and applications (P. Woelfel) - The complexity of constraints on intervals and lengths (A. Krokhin, P. Jeavons, P. Jonsson) |
12:15 |
Lunch (provided) | |
| 14:15 | Session A : Algorithms - Scheduling (chair : C. Gavoille) | Session B : Automata and Formal Languages (chair : A. Muscholl) |
| 15:30 |
- An asymptotic $O(\ln\rho/\ln\ln\rho)$-approximation algorithm for the scheduling problem with duplication on large communication delay graphs (R. Lepere, C. Rapine)
- Scheduling at twilight the easy way (H. Bast) - Complexity of multi-dimensional loop alignment (A. Darte, G. Huard) |
- Nesting until and since in linear temporal logic (D. Thérien, T. Wilke)
- Comparing verboseness for finite automata and turing machines (T. Tantau) - On the average parallelism in trace monoids (D. Krob, J. Mairesse, I. Michos) |
| 15:30 | Coffee Break | |
| 16:00 | Session A : Complexity (chair : T. Erlebach) | Session B : Logic in Computer Science (chair : P. Gastin) |
| 17:15 |
- On the parameterized intractability of CLOSETS SUBSTRING and related problems (M. R. Fellows, J. Gramm, R. Niedermeier)
- On the complexity of protein similarity search under mRNA structure constraints (R. Backofen, N.S. Narayanaswamy, F. Swidan) - Pure dominance constraints (M. Bodirsky, M. Kutz) |
- Ground tree rewriting graphs of bounded tree width (C. Löding)
- Timed control synthesis for external specifications (D. D`Souza, P. Madhusudan) - Axiomatizing GSOS with termination (J.C.M. Baeten, E.P. de Vink) |
17:30 |
Cocktail |
Friday 15 March |
| 9:00 10:00 |
Invited Talk: Models and techniques for communication in dynamic networks
C. Scheideler (Johns Hopkins University) Chair : J. Durand-Lose |
|
| 10:00 | Session A : Algorithms - Data Mining (chair : Y. Métivier) | Session B : Quantum Computing (chair : M. Santha) |
| 11:00 |
- On the complexity of generating maximal frequent and minimal infrequent sets (E. Boros, V. Gurvich, L. Khachiyan, K. Makino)
- On dualization in products of forests (K. M. Elbassioni) |
- Improved quantum communication complexity bounds for disjointness and equality (P. Høyer, R. de Wolf)
- On quantum computation with some restricted amplitudes (H. Nishimura) |
| 11:00 | Coffee Break | |
| 11:30 | Session A : Algorithms - Routing (chair : M. Morvan) | Session B : Quantum Computing (chair M. Santha) |
| 12:45 |
- A space lower bound for routing in trees (P. Fraigniaud, C. Gavoille)
- Labeling schemes for dynamic tree networks (A. Korman, D. Peleg, Y. Rodeh) - Tight bounds for the performance of Longest-in-System on DAGs (M. Adler, A. Rosén) |
- A quantum Goldreich-Levin theorem with cryptographic applications (M. Adcock, R. Cleve)
- On quantum and approximate privacy (H. Klauck) - On quantum versions of the Yao principle (M. de Graaf, R. de Wolf) |
12:45 |
Lunch (provided) | |
| 14:30 | Session A : Structural Complexity (chair : Y. Métivier) | Session B : Automata and Formal Languages (chair : D. Lugiez) |
| 15:45 |
- Describing parameterized complexity classes (J. Flum, M. Grohe)
- Games with a uniqueness property (S. Aida, M. Crasmaru, K. W. Regan, O. Watanabe) - Bi-immunity separates strong NP-completeness notions (A. Pavan, A. L Selman) |
- A further step towards a theory of regular MSC languages (D. Kuske)
- Existential and positive theories of equations in graph products (V. Diekert, M. Lohrey) - The membership problem for regular expressions with intersection is complete in LOGCFL (H. Petersen) |
| 15:45 | Coffee Break | |
| 16:15 | Session A : Algorithms - Randomness (chair : T. Erlebach) | Session B : Logic in Computer Science (chair : A. Muscholl) |
| 17:30 |
- A probabilistic 3-SAT algorithm further improved (T. Hofmeister, U. Schöning, R. Schuler, O. Watanabe)
- The secret of selective game tree search, when using random-error evaluations (U. Lorenz, B. Monien) - Randomized acceleration of fundamental matrix computations (V. Y. Pan) |
- Axiomatising tree-interpretable structures (A. Blumensath)
- EXPSPACE-complete variant of guarded fragment with transitivity (E. Kieroński) - A parametric analysis of the state explosion problem in model checking (S. Demri, F. Laroussinie, P. Schnoebelen) |
19:30 |
Conference Dinner |
Saturday 16 March |
| 9:00 | Session A : Algorithms - Comp. Geometry (chair : E. Mayr) | Session B : Automata and Formal Languages (chair : D. Lugiez) |
| 10:15 |
- Approximations for ATSP with parametrized triangle inequality (L. S. Chandran, L. S. Ram)
- A new diagram from disks in the plane (J. Giesen, M. John) - Computing the maximum detour and spanning ratio of planar chains, trees and cycles (S. Langerman, P. Morin, M. Soss) |
- Recognizable sets of message sequence charts (R. Morin)
- Strong bisimilarity and regularity of Basic Parallel Processes is PSPACE-hard (J. Srba) - On the enumerative sequences of regular languages on k symbols (M.-P. Béal, D. Perrin) |
| 10:15 | Coffee Break | |
| 10:40 | Session A : Structural Complexity (chair : B. Durand) | Session B : Logic in Computer Science (chair : A. Petit) |
| 11:30 |
- How many missing answers can be tolerated by query learners ? (H. U. Simon)
- On the computational power of boolean decision lists (M. Krause) |
- Generalized model-checking over locally tree-decomposable classes (M. Frick)
- Learnability and definability in trees and similar structures (M. Grohe, G. Turan) |
| 11:30 12:30 |
Invited Talk: What is a theory ?
G. Dowek (INRIA) Chair : H. Alt |
|
12:30 |
Conference Adjourns |
|