The 7th International Computer Science Symposium in Russia
    Proceedings 
    News 
    Call For Papers 
    Conference 
    Important Dates 
    Topics 
    Program 
    Workshops 
    Invited Speakers 
    Committees 
    Venue 
    Travel information 
    Registration 
    Archive 
    Contacts 
    Subscription 
EATCS
Springer Link
Yandex
Microsoft Research

 
The 7th International Computer Science Symposium in Russia
Program

Preliminary program of CSR'12

Sunday, July 1
09:00–18:00Workshop (PSSV 2012)

Monday, July 2
09:00–16:00Workshops (PSSV 2012, CTCrypt 2012)


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

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

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

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

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