Schedule
(Created page with "'''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 Openi...") |
|||
(9 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
'''Schedule of CSR 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. | 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 | + | * 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 | Session 1 Algorithms | ||
− | + | 11:00-11:30 Klaus Jansen and Stefan Kraft | |
An Improved Knapsack Solver for Column Generation | An Improved Knapsack Solver for Column Generation | ||
− | + | 11:30-12:00 Volker Diekert and Armin Weiss | |
QuickHeapsort: Modifications and improved analysis | QuickHeapsort: Modifications and improved analysis | ||
− | + | 12:00-12:30 Pawel Gawrychowski | |
Alphabetic minimax trees in linear time | Alphabetic minimax trees in linear time | ||
− | Lecture 1 | + | 12:30-14:30 Lunch |
+ | |||
+ | 14:30-15:30 Lecture 1 Jeffrey Shallit Decidability and Enumeration for Automatic Sequences: A Survey | ||
Session 2 Automata | 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 | 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 | 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 | Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height | ||
− | |||
− | Lecture 2 Nicole Schweikardt | + | * 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 | Session 3 Logic, Proof Complexity | ||
− | + | 10:00-10:30 Luke Friedman and Yixin Xu | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
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 | ||
+ | |||
+ | 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 | Graph expansion, Tseitin formulas and resolution proofs for CSP | ||
+ | 12:30-14:30 Lunch | ||
− | Lecture 3 Ryan Williams | + | 14:30-15:30 Lecture 3 Ryan Williams ACC Circuit Lower Bounds |
Session 4 Complexity 1 | Session 4 Complexity 1 | ||
− | + | 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 | ||
− | + | ||
− | 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'' | + | 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 | Amortized communication complexity of an equality predicate | ||
− | |||
− | Lecture 4 | + | * Thursday, 27.06 |
− | + | ||
+ | 09:00-10:00 Lecture 4 Alexander Kostochka On coloring of sparse graphs | ||
Session 5 Words and Languages | 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 | 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 | Cyclic Shift on Prefix-Free Languages | ||
− | + | 11:30-12:00 Sergey Avgustinovich and Svetlana Puzynina | |
Weak abelian periodicity of infinite words | Weak abelian periodicity of infinite words | ||
− | + | 12:00-12:30 Mikhail Vyalyi | |
Universality of regular realizability problems | Universality of regular realizability problems | ||
− | + | 12:30-14:00 Lunch | |
− | + | 14:00-18:00 Excursion | |
− | Lecture 5 Paul Spirakis Potential Functions in Strategic Games | + | 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 | Session 6 Algorithms 2 | ||
− | + | 10:00-10:30 Nicolas Boria, Cйcile Murat and Vangelis Paschos | |
The Probabilistic Dominating Set problem | 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 | 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 | QCSP on partially reflexive cycles - the wavy line of tractability | ||
− | + | 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 | ||
− | + | 15:30-16:00 Timofey Stepanov | |
Random selection in few rounds | Random selection in few rounds | ||
− | + | ||
+ | 16:00-16:30 Coffee break | ||
+ | |||
+ | 16:30-17:00 Abuzer Yakaryilmaz | ||
One-counter verifiers for decidable languages | 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 | More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding | ||
− | Business meeting | + | 17:30-18:00 Business meeting |
− | |||
− | Lecture 7 Thomas Colcombet Composition with algebra in the background | + | * Saturday, 29.06 |
+ | |||
+ | 09:00-10:00 Lecture 7 Thomas Colcombet Composition with algebra in the background | ||
Session 8 Logic, Automata | Session 8 Logic, Automata | ||
− | + | 10:00-10:30 Kshitij Bansal and Stephane Demri | |
Model-Checking Bounded Multi-Pushdown Systems | 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 | Multi-weighted Automata and MSO Logic | ||
− | + | 11:30-12:00 David Janin | |
− | + | 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