Program

All the workshops will be held in Steklov Institute of Mathematics, while the conference will be held in Academic University.

Sunday, June 12
09:00–18:00Workshops (Steklov Institute)
Monday, June 13
09:00–16:00Workshops (Steklov Institute)
18:00–20:00Welcoming reception (local beer, snacks). Registration (Academic University)
Tuesday, June 14
08:30–09:30Registration
09:30–10:30 OPENING LECTURE: Dima Grigoriev. Complexity lower bounds for algebraic computation trees
10:30–11:00Coffee break
11:00–11:30 Scott Aaronson. The Equivalence of Sampling and Searching
11:30–12:00 Benjamin Doerr and Carola Winzen. Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity
12:00–12:30 Arkadev Chattopadhyay, Ricard Gavalda, Kristoffer Arnsfelt Hansen and Denis Therien. Learning Read-constant Polynomials of Constant Degree modulo Composites
12:30–14:00Lunch
14:00–15:00 INVITED TALK: Manindra Agrawal. The Arithmetic Complexity of Euler Function
15:00–15:15Coffee break
15:15–15:45 Andrei Romashchenko. Pseudo-random graphs and bit probe schemes with one-sided error
15:45–16:15 Daniil Musatov. Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via ``Naive'' Derandomization
16:15–16:30Coffee break
16:30–17:00 Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen and Peter Bro Miltersen. The complexity of solving reachability games using value and strategy iteration
17:00–17:30 Alexey Pospelov. Faster Polynomial Multiplication via Discrete Fourier Transforms
Wednesday, June 15
09:30–10:30 INVITED TALK: Alexander Shen. Kolmogorov Complexity as a Language
10:30–11:00Coffee break
11:00–11:30 Jiri Sima and Stanislav Zak. Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
11:30–12:00 Dmitry Itsykson and Dmitry Sokolov. The complexity of inversion of explicit Goldreich's function by DPLL algorithms
12:00–12:30 Alex Davydow and Sergey Nikolenko. Gate elimination for linear functions and new feebly secure constructions
12:30–14:00Lunch
14:00–19:00SOCIAL PROGRAM
Thursday, June 16
09:30–10:30INVITED TALK: Laszlo Babai. Finite Groups and Complexity Theory: from Leningrad to Saint Petersburg via Las Vegas
10:30–11:00Coffee break
11:00–11:30 Catarina Carvalho, Laszlo Egri, Marcel Jackson and Todd Niven. On Maltsev Digraphs
11:30–12:00 Loukas Georgiadis, Stavros Nikolopoulos and Leonidas Palios. Join-Reachability Problems in Directed Graphs
12:00–12:30 Fabian Wagner. Graphs of Bounded Treewidth can be Canonized in AC^1
12:30–14:00Lunch
14:00–15:00 INVITED TALK: Jarkko Kari. Snakes and Cellular Automata: Reductions and Inseparability Results
15:00–15:15Coffee break
15:15–15:45 Pinar Heggernes, Daniel Meister and Udi Rotics. Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
15:45–16:15 Klaus Meer. An extended tree-width notion for directed graphs related to the computation of permanents
16:15–16:30Coffee break
16:30–17:00 Petr Golovach, Daniel Paulusma and Jian Song. Computing vertex-surjective homomorphisms to partially reflexive trees
17:00–17:30 Markus Lohrey and Christian Mathissen. Compressed Membership in Automata with Compressed Labels
17:30–18:10BUSINESS MEETING
Friday, June 17
09:30–10:30 INVITED TALK: Sergey Yekhanin. Locally decodable codes
10:30–11:00Coffee break
11:00–11:30 Violetta Lonati, Dino Mandrioli and Matteo Pradella. Precedence Automata and Languages
11:30–12:00 Sergey Tarasov and Mikhail Vyalyi. Orbits of linear maps and regular languages
12:00–12:30 Remi Morin. Shared-Memory Systems and Charts
12:30–14:00Lunch
14:00–15:00 INVITED TALK: Andrei Bulatov. On the CSP Dichotomy conjecture
15:00–15:15Coffee break
15:15–15:45 Tamar Aizikowitz and Michael Kaminski. LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata
15:45–16:15Christos Kapoutsis. Two-Way Automata versus Logarithmic Space
16:15–16:30Coffee break
16:30–17:00 Guillaume Blin, Romeo Rizzi and Stephane Vialette. A Polynomial-Time Algorithm for Finding Minimal Conflicting Sets
17:00–17:30 Konstantin Likhomanov and Arseny Shur. Two Combinatorial Criteria for BWT Images
19:00–22:00CONFERENCE DINNER
Saturday, June 18
09:30–10:30 INVITED TALK: Amir Shpilka. Recent Results on Polynomial Identity Testing
10:30–11:00Coffee break
11:00–11:30 Alexander Tiskin. Towards approximate matching in compressed strings: Local subsequence recognition
11:30–12:00 Eric Remila. The Optimal Strategy for the Average Long-Lived Consensus
12:00–12:30 Kim Thang Nguyen. Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs
12:30–14:00Lunch
14:00–15:00 INVITED TALK: Madhu Sudan. The method of multiplicities
15:00–15:15Coffee break
15:15–15:45 Matthijs Bomhoff. Recognizing Sparse Perfect Elimination Bipartite Graphs
15:45–16:15 Arnon Avron and Ori Lahav. A Multiple-Conclusion Calculus for First-Order Godel Logic