Institute of Computer Science
20th International Symposium on Theoretical Aspects of Computer Science
February 27 - March 1, 2003
|
Institute of Computer Science
|
|
|
STACS 2003 20th International Symposium on Theoretical Aspects of Computer Science February 27 - March 1, 2003 |
Wednesday, 26.02.2003
|
||
|---|---|---|
| 18:00 |
Welcome reception and registration  the people / the food  | |
|
Thursday, 27.02.2003
|
||
| 8:00 |
Registration | |
| 8:45 |
Opening | |
| 9:00 |
Logic as a Query
Language: from Frege to XML Victor Vianu, UC San Diego Chair: M. Habib  | |
| 10:00 | Coffee Break | |
| 10:30 | Session A: Graph Drawing, Computational Geometry, Chair: H. Alt | Session B: Formal
Languages Chair: G. Senizergues |
| .
10.55
11.20
11.45 |
Improved Compact Visibility
Representation of Planar Graph via Schnyders Realizer C. Lin, H. Lu, I. Sun  with incredible animations! Rectangle Visibility Graphs: Characterization, Construction, and Compaction, I. Streinu, S. Whitesides  Approximating geometric bottleneck shortest paths, P. Bose, A. Maheshwari, G. Narasimhan, M. Smid, N. Zeh  Optimization in Arrangements, S. Langerman, W. Steiger  |
Complete Classifications for
the Communication Complexity of Regular Languages P. Tesson, D. Therien
 The commutation with codes and ternary sets of words J. Karhumäki, M. Latteux, I. Petre  On the Confluence of Linear Shallow Term Rewrite Systems G. Godoy, A. Tiwari, R. Verma  Wadge degrees of omega-languages of deterministic Turing machines V. Selivanov  |
|
12:10 |
Lunch | |
| 14:00 | Session A: Network Algorithms Chair: P. Fraigniaud |
Session B: Algebraic Complexity Chair: M. Goldwurm |
| .
14.25 14.50 |
Faster deterministic
broadcasting in ad hoc radio networks, D. Kowalski, A. Pelc
 Private Computations in Networks: Topology versus Randomness , A. Jakoby, M. Liskiewicz, R. Reischuk  On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements, T. Erlebach, S. Stefanakos  |
Lattice Reduction by Random
Sampling and Birthday Methods, C. Schnorr
 On the Ultimate Complexity of Factorials, Q. Cheng  On the Effective Jordan Decomposability X. Zheng, R. Rettinger, B. von Braunmühl  |
| 15:15 |
Coffee Break | |
| 15:45 | Session A: Combinatorial Algorithms Chair: R. Wanka |
Session B: Complexity Theory Chair: P. B. Miltersen |
| .
16.10
16.35 |
Fast algorithms for
extended regular expression matching and searching , L. Ilie, B. Shan, S. Yu
 Algorithms for Transposition Invariant String Matching , V. Mäkinen, G. Navarro, E. Ukkonen  On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets , A. Mityagin  |
Some Results on Derandomization,
H. Buhrman, L. Fortnow, A. Pavan
 On the Representation of Boolean Predicates of the Diffie-Hellman Function , E. Kiltz  Quantum circuits with unbounded fan-out, R. Spalek  |
Friday, 28.02.2003
|
||
| 9:00 |
How does Computer Science Change Molecular Biology ? | |
| 10:00 | Coffee Break | |
| 10:30 | Session A: Online Algorithms, Scheduling,
Data Structures Chair: R. Grossi |
Session B: Branching Programs, Logic Chair: M. Krause |
| .
10.55 11.20
11.45 |
Analysis of the Harmonic
Algorithm for Three Servers, M. Chrobak, J. Sgall
This paper was withdrawn. Non-Clairvoyant scheduling for minimizing mean slowdown N. Bansal, K. Dhamdhere, J. Konemann, A. Sinha  Space Efficient Hash Tables With Worst Case Constant Access Time, D. Fotakis, R. Pagh, P. Sanders, P. Spirakis  Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure H. Bronnimann, F. Cazals, M. Durand  |
Complexity Theoretical
Results on Nondeterministic Graph-Driven Read-Once Branching
Programs, B. Bollig
 Randomness versus Nondeterminism for Read-Once and Read-k-Times Branching Program, M. Sauerhoff  Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids Extended Abstract, P. Hlineny  Algebraic Characterizations of Small Classes of Boolean Functions, R. Gavaldà, D. Thèrien  |
