Schedule
Line 15: | Line 15: | ||
Talk 1 Klaus Jansen and Stefan Kraft | Talk 1 Klaus Jansen and Stefan Kraft | ||
An Improved Knapsack Solver for Column Generation | An Improved Knapsack Solver for Column Generation | ||
− | Talk 2 | + | Talk 2 Volker Diekert and Armin Weiss |
QuickHeapsort: Modifications and improved analysis | QuickHeapsort: Modifications and improved analysis | ||
Talk 3 Pawel Gawrychowski | Talk 3 Pawel Gawrychowski | ||
Alphabetic minimax trees in linear time | Alphabetic minimax trees in linear time | ||
− | Lecture 1 | + | Lecture 1 Jeffrey Shallit Decidability and Enumeration for Automatic Sequences: A Survey |
Session 2 Automata | Session 2 Automata | ||
− | Talk 1 | + | Talk 1 Amaldev Manuel, Anca Muscholl and Gabriele Puppis |
− | + | Walking on Data Words | |
Talk 2 Pavel Martyugin | Talk 2 Pavel Martyugin | ||
Careful synchronization of partial automata with restricted alphabets | Careful synchronization of partial automata with restricted alphabets | ||
Line 40: | Line 40: | ||
Session 3 Logic, Proof Complexity | Session 3 Logic, Proof Complexity | ||
− | Talk 1 | + | Talk 1 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 | ||
+ | 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 | Talk 4 Dmitry Itsykson and Vsevolod Oparin | ||
Graph expansion, Tseitin formulas and resolution proofs for CSP | Graph expansion, Tseitin formulas and resolution proofs for CSP | ||
− | Lecture 3 Ryan Williams | + | Lecture 3 Ryan Williams ACC Circuit Lower Bounds |
Session 4 Complexity 1 | Session 4 Complexity 1 | ||
− | Talk 1 | + | Talk 1 Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein |
− | + | ||
− | + | ||
Information lower bounds via self-reducibility | Information lower bounds via self-reducibility | ||
+ | Talk 2 Anton Makhlin | ||
+ | On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles | ||
Talk 3 Nikolay Vereshchagin | Talk 3 Nikolay Vereshchagin | ||
An improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP Languages are Hard on the Worst-Case, | An improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP Languages are Hard on the Worst-Case, | ||
Line 68: | Line 68: | ||
* Thursday, 27.06 | * Thursday, 27.06 | ||
− | Lecture 4 | + | Lecture 4 Alexander Kostochka On coloring of sparse graphs |
Session 5 Words and Languages | Session 5 Words and Languages | ||
Line 122: | Line 122: | ||
Talk 2 Manfred Droste and Vitaly Perevoshchikov | Talk 2 Manfred Droste and Vitaly Perevoshchikov | ||
Multi-weighted Automata and MSO Logic | Multi-weighted Automata and MSO Logic | ||
− | Talk 3 | + | Talk 3 David Janin |
− | + | Overlapping tile automata |
Revision as of 12:33, 14 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 Volker Diekert and Armin Weiss QuickHeapsort: Modifications and improved analysis Talk 3 Pawel Gawrychowski Alphabetic minimax trees in linear time
Lecture 1 Jeffrey Shallit Decidability and Enumeration for Automatic Sequences: A Survey
Session 2 Automata
Talk 1 Amaldev Manuel, Anca Muscholl and Gabriele Puppis Walking on Data Words 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 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