Preliminary program of CSR'12

Sunday, July 1

09:00–18:00

Workshop (PSSV 2012)

Monday, July 2

09:00–16:00

Workshops (PSSV 2012, CTCrypt 2012)

Tuesday, July 3

08:30–09:15	Registration
09:15–09:30	WELCOMING AND OPENING SPEECH: Roman Strongin, President of N.I. Lobachevsky State University of Nizhni Novgorod
09:30–10:30	OPENING LECTURE: Vijay Vazirani. Can the Theory of Algorithms Ratify the "Invisible Hand of the Market?"
10:30–11:00	Coffee break
11:00–11:30	Nachshon Cohen and Zeev Nutov. Approximating minimum power edge-multi-covers
11:30–12:00	Romeo Rizzi and Florian Sikora. Some results on more flexible versions of Graph Motif
12:00–12:30	Sebastian Bauer, Uli Fahrenberg, Axel Legay and Claus Thrane. General Quantitative Specification Theories with Modalities
12:30–14:00	Lunch
14:00–15:00	TURING LECTURE connected to THE ALAN TURING YEAR 2012: Yuri Matiyasevich. Alan Turing and Number Theory
15:00–15:15	Coffee break
15:15–15:45	Pinar Heggernes and Sigve Hortemo Sæther. Broadcast Domination on block graphs in linear time
15:45–16:15	Martin Dietzfelbinger and Michael Rink. Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs
16:15–16:30	Coffee break
16:30–17:00	Bernhard Heinemann. Characterizing Certain Topological Specifications
17:00–17:30	Eli Fox-Epstein and Danny Krizanc. The Complexity of Minor-Ancestral Graph Properties with Forbidden Pairs

Wednesday, July 4

09:30–10:30	INVITED TALK: Lev Beklemishev. DKAL: A Distributed Knowledge Authorization Language and Its Logic of Information
10:30–11:00	Coffee break
11:00–11:30	Timo Jolivet and Jarkko Kari. Consistency of multidimensional combinatorial substitutions
11:30–12:00	Hans Simon. Boolean Composition of Visual Secret Sharing Schemes
12:00–12:30	Petr Golovach, Bernard Lidicky, Barnaby Martin and Daniel Paulusma. Finding vertex-surjective graph homomorphisms
12:30–14:00	Lunch
14:00–19:00	SOCIAL PROGRAM

Thursday, July 5

09:30–10:30	INVITED TALK: Mikołaj Bojańczyk. Infinite Sets That Are Finite Up to Permutations
10:30–11:00	Coffee break
11:00–11:30	Prateek Karandikar and Philippe Schnoebelen. Cutting Through Regular Post Embedding Problems
11:30–12:00	Dennis Komm, Tobias Moemke and Richard Kralovic. On the Advice Complexity of the Set Cover Problem
12:00–12:30	Amr Elmasry and Jyrki Katajainen. Worst-Case Optimal Priority Queues via Extended Regular Counters
12:30–14:00	Lunch
14:00–15:00	INVITED TALK: Julien Cassaigne. Dynamics of Rauzy Graphs for Low-Complexity Words
15:00–15:15	Coffee break
15:15–15:45	Andreas Goerdt and Lutz Falke. Satisfiability thresholds beyond $k-$XORSAT
15:45–16:15	Barnaby Martin, Florent Madelaine and Juraj Stacho. Constraint Satisfaction with Counting Quantifiers
16:15–16:30	Coffee break
16:30–17:00	Christos Kapoutsis and Giovanni Pighizzini. Two-way automata characterizations of L/poly versus NL
17:00–17:30	Stefan Dobrev, Evangelos Kranakis, Oscar Morales Ponce and Milan Plvzik. Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs
17:30–18:10	BUSINESS MEETING

Friday, July 6

09:30–10:30	INVITED TALK: Piotr Indyk. Faster Algorithms for Sparse Fourier Transform
10:30–11:00	Coffee break
11:00–11:30	Maxim Babenko and Ivan Pouzyrevsky. Resilient Quicksort and Selection
11:30–12:00	Evgeny Demenkov. A Lower Bound on Circuit Complexity of Vector Function in $U_2$
12:00–12:30	Evgeny Demenkov, Alexander Kulikov, Ivan Mihajlin and Hiroki Morizumi. Computing all MOD-functions simultaneously
12:30–14:00	Lunch
14:00–15:00	INVITED TALK: Jaroslav Nesetril. Algorithms, Dichotomy and Statistics for Geometric and Sparse Graphs
15:00–15:15	Coffee break
15:15–15:45	Svetlana Selezneva. Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
15:45–16:15	Ville Salo. A Characterization of Cellular Automata Generated by Idempotents on the Full Shift
16:15–16:30	Coffee break
16:30–17:00	Dmitry Chistikov. Checking Tests for Read-Once Functions over Arbitrary Bases
17:00–17:30	Volker Diekert and Manfred Kufleitner. Bounded synchronization delay in omega-rational expressions for star-free infinitary languages
19:00–22:00	CONFERENCE DINNER

Saturday, July 7

09:30–10:30	INVITED TALK: Max Alekseyev. Challenges in Comparative Genomics: from Biological Problems to Combinatorial Algorithms (and back)
10:30–11:00	Coffee break
11:00–11:30	Daniil Musatov. Resource-Bounded Kolmogorov Extractors
11:30–12:00	Michael Blondin and Pierre Mckenzie. The Complexity of Intersecting Finite Automata Having Few Final States
12:00–12:30	Galina Jiraskova. Optimal Simulation of AFAs by NFAs and Operations on AFA and BFA Languages
12:30–14:00	Lunch
14:00–14:30	Bartlomiej Bosek, Stefan Felsner, Kolja Knauer and Grzegorz Matecki. News about Semiantichains and Unichain Coverings