CRDF logo
Международный Симпозиум по Информатике -- в России
CSR 2006
8-12 июня, Санкт-Петербург, Россия

Организаторы: С.-Петербургское отделение Математического института им. В.А.Стеклова РАН
и Международный Математический Институт им. Эйлера
Спонсорская поддержка: Американский фонд гражданских исследований и развития (CRDF)
и Российский фонд фундаментальных исследований (РФФИ)

PDMI logo
RFBR logo

CSR-2006: PRELIMINARY Program

NB: Columns mean parallel sessions.

Wednesday, June 7

8:30-9:00 WOWA'06 REGISTRATION
9:00-18:00 WORKSHOP: WOWA'06
18:00-20:00 WELCOMING RECEPTION
CSR-2006 REGISTRATION

Thursday, June 8

8:30-9:00 REGISTRATION
9:00-10:15 Conference opening.
Opening lecture. Stephen A. Cook (University of Toronto, Canada).
  COFFEE BREAK
10:40-11:40 Invited lecture. Russell Impagliazzo (University of California at San Diego, USA).
 LUNCH
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.
  COFFEE BREAK
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.
  COFFEE BREAK
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).
  COFFEE BREAK
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.
 LUNCH
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.
  COFFEE BREAK
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).
  COFFEE BREAK
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.
 LUNCH
  SOCIAL PROGRAM

Sunday, June 11

9:00-10:00 Invited lecture. Omer Reingold (Weizmann Institute, Israel). Undirected Graph Connectivity in Log-Space.
  COFFEE BREAK
10:20-11:20 Invited lecture. Bob Colwell (R&E Colwell & Assoc. Inc., USA).
 LUNCH
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.
  COFFEE BREAK
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.
  CONFERENCE DINNER

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).
  COFFEE BREAK
10:20-11:20 Invited lecture. Michael Kaminski (Technion, Israel).
 LUNCH
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.
  COFFEE BREAK
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.