program.pdf ]

STACS 2002 - Preliminary Program

Thursday 14 March




Keynote Talk: Hyper-encryption and everlasting security
M.O. Rabin
(Harvard University)
joint work with Y.Z. Ding
Chair : A. Ferreira
10:30Coffee 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)


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:30Coffee 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)



Friday 15 March


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:00Coffee 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)


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:45Coffee 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)


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:15Coffee 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)

Invited Talk: What is a theory ?
G. Dowek
Chair : H. Alt


Conference Adjourns