From CSR 2013
Jump to: navigation, search

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 (Ural University, pr. Lenina, 51)

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

  • Tuesday, 25.06

08:00-09:00 Registration (Ural University, pr. Lenina, 51)

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

14:30-15:30 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

09:00-10:00 Lecture 2 Nicole Schweikardt A short tutorial on order-invariant first-order logic

Session 3 Logic, Proof Complexity

 10:00-10:30  Luke Friedman and Yixin Xu
             Exponential Lower Bounds for Refuting Random Formulas Using 
             Ordered Binary Decision Diagrams
 10:30-11:00  Coffee break
 11:00-11:30  Barnaby Martin and Stefan Dantchev
             Parameterized Resolution with bounded conjunction
 11:30-12:00  Alexey Sorokin
             Lower and upper bounds for the length of joins in Lambek calculus
 12:00-12:30  Dmitry Itsykson and Vsevolod Oparin
             Graph expansion, Tseitin formulas and resolution proofs for CSP

12:30-14:30 Lunch

14:30-15:30 Lecture 3 Ryan Williams ACC Circuit Lower Bounds

Session 4 Complexity 1

 15:30-16:00  Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein
             Information lower bounds via self-reducibility
 16:00-16:30  Coffee break
 16:30-17:00  Anton Makhlin
             On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles
 17:00-17:30  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
 17:30-18:00  Vladimir Nikishkin
             Amortized communication complexity of an equality predicate

  • Thursday, 27.06

09:00-10:00 Lecture 4 Alexander Kostochka On coloring of sparse graphs

Session 5 Words and Languages

 10:00-10:30  Romeo Rizzi and Stйphane Vialette
             On recognizing words that are squares for the shuffle product
 10:30-11:00  Coffee break 
 11:00-11:30  Jozef Jirasek and Galina Jiraskova
             Cyclic Shift on Prefix-Free Languages
 11:30-12:00  Sergey Avgustinovich and Svetlana Puzynina
             Weak abelian periodicity of infinite words
 12:00-12:30  Mikhail Vyalyi
             Universality of regular realizability problems

12:30-14:00 Lunch

14:00-18:00 Excursion

19:00-21:00 Conference dinner (Vysotsky Business Centre)

  • Friday, 28.06

09:00-10:00 Lecture 5 Paul Spirakis Potential Functions in Strategic Games

Session 6 Algorithms 2

 10:00-10:30  Nicolas Boria, Cйcile Murat and Vangelis Paschos
             The Probabilistic Dominating Set problem
 10:30-11:00  Coffee break
 11:00-11:30  Marek Tesar and Jiri Fiala
             Dichotomy of the H-Quasi-cover problem
 11:30-12:00  Barnaby Martin and Florent Madelaine
             QCSP on partially reflexive cycles - the wavy line of tractability
 12:00-12:30  Abuzer Yakaryilmaz
             Quantum alternation

12:30-14:30 Lunch

14:30-15:30 Lecture 6 Gilles Dowek Real numbers, chaos, and the principle of a bounded density of information

Session 7 Complexity 2

 15:30-16:00  Timofey Stepanov 
             Random selection in few rounds
 16:00-16:30  Coffee break 
 16:30-17:00  Abuzer Yakaryilmaz
             One-counter verifiers for decidable languages
 17:00-17:30  Andreas Frцhlich, Gergely Kovбsznai and Armin Biere
             More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding
 17:30-18:00  Business meeting

  • Saturday, 29.06

09:00-10:00 Lecture 7 Thomas Colcombet Composition with algebra in the background

Session 8 Logic, Automata

 10:00-10:30  Kshitij Bansal and Stephane Demri
             Model-Checking Bounded Multi-Pushdown Systems
 10:30-11:00  Coffee break 
 11:00-11:30  Manfred Droste and Vitaly Perevoshchikov
             Multi-weighted Automata and MSO Logic
 11:30-12:00  David Janin
             Overlapping tile automata
Personal tools

CSR 2013