Schedule

From CSR 2013
(Difference between revisions)
Jump to: navigation, search
 
(2 intermediate revisions by one user not shown)
Line 6: Line 6:
 
* Monday, 24.06
 
* Monday, 24.06
  
15:00-18:00 Registration
+
15:00-18:00 Registration (Ural University, pr. Lenina, 51)
  
 
18:00-20:00 Welcome reception (University Cafeteria)
 
18:00-20:00 Welcome reception (University Cafeteria)
Line 12: Line 12:
 
* Tuesday, 25.06
 
* Tuesday, 25.06
  
08:00-09:00 Registration
+
08:00-09:00 Registration (Ural University, pr. Lenina, 51)
  
 
09:00-09:30 Welcome  
 
09:00-09:30 Welcome  
Line 37: Line 37:
 
   15:30-16:00  Amaldev Manuel, Anca Muscholl and Gabriele Puppis
 
   15:30-16:00  Amaldev Manuel, Anca Muscholl and Gabriele Puppis
 
               Walking on Data Words
 
               Walking on Data Words
   16:00-16:30  ''Coffee break''
+
 
 +
   16:00-16:30  Coffee break
 +
 
 
   16:30-17:00  Pavel Martyugin  
 
   16:30-17:00  Pavel Martyugin  
 
               Careful synchronization of partial automata with restricted alphabets
 
               Careful synchronization of partial automata with restricted alphabets
Line 55: Line 57:
 
               Exponential Lower Bounds for Refuting Random Formulas Using  
 
               Exponential Lower Bounds for Refuting Random Formulas Using  
 
               Ordered Binary Decision Diagrams
 
               Ordered Binary Decision Diagrams
   10:30-11:00 ''Coffee break''
+
 
 +
   10:30-11:00 Coffee break
 +
 
 
   11:00-11:30  Barnaby Martin and Stefan Dantchev
 
   11:00-11:30  Barnaby Martin and Stefan Dantchev
 
               Parameterized Resolution with bounded conjunction
 
               Parameterized Resolution with bounded conjunction
Line 71: Line 75:
 
   15:30-16:00  Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein
 
   15:30-16:00  Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein
 
               Information lower bounds via self-reducibility
 
               Information lower bounds via self-reducibility
   16:00-16:30  ''Coffee break''
+
 
 +
   16:00-16:30  Coffee break
 +
 
 
   16:30-17:00  Anton Makhlin
 
   16:30-17:00  Anton Makhlin
 
               On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles
 
               On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles
Line 83: Line 89:
 
* Thursday, 27.06
 
* Thursday, 27.06
  
Lecture 4  Alexander Kostochka  On coloring of sparse graphs
+
09:00-10:00 Lecture 4  Alexander Kostochka  On coloring of sparse graphs
  
 
Session 5  Words and Languages
 
Session 5  Words and Languages
 
    
 
    
   Talk 1 Romeo Rizzi and Stйphane Vialette
+
   10:00-10:30 Romeo Rizzi and Stйphane Vialette
 
               On recognizing words that are squares for the shuffle product
 
               On recognizing words that are squares for the shuffle product
   Talk 2 Jozef Jirasek and Galina Jiraskova
+
 
 +
   10:30-11:00  Coffee break
 +
 
 +
  11:00-11:30 Jozef Jirasek and Galina Jiraskova
 
               Cyclic Shift on Prefix-Free Languages
 
               Cyclic Shift on Prefix-Free Languages
   Talk 3 Sergey Avgustinovich and Svetlana Puzynina
+
   11:30-12:00 Sergey Avgustinovich and Svetlana Puzynina
 
               Weak abelian periodicity of infinite words
 
               Weak abelian periodicity of infinite words
   Talk 4 Mikhail Vyalyi
+
   12:00-12:30 Mikhail Vyalyi
 
               Universality of regular realizability problems
 
               Universality of regular realizability problems
  
Social program and conference dinner
+
12:30-14:00 Lunch
  
 +
14:00-18:00 Excursion
 +
 +
19:00-21:00 Conference dinner (Vysotsky Business Centre)
  
 
* Friday, 28.06
 
* Friday, 28.06
  
Lecture 5 Paul Spirakis  Potential Functions in Strategic Games
+
09:00-10:00 Lecture 5 Paul Spirakis  Potential Functions in Strategic Games
  
 
Session 6  Algorithms 2
 
Session 6  Algorithms 2
 
    
 
    
   Talk 1 Nicolas Boria, Cйcile Murat and Vangelis Paschos
+
   10:00-10:30 Nicolas Boria, Cйcile Murat and Vangelis Paschos
 
               The Probabilistic Dominating Set problem
 
               The Probabilistic Dominating Set problem
   Talk 2 Marek Tesar and Jiri Fiala
+
 
 +
   10:30-11:00  Coffee break
 +
 
 +
  11:00-11:30 Marek Tesar and Jiri Fiala
 
               Dichotomy of the H-Quasi-cover problem
 
               Dichotomy of the H-Quasi-cover problem
   Talk 3 Barnaby Martin and Florent Madelaine
+
   11:30-12:00 Barnaby Martin and Florent Madelaine
 
               QCSP on partially reflexive cycles - the wavy line of tractability
 
               QCSP on partially reflexive cycles - the wavy line of tractability
   Talk 4 Abuzer Yakaryilmaz
+
   12:00-12:30 Abuzer Yakaryilmaz
 
               Quantum alternation
 
               Quantum alternation
  
Lecture 6  Gilles Dowek  Real numbers, chaos, and the principle of a bounded density of information
+
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
 
Session 7 Complexity 2
 
    
 
    
   Talk 1 Timofey Stepanov  
+
   15:30-16:00 Timofey Stepanov  
 
               Random selection in few rounds
 
               Random selection in few rounds
   Talk 2 Abuzer Yakaryilmaz
+
 
 +
   16:00-16:30  Coffee break
 +
 
 +
  16:30-17:00 Abuzer Yakaryilmaz
 
               One-counter verifiers for decidable languages
 
               One-counter verifiers for decidable languages
   Talk 3 Andreas Frцhlich, Gergely Kovбsznai and Armin Biere
+
   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
 
               More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding
   Business meeting
+
   17:30-18:00  Business meeting
  
  
 
* Saturday, 29.06
 
* Saturday, 29.06
  
Lecture 7  Thomas Colcombet  Composition with algebra in the background
+
09:00-10:00 Lecture 7  Thomas Colcombet  Composition with algebra in the background
  
 
Session 8  Logic, Automata
 
Session 8  Logic, Automata
 
    
 
    
   Talk 1 Kshitij Bansal and Stephane Demri
+
   10:00-10:30 Kshitij Bansal and Stephane Demri
 
               Model-Checking Bounded Multi-Pushdown Systems
 
               Model-Checking Bounded Multi-Pushdown Systems
   Talk 2 Manfred Droste and Vitaly Perevoshchikov
+
 
 +
   10:30-11:00  Coffee break
 +
 
 +
  11:00-11:30 Manfred Droste and Vitaly Perevoshchikov
 
               Multi-weighted Automata and MSO Logic
 
               Multi-weighted Automata and MSO Logic
   Talk 3 David Janin
+
   11:30-12:00 David Janin
 
               Overlapping tile automata
 
               Overlapping tile automata

Latest revision as of 17:35, 18 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 (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
Namespaces

Variants
Actions
CSR 2013
Navigation
Toolbox