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 | ||
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 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 |