Program of CSR 2009
Tuesday, August 18
Wednesday, August 19
| 8:30-9:30 |
REGISTRATION
|
|---|
| 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 |
|---|
| 14:00-15:00 | BUSINESS MEETING |
| 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 |
| 19:00 | CONFERENCE DINNER |
|---|
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 |
| 15:00 | SOCIAL PROGRAM |
|---|
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 |
