(panoramic photo of Moscow from moscow.photobase.ru)
CCR Logo        

Eighth International Conference on Computability, Complexity and Randomness (CCR 2013)

September 23–27, 2013, Moscow, Russia


Conference program

Talks will be held at Moscow Center for Continuous Mathematical Education (Bolshoj Vlasjevskij 11, Conference hall, 4th floor). The timing includes 15-minute questions+break time after each talk

Monday, Sept. 23

09.00–10.00      registration, opening
10.00–11.00     Laurent BIENVENU (invited talk) Probabilistic algorithms in computability theory Slides, PDF
11.00–11.40      Jason TEUTSCH (by Skype), Frank STEPHAN Things that can be made into themselves Slides, PDF
COFFEE BREAK
12.00–12.40     Ludovic PATEY Classifying principles by the no randomized algorithm property
12.40–13.20     Satyadev NANDAKUMAR, Santosh VANGEPALI Normality and finite-state dimension of Liouiville numbers. Slides, PDF
13.20–14.00     Andrey FROLOV $\Delta^0_2$-spectra of linear orderings
14.00–15.00     LUNCH (MCCME canteen)
15.00–16.00     Yue YANG (invited talk) Nonstandard models of arithmetic and Ramsey theorem Slides, PDF
16.00–16.40     Benoit MONIN Continuous higher randomness Slides, PDF

Tuesday, Sept. 24

10.00–11.00     Sergey YEKHANIN (invited talk) Locally decodable codes: from computational complexity to cloud computing Slides, PDF
11.00–11.40     Sergei KONYAGIN Deterministic root finding in fields of prime order
COFFEE BREAK
12.00–12.40     Alexander KNOP Circuit lower bounds for Heuristic MA
12.40–13.20     Svetlana SELEZNEVA, Anton BUKHMAN Polynomial time algorithms for checking some properties of Boolean functions
13.20–14.00     Kristoffer Arnsfelt HANSEN, Vladimir PODOLSKII Polynomial threshold functions over $\{1,2\}$, and threshold circuits Slides, PDF
14.00–15.00     LUNCH (MCCME canteen)
15.00–16.00     Eduard HIRSCH (invited talk) Distributional proving problems, and beyond Slides, PDF
16.00–16.40     Anton MAKHLIN On the encoding invariance of polynomial time computable distribution ensembles
16.40–17.20     Mikhail DEKTYAREV Garden-hose complexity and communication/circuit complexity Slides, PDF
19.00 Conference dinner

Wednesday, Sept. 25

10.00–11.00     Mikhael Yampolsky (invited talk) Boundary values of conformal maps: computable Caratheodory theory, computability of the harmonic measure, and applications to dynamics
11.00–11.40     Bruno BAUWENS, Anton MAKHLIN, Nikolay VERESHCHAGIN, Marius ZIMAND Short lists with short program in short time
COFFEE BREAK
12.00–12.40     Marius ZIMAND Some remarks on `short lists with short programs' problem Slides, PDF
12.40–13.20     Daniyar CHUMBALOV Combinatorial version of the Slepian–Wolf coding theorem for binary strings Slides, PDF
13.20–14.00     Daniil Musatov Muchnik theorem with bounded resources and several conditions
14.00–15.00     LUNCH (MCCME canteen)
15.00–16.00     Emmanuel JEANDEL (invited talk) Smart Turing machines are slow Slides, PDF
16.00– SOCIAL PROGRAM

Thursday, Sept. 26

10.00-10.40     Sanjay JAIN, Frank STEPHAN, Jason TEUTSCH Closed r.e. sets – recent progress. Slides, PDF Full text, Postscript
10.50–11.30     Kenshi MIYABE Almost uniform weak randomness Slides, PDF
COFFEE BREAK
12.00–12.40     Mikhail RASKIN Computable measures that are couplable but not computably couplable Slides, PDF
12.40–13.20     Hayato TAKAHASHI Generalization of van Lambalgen's theorem and blind randomness for conditional probability Slides, PDF
13.20–14.00     Bruno BAUWENS Asymmetry of the Kolmogorov complexity of on-line predicting odd and even bits Slides, PDF
14.00–15.00     LUNCH (MCCME canteen)
15.00–16.00     Alexander SHEN (invited talk) Quantitative randomness
16.00–16.40     Vladimir VYUGIN On stability properties of probability laws with respect to small violations of randomness. Slides, PDF
16.40–17.20     Business meeting

Friday, Sept. 27

10.00–11.00     George BARMPALIAS (invited talk) From randomness to segregation Slides, PDF
11.00–11.40     Kohtaro TADAKI Cryptography and algorithmic randomness, II Slides, PDF
COFFEE BREAK
12.00–13.20      Akim KUMOK, Mikhail ANDREEV Weak and strong effectively $\alpha$-null sets Slides, PDF
13.20–14.00     Arsenij Savin, Nikolay Vereshchagin Total and plain conditional complexities.
14.00–15.00     LUNCH (MCCME canteen)


Contacts
For questions, in particular about scientific aspects of the meeting, please contact the chairs of the programme committee

Inquiries about organizational matters such as registration or accommodation are best addressed directly to the staff at the ccr2013@mccme.ru

Copyright Notice
The layout of the webpage has been adapted from the style of the CCA conference series and is used by courtesy of Vasco Brattka.