CRDF logo
International Computer Science Symposium in Russia
CSR 2006
June 8-12, St.Petersburg, Russia

Organized by St.Petersburg Department of Steklov Institute of Mathematics
and Euler International Mathematical Institute
Sponsored by the U.S. Civilian Research & Development Foundation
and Russian Foundation for Basic Research

PDMI logo
RFBR logo


NB: Columns mean parallel sessions.

Wednesday, June 7

9:00-18:00 WORKSHOP: WOWA'06

Thursday, June 8

9:00-10:15 Conference opening.
Opening lecture. Stephen A. Cook (University of Toronto, Canada).
10:40-11:40 Invited lecture. Russell Impagliazzo (University of California at San Diego, USA).
14:00-15:00 Yoram Hirshfeld, Alexander Rabinovich. Expressiveness of Metric Modalities for Continuous Time. Dina Goldin, Huayan Gao. Dynamic Isoline Extraction for Visualization of Streaming Data.
Grigori Mints. Unwinding a Non-Effective Cut Elimination Proof. Sergiy Popov. Nonlinear Visualization of Incomplete Data Sets.
15:20-16:20 Olaf Beyersdorff. Tuples of Disjoint NP-Sets. Panrasee Ritthipravat, Thavida Maneewarn, Jeremy Wyatt, Djitt Laowattana. Fuzzy-Q Knowledge Sharing Techniques with Expertness Measures: A Comparison and Analysis.
Anna Gal, Michal Koucky, Pierre McKenzie. Incremental Branching Programs. Aoun Raza. A Review of Race Detection Mechanisms.
16:40-17:40 Invited lecture. Gerard Berry (Esterel Technologies, France).

Friday, June 9

9:00-10:00 Invited lecture. Byron Cook (Microsoft Research, USA).
10:20-11:50 Leonid Khachiyan, Vladimir Gurvich, Jihui Zhao. Extending Dijkstra's Algorithm to the Shortest Path Interdiction Problem. Freiric Barral, Serge Soloviev. Inductive Type Schemas as Functors. Jan-Willem Roorda, Koen Claessen. Explaining Symbolic Trajectory Evaluation by Giving it a Faithful Semantics.
Florent Madelaine, Stefan Dantchev. Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems. Natalia Rubtsova. Evidence Reconstruction of Epistemic Modal Logic S5. Carsten Sinz, Armin Biere. Extended Resolution Proofs for Conjoining BDDs.
Maxim Babenko. Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure Valery Plisko. On Primitive Recursive Realizabilities. Frederic Loulergue, Radia Benheddi, Frederic Gava, Dimitri Louis-Regis. Bulk Synchronous Parallel ML: Semantics and Implementation of the Parallel Juxposation.
14:00-15:30 Manuel Bodirsky, Jan Kara. The Complexity of Equality Constraint Languages. Daniel Moelle, Stefan Richter, Peter Rossmanith. Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover. Haoran Zhang. A New Flow Control Algorithm for High Speed Computer Network.
Sergei Avgustinovich, Anna Frid. Canonical Decomposition of a Regular Factorial Language. Piotr Berman, Martin Fuerer, Alex Zelikovsky. Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees. Hamid Sarbazi-Azad, Hamid Mahini, Ahmad Patoghy. Analytic Modeling of Channel Traffic in n-Cube Networks.
Alexander Okhotin. Language Equations with Symmetric Difference. Alexander Chistov. Efficient Algorithms in Zero-Characteristic for a New Model of Representation of Algebraic Varieties. Binod Vaidya, SangDuck Lee, SeungJo Han. Authentication Mechanism Using One-Time Password for 802.11 Wireless LAN.
15:50-16:50 Invited lecture. Boaz Barak (Princeton University, USA).
17:00-18:00 Business meeting CSR-2006, CSR-2007.

Saturday, June 10

