Program

Wednesday, June 7, 2017 – Workshop Computation and cryptography with qu-bits

16.30 – registration for the CSR, welcome party

Thursday, June 8, 2017 – CSR Day 1

9.00 – 11.00 – registration for the CSR and Welcome coffee

11.00 – opening

11.30 – 12.30 – INVITED TALK: Verification of Quantum Computation and the Price of Trust, Elham Kashefi

12.30 – 15.00 – Lunch

15.00 – 16.45 – Session I

15.00 – 15.30 – Cascade Heap: Towards Time-Optimal Extractions, Maxim Babenko, Ignat Kolesnichenko, and Ivan Smirnov

15.35 – 16.05 – Dynamic Stabbing Queries with Sub-logarithmic Local Updates for Overlapping Intervals, Elena Khramtcova* and Maarten Löffler

16.10 – 16.40 – Popularity in the Generalized Hospital Residents Setting, Meghana Nasre and Amit Rawat*

Friday, June 9, 2017 – CSR Day 2

9.30 – 10.30 – INVITED TALK: Concatenation Hierarchies: New Bottle, Old Wine, Marc Zeitoun

10.30 – 11.30 – coffee break

11.30 – 13.15 – Session II

11.30 – 12.00 – Green’s Relations in Finite Transformation Semigroups, Lukas Fleischer* and Manfred Kufleitner

12.05 – 12.35 – The Transformation Monoid of a Partially Lossy Queue, Chris Köcher* and Dietrich Kuske


12.40 – 13.10 – The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0, Alexei Miasnikov, Svetla Vassileva, and Armin Weiß*


13.15 – 15.00 – Lunch

15.00 – 16.10 – Session III

15.00 – 15.30 – On a Generalization of Horn Constraint Systems, Piotr Wojciechowski, R. Chandrasekaran, and K. Subramani

15.35 – 16.05 – Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams, Kamil Khadiev* and Aliya Khadieva

16.10 – 17.00 – coffee break

17.00 – city tour

Saturday, June 10, 2017 – CSR Day 3

9.30 – 10.30 – INVITED TALK: Can We Locally Compute Sparse Connected Subgraphs?, Ronitt Rubinfeld

10.30 – 11.00 – coffee break

11.00 – 12.45 – Session IV

11.00 – 11.30 – Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets, Olivier Bodini, Matthieu Dien*, Antoine Genitrini, and Frédéric Peschanski

11.35 – 12.05 – Parameterized Counting of Trees, Forests and Matroid Bases, Cornelius Brand* and Marc Roth

12.10 – 12.40 – Dag-Like Communication and Its Applications, Dmitry Sokolov

12.45 – 14.45 – Lunch

14.45 – 15.45– INVITED TALK: Graph Sketching and Streaming: New Approaches for Analyzing
 Massive Graphs, Andrew McGregor

15.45 – 16.55 – Session V

15.45 – 16.15 – Unary Coded PSPACE-Complete Languages in ASPACE(loglog n), Viliam Geffert

16.20 – 16.50 – On Algorithmic Statistics for Space-Bounded Algorithms, Alexey Milovanov

17.00 – CSR Steering Committee work meeting

Sunday, June 11, 2017 – CSR Day 4

9.30 – 10.30 – INVITED TALK: Advances in Parameterized Verification of Population Protocols, Javier Esparza

10.30 – 11.30 – coffee break

11.30 – 12.40 – Session VI

11.30 – 12.00 – Palindromic Decompositions with Gaps and Errors, Michał Adamczyk, Mai Alzamel, Panagiotis Charalampopoulos*, Costas S. Iliopoulos, and Jakub Radoszewski

12.05 – 12.35 – Edit Distance Neighbourhoods of Input-Driven Pushdown Automata, Alexander Okhotin and Kai Salomaa

12.40 – 14.40 – Lunch

14.40 – 16.25 – Session VII

14.40 – 15.10 – Approximation Algorithms for the Maximum Carpool Matching Problem, Gilad Kutiel

15.15 – 15.45 – The (Minimum) Rank of Typical Fooling-Set Matrices, Mozhgan Pourmoradnasseri* and Dirk Oliver Theis

15.50 – 16.20 – On Probabilistic Algorithm for Solving Almost All Instances of the Set Partition Problem, Alexandr V. Seliverstov

18.30 – conference dinner

Monday, June 12, 2017 – CSR, Day 5

10.00 – 11.10 – Sessions VIII

10.00 – 10.30 – Generalized Dyck Shifts, Marie-Pierre Béal and Pavel Heller*

10.35 – 11.05 – Turing Degree Spectra of Minimal Subshifts, Michael Hochman and Pascal Vanier*

11.10 – 11.40 – coffee break

11.40 – 12.50 – Session IX

11.40 – 12.10 – The Descriptive Complexity of Subgraph Isomorphism Without Numerics, Oleg Verbitsky and Maksim Zhukovskii*

12.15 – 12.45 – Nondeterministic Unitary OBDDs, Aida Gainutdinova* and Abuzer Yakaryılmaz