|
12:10 |
Lunch | |
| 14:00 | Session A: Shortest-Path Problems Chair: H.-U. Simon |
Session B: Algebraic Complexity, Logic
Chair: A. Bouajjani |
| .
14.25 14.50 |
On the Difficulty of Some Shortest Path Problems, J. Hershberger, S. Suri, A. Bhosle 
T. Feder, A. Meyerson, R. Motwani, L. O'Callaghan, R. Panigrahy 
 |
Solving order constraints in
logarithmic space,
A. Krokhin, B. Larose
 The Inversion Problem for Computable Linear Operators, V. Brattka  Algebras of minimal rank over arbitrary fields, M. Bläser  |
| 15:15 |
Coffee Break | |
| 15:45 | Session A: Graphs, Matchings Chair: M. Habib |
Session B: Complexity, Logic Chair: D. Niwinski |
| .
16.10 16.35 |
Evolutionary Algorithms and
the Maximum Matching Problem, O. Giel, I. Wegener
 Alternative algorithms for counting all matchings in graphs, P. Sankowski  Strong Stability in the Hospitals/Residents Problem R.W. Irving, D.F. Manlove, S. Scott  |
The Inference Problem for
Propositional Circumscription of Affine Formulas is coNP-complete,
A. Durand, M. Hermann
 Decidable theories of Cayley-graphs, D. Kuske, M. Lohrey  The complexity of resolution with generalized symmetry rules, S. Szeider  |
|
19:30 |
Conference Dinner, TV Tower at Alexanderplatz  | |
|
Saturday, 1.3.2003
|
||
| 9:00 |
Invited Talk: Polynomial Ideal Power - A Survey  | |
| 10:00 |
Coffee Break | |
| 10:30 | Session A: Graphs, Combinatorics Chair: M. Grohe |
Session B: Complexity Chair: B. Durand |
| .
10.55 11.20
11.45 |
Colouring random graphs in
expected polynomial time, A. Coja-Oghlan, A. Taraz
 An Information Upper Bound of Planar Graphs Using Triangulation, N. Bonichon, C. Gavoille, N. Hanusse  Finding large independent sets in polynomial expected time A. Coja-Oghlan  Distributed Soft Path Coloring P. Damaschke  |
Competing Provers Yield
Improved Karp--Lipton Collapse Results, J.-Y. Cai, V. Chakaravarthy, L.A. Hemaspaandra, M. Ogihara
 One Bit of Advice, H. Buhrman, R. Chang, L. Fortnow  Strong Reductions and Immunity for Exponential Time, M. Schaefer, F. Stephan  The Complexity of Membership Problems for Arithmetic Circuits over the Natural Numbers, P. McKenzie, K. Wagner  |
|
12:10 |
Lunch | |
| 14:00 | Session A: Optimization Chair: R. Wanka |
Session B: Automata Chair: B. Durand |
| .
14.25 14.50 |
Performance Ratios for the
Differencing Method Applied to the Balanced Number Partitioning
Problem,
W. Michiels, J. Korst, E. Aarts, J. van Leeuwen
 Cake-Cutting is Not a Piece of Cake, M. Magdon-Ismail, C. Busch, M.S. Krishnamoorthy  The Price of Truth: Frugality in Truthful mechanisms, K. Talwar  |
Untameable Timed Automata!
P. Bouyer
 The Intrinsic Universality Problem of One-Dimensional Cellular Automata, N. Ollinger  On sand automata, J. Cervelle, E. Formenti  |
| 15:15 |
Coffee Break | |
| 15:45 | Session A: Algorithms, Complexity Chair: H.-U. Simon |
Session B: Semantics, Logic Chair: A. Bouajjani |
| .
16:10 16:35 |
Adaptive Sorting and the
Information Theoretic Lower Bound, A. Elmasry, M. Fredman
 A Discrete Subexponential Algorithm for Parity Games, H. Björklund, S. Sandberg, S. Vorobyov  Rectangle Visibility Graphs: Characterization, Construction, and Compaction, I. Streinu, S. Whitesides |
Cryptographically Sound and
Machine-Assisted Verification of Security Protocols,
M. Backes,
C. Jacobi
 Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic, V. Bruyère, E. DallOlio, J.-F. Raskin  |
|
16:35 |
End of Conference | |
| DB: stacs03 | Webmaster STACS 2003 |
