Schedule

Revision as of 08:11, 11 March 2013

Schedule of CSR 2013 (preliminary)

Morning sessions start at 9:00 and end at 12:30; afternoon sessions start at 14:30 and end at 18:00.

Tuesday, 25.06

Welcome

Opening Lecture Mario Szegedy The Lovasz Local Lemma – a Survey

Session 1 Algorithms

 Talk 1  Klaus Jansen and Stefan Kraft 
             An Improved Knapsack Solver for Column Generation
 Talk 2  Armin Weiss and Volker Diekert
             QuickHeapsort: Modifications and improved analysis
 Talk 3  Pawel Gawrychowski
             Alphabetic minimax trees in linear time

Lecture 1 Alexander Kostochka On coloring of sparse graphs

Session 2 Automata

 Talk 1  David Janin
             Overlapping tile automata
 Talk 2  Pavel Martyugin 
             Careful synchronization of partial automata with restricted alphabets
 Talk 3  Sven De Felice and Cyril Nicaud
             Random Generation of Deterministic Acyclic Automata using the Recursive Method
 Talk 4  Viliam Geffert, Zuzana Bednarova, Carlo Mereghetti and Beatrice Palano
             Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height

Wednesday, 26.06

Lecture 2 Nicole Schweikardt TBA

Session 3 Logic, Proof Complexity

 Talk 1  Alexey Sorokin
             Lower and upper bounds for the length of joins in Lambek calculus
 Talk 2  Barnaby Martin and Stefan Dantchev
             Parameterized Resolution with bounded conjunction
 Talk 3  Luke Friedman and Yixin Xu
             Exponential Lower Bounds for Refuting Random Formulas Using 
             Ordered Binary Decision Diagrams
 Talk 4  Dmitry Itsykson and Vsevolod Oparin
             Graph expansion, Tseitin formulas and resolution proofs for CSP

Lecture 3 Ryan Williams Towards NEXP versus BPP?

Session 4 Complexity 1

 Talk 1  Anton Makhlin
             On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles
 Talk 2  Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein
             Information lower bounds via self-reducibility
 Talk 3  Nikolay Vereshchagin
             An improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP Languages are Hard on the Worst-Case,  
             Then it is Easy to Find Their Hard Instances
 Talk 4  Vladimir Nikishkin
             Amortized communication complexity of an equality predicate

Thursday, 27.06

Lecture 4 Jeffrey Shallit Decidability and Enumeration for Automatic Sequences: A Survey

Session 5 Words and Languages

 Talk 1  Romeo Rizzi and Stйphane Vialette
             On recognizing words that are squares for the shuffle product
 Talk 2  Jozef Jirasek and Galina Jiraskova
             Cyclic Shift on Prefix-Free Languages
 Talk 3  Sergey Avgustinovich and Svetlana Puzynina
             Weak abelian periodicity of infinite words
 Talk 4  Mikhail Vyalyi
             Universality of regular realizability problems

Social program and conference dinner

Friday, 28.06

Lecture 5 Paul Spirakis Potential Functions in Strategic Games

Session 6 Algorithms 2

 Talk 1  Nicolas Boria, Cйcile Murat and Vangelis Paschos
             The Probabilistic Dominating Set problem
 Talk 2  Marek Tesar and Jiri Fiala
             Dichotomy of the H-Quasi-cover problem
 Talk 3  Barnaby Martin and Florent Madelaine
             QCSP on partially reflexive cycles - the wavy line of tractability
 Talk 4  Abuzer Yakaryilmaz
             Quantum alternation

Lecture 6 Gilles Dowek Real numbers, chaos, and the principle of a bounded density of information

Session 7 Complexity 2

 Talk 1  Timofey Stepanov 
             Random selection in few rounds
 Talk 2  Abuzer Yakaryilmaz
             One-counter verifiers for decidable languages
 Talk 3  Andreas Frцhlich, Gergely Kovбsznai and Armin Biere
             More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding
Business meeting

Saturday, 29.06

Lecture 7 Thomas Colcombet Composition with algebra in the background

Session 8 Logic, Automata

 Talk 1  Kshitij Bansal and Stephane Demri
             Model-Checking Bounded Multi-Pushdown Systems
 Talk 2  Manfred Droste and Vitaly Perevoshchikov
             Multi-weighted Automata and MSO Logic
 Talk 3  Amaldev Manuel, Anca Muscholl and Gabriele Puppis
             Walking on Data Words