9:00-10:00 Invited lecture. Pascal Koiran (Ecole Normale Superieure de Lyon, France).
10:20-11:50 Tatiana Yavorskaya (Sidon). Logic of Proofs with Two Proof Predicates. Hartmut Messerschmidt, Friedrich Otto. On Nonforgetting Restarting Automata that Are Deterministic and/or Monotone. Andreas Abel. Polarized Subtyping for Sized Types.
Sergey Dudakov. Isolation and Reducibility Properties and the Collapse Result. Thomas Fernique, Olivier Bodini. Planar Dimer Tilings. Vladimir Tonchev, Hao Wang. Optimal Difference Systems of Sets with Multipliers.
Sergey Shlepakov. Functional Equations in Shostak Theories. Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov. On a Maximal NFA without Mergible States. Feng Lu, Poh-Chin Lai. A Shortest Path Algorithm Based on Limited Search Heuristics.

Sunday, June 11

9:00-10:00 Invited lecture. Omer Reingold (Weizmann Institute, Israel). Undirected Graph Connectivity in Log-Space.
10:20-11:20 Invited lecture. Bob Colwell (R&E Colwell & Assoc. Inc., USA).
13:15-14:45 Andrey Muchnik, Nikolay Vereshchagin. Shannon entropy vs. Kolmogorov complexity. Alexander Tiskin. All Semi-Local Longest Common Subsequences in Subquadratic Time. Konstantin Bournayev. Neural-Network Based Physical Fields Modeling Techniques.
Michael Ustinov. Non-Approximability of the Randomness Deficiency Function. Ingmar Meinecke. Weighted Logics for Traces. Rodolfo A. Pazos R., Joaquin Perez Ortega, Jose A. Martinez F., Juan J. Gonzalez B., Mirna P. Ponce F. Least Likely to Use: a New Page Replacement Strategy for Improving Database Management System Response Time.
Laurent Bienvenu. Constructive Equivalence Relations on Computable Probability Measures. Kalle Saari. On the Frequency of Letters in Morphic Sequences. Haoran Zhang. Nonlinear Systems Modeling and Control Using Support Vector Machine Technique.
15:10-16:10 Patrick Cegielski, Irene Guessarian, Yury Lifshits, Yuri Matiyasevich. Window Subsequence Problems for Compressed Texts. Pooya Shareghi, Hamid Sarbazi-Azad, Navid Imani. Capturing an Intruder in the Pyramid. Xiaogang Dong, Ilya Pollak. Approximate Methods for Constrained Total Variation Minimization.
Vikraman Arvind, Bireswar Das. SZK Proofs for Black-Box Group Problems. Yong-Guk Kim, Min-Soo Jang, Kyoung-Sic Cho. Performance Comparison between Backpropagation, Neuro-Fuzzy Network, and SVM. Pasan Kulvanit, Theera Piroonratana, Nachol Chaiyaratana. Evolutionary Multi-Objective Optimisation by Diversity Control.
16:10-17:10 Invited lecture. Michael Kishinevsky (Intel, USA). Synchronous Elastic Circuits.

Monday, June 12

In parallel to the main conference, a Workshop (Tutorial) on Automata Based Programming (WABP) will be held. The workshop lectures start at 9:00 with registration and preparations since 8:30.

9:00-10:00 Invited lecture. Melvin Fitting (Lehman College and the Graduate Center, CUNY, USA).
10:20-11:20 Invited lecture. Michael Kaminski (Technion, Israel).
13:15-14:45 Evan Goris. Logic of Proofs for Bounded Arithmetic. Dmitry Pavlov. Manipulator Path Planning in 3-Dimensional Space.
Stefan Dantchev. Relativisation Provides Natural Separations for Resolution-Based Proof Systems. XiaoJun Liu, Jie Yang, Hongbin Shen. A New Scaling Kernel-Based Fuzzy System with Low Computational Complexity.
Vladimir Rybakov. Linear Temporal Logic with Until and Before on Integer Numbers, Deciding Algorithms. Elena Zheleva, Abdullah Arslan. Fast Motif Search in Protein Sequence Databases.
15:15-16:15 Marie-Pierre Beal, Sylvain Lombardy, Jacques Sakarovitch. Conjugacy and Equivalence of Weighted Automata and Functional Transducers. Byungryong Kim, Kichang Kim. Improved Technique of IP Address Fragmentation Strategies for DoS Attack Traceback.  
Nicolas Baudru, Remi Morin. Unfolding Synthesis of Asynchronous Automata. Hao-Ming Wang, Ye Guo, Bo-Qin Feng. Optimizing Personalized Retrieval System Based on Web Ranking.