4th International Computer Science Symposium in Russia

CSR-2009 August 18-23, 2009
Novosibirsk, Russia


Important dates


Invited speakers


Travel Information

Previous CSRs

Program of CSR 2009

Tuesday, August 18


Wednesday, August 19

9:30-10:30 OPENING LECTURE: Andrei Voronkov
10:30-11:00 Coffee break
11:00-11:30 Edward Hirsch, Sergey Nikolenko. A feebly secure trapdoor function
11:30-12:00 Yi Deng, Giovanni Di Crescenzo, Dongdai Lin and Dengguo Feng. Black-box concurrent non-malleable zero knowledge in the bare public key model
12:00-12:30 Ely Porat. An optimal Bloom Filter replacement based on matrix solving
12:30-14:00 Lunch
15:00-15:30 Coffee break
15:30-16:00 Andreas Goerdt. On random ordering constraints
16:00-16:30 Peter Jonsson and Johan Thapper. Approximability of the Maximum Solution Problem for certain families of algebras
16:30-17:00 Chris Calabro and Ramamohan Paturi. k-SAT is no harder than Decision-Unique-k-SAT

Thursday, August 20

9:30-10:30 INVITED TALK: Wolfgang Thomas
10:30-11:00 Coffee break
11:00-11:30 Tommy Färnqvist, Peter Jonsson and Johan Thapper. Approximability distance in the space of H-colourability problems
11:30-12:00 Pim van 't Hof, Daniel Paulusma and Gerhard Woeginger. Partitioning graphs into connected parts
12:00-12:30 Arnon Avron, Agata Ciabattoni and Anna Zamansky. Canonical Calculi: Invertibility, Axiom expansion and (Non)-determinism
12:30-14:00 Lunch
14:00-14:30 Christian Choffrut and Juhani Karhumäki. Unique decipherability in the monoid of languages: an application of rational relations
14:30-15:00 Artur Jez and Alexander Okhotin. One-nonterminal conjunctive grammars over a unary alphabet
15:00-15:30 Galina Jiraskova. Concatenation of regular languages and descriptional complexity
15:30-16:00 Coffee break
16:00-16:30 Kristoffer Arnsfelt Hansen. Depth reduction for circuits with a single layer of modular counting gates
16:30-17:00 Maurice Jansen and Raghavendra Rao B. V. Simulation of arithmetical circuits by branching programs preserving constant width and syntactic multilinearity

Friday, August 21

9:30-10:30 INVITED TALK: Nikolai Vereshchagin
10:30-11:00 Coffee break
11:00-11:30 Alexander Kononov, Sergey Sevastyanov and Maxim Sviridenko. Complete complexity classification of short shop scheduling
11:30-12:00 Philippe Baptiste, Jaques Carlier, Alexander Kononov, Maurice Queyranne, Sergey Sevastyanov and Maxim Sviridenko. Integrality Property in Preemptive Parallel Machine Scheduling
12:00-12:30 Sergey Tverdyshev and Mark Hillebrand. Formal verification of gate-level computer systems
12:30-14:00 Lunch
14:00-14:30 Yuri Pritykin and Julya Ulyashkina. Aperiodicity measure for infinite sequences
14:30-15:00 Dmitry Itsykson. Structural complexity of AvgBPP

Saturday, August 22

9:30-10:30 INVITED TALK: Hongseok Yang
10:30-11:00 Coffee break
11:00-11:30 Markus Lohrey and Niko Haubold. Compressed word problems in HNN-extensions and amalgamated products
11:30-12:00 Maurice Jansen. Lower bounds for the determinantal complexity of explicit low degree polynomials
12:00-12:30 Somnath Sikdar, Neeldhara Misra, Saket Saurabh and Venkatesh Raman. The budgeted unique coverage problem and color-coding
12:30-14:00 Lunch
14:00-14:30 Daniil Musatov, Andrei Romashchenko and Alexander Shen. Variations on Muchnik's conditional complexity theorem
14:30-15:00 Stefan Richter, Daniel Moelle, Peter Rossmanith and Dogan Kesdogan. Breaking anonymity by learning a unique minimum hitting set
15:00-15:30 Coffee break
15:30-16:00 Raghavendra Rao B. V. and Jayalal M.N. Sarma. On the complexity of matroid isomorphism problem
16:00-16:30 Magnus Wahlström. New Plain-Exponential Time Classes for Graph Homomorphism

Sunday, August 23

9:30-10:30 INVITED TALK: Sergei Odintsov
10:30-11:00 Coffee break
11:00-11:30 Abuzer Yakaryilmaz and A.C. Cem Say. Languages recognized with unbounded error by quantum finite automata
11:30-12:00 Olaf Beyersdorff and Zenon Sadowski. Characterizing the existence of optimal proof systems and complete sets for promise classes
12:00-12:30 Mikhail Vyalyi. On models of a nondeterministic computation