Schedule

Revision as of 13:28, 11 June 2013

Schedule of CSR 2013

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

• Monday, 24.06

15:00-18:00 Registration

18:00-20:00 Welcome reception (University Cafeteria)

• Tuesday, 25.06

08:00-09:00 Registration

09:00-09:30 Welcome

09:30-10:30 Opening Lecture Mario Szegedy The Lovasz Local Lemma – a Survey

10:30-11:00 Coffee break

Session 1 Algorithms

 11:00-11:30  Klaus Jansen and Stefan Kraft 
             An Improved Knapsack Solver for Column Generation
 11:30-12:00  Volker Diekert and Armin Weiss 
             QuickHeapsort: Modifications and improved analysis
 12:00-12:30  Pawel Gawrychowski
             Alphabetic minimax trees in linear time

12:30-14:30 Lunch

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

Session 2 Automata

 15:30-16:00  Amaldev Manuel, Anca Muscholl and Gabriele Puppis
             Walking on Data Words
 16:00-16:30  Coffee break
 16:30-17:00  Pavel Martyugin 
             Careful synchronization of partial automata with restricted alphabets
 17:00-17:30  Sven De Felice and Cyril Nicaud
             Random Generation of Deterministic Acyclic Automata using the Recursive Method
 17:30-18:00  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 A short tutorial on order-invariant first-order logic

Session 3 Logic, Proof Complexity

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

Lecture 3 Ryan Williams ACC Circuit Lower Bounds

Session 4 Complexity 1

 Talk 1  Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein
             Information lower bounds via self-reducibility
 Talk 2  Anton Makhlin
             On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles
 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 Alexander Kostochka On coloring of sparse graphs

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  David Janin
             Overlapping tile automata