** January, 5: ** American Mathematical Society annual meeting in
Washington: presentation of the talk on aperiodic tiling and
fixed point construction (Bruno Durand, Andrei Romashchenko,
Alexader Shen; delivered by Alexander Shen) at the special
session organized by Steve Simpson

** January, 9: **
Talk at IBM Research center (White Plains) on the research on
tilings (Alexander Shen)

** January, 20: **
Talk at Penn State University Logic seminar (organized by Steve
Simpson) on tilings and computablity (Alexander Shen)

** January, 22: **
Talk at Penn State University colloqium on algorithmic
randomness and foundations of probability (Alexander Shen,
invited by Sergei Tabachnikov)

** January, 26: **
Talk at Microsoft Research center (Boston) on the research on
tilings (Alexander Shen)

** January: **
Nikolai Vereshchagin and Vladmir Podolsky (Moscow State
University, Poncelet laboratory) visit to LIF Marseille. Work
on Amman tilings.

Work with Bruno Durand on Ammann tilings. Any tiling of a half-plane
can be retrieved from its imprint on the border of the half-plane.
In contrast, the information in the half of the imprint is not enough
to recover the tiling.

** January, 30: **
The paper "Variations on Muchnik's Conditional Complexity
Theorem" by Daniil Musatov, Andrei Romashchenko and Alexander
Shen accepted at CSR 2009.

** January, 30: **
NAFIT organizational meeting (Paris): Gregory Lafitte,
Alexander Shen

** February, 19: **
Laurent Bienvenu's talk at LIF

** February: **
Bruno Durand, Andrei Romashchenko, Alexander Shen,
Fixed point theorem and aperiodic tilings,

Bulletin of the EATCS, no. 97, pp. 126-136
(The Logic in Computer Science Column by Yuri Gurevich)

pdf

** March 4—6: **
FRAC meeting in Paris.

Michael Weiss and Gregory Lafitte:
Pavages et universalite.

Alexander Shen: Decomposition
complexity and possible applications to finite automata.

** March, 16: **
Decomposition complexity (talk at Dobrushin laboratory,
Moscow, IITP RAS), Alexander Shen

** March 17: **
* Limit complexities revisited * paper (Laurent Bienvenu,
Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin) appeared
in * Theory of Computing Systems * DOI
10.1007/s00224-009-9203-9

** March, 28—29; April, 04—05: **
Tutorial on expanders. Lectures by Andrei Romashchenko (20 hours)
(St. Petersburn Computer Science club, PDMI RAS)

** April, 5: **
The paper "High Complexity Tilings with Sparse Errors"
by Bruno Durand, Alexander Shen and Andrei Romashchenko accepted
at ICALP 2009.

** May 19, Changsha (China) **
TAMC 09: Theory and Applications of Models of Computation,

talk by Gregory Lafitte and Michael Weiss, "An Almost Totally
Universal Tile Set", Lecture Notes in Computer Science, v.5332,
p.271-280.

** May, 27—31, Madison (Wisconsin): ** FRG Workshop *
Algorithmic Randomness * (organized by Joseph Miller and
Steffen Lempp). Talk: Muchnik's game interpretation of
Kolmogorov complexity (Alexander Shen)

** June 8: **
The paper "Stability of Kolmogorov complexity properties under
relativization" by Andrei Muchnik and Andrei Romashchenko
submitted (at last) to * Problems of information
transmission. *

** June 12: **
RFBR and CNRS have approved our proposal for the
French—Russian workshop on algorithm theory and application.
This 3-days seminar is supposed to be organized in Moscow
(lab. Poncelet) in June 2010. French side coordinator: Thomas
Fernique; Russian side coordinator: Nikolai Vereshchagin, with
some help of Andrei Romashchenko.

** June 14: **
Paper ``Algorithmic information theory and martingales''
(Laurent Bienvenu, Alexander Shen) submitted to
arxiv:0906.2614. A historical account of algorithmic
information theory and its predecessor with special attention
to martingales. (The idea of such a paper was suggested by
Glenn Shafer.)

** June 2009:**
More historical version of this paper (coauthored with Glenn Shafer):

"On the history of martingales in the study of randomness",

Electronic Journ@l for History of Probability and Statistics,
Vol.5, no.1, Juin 2009,

text

LIX colloquium "Reachability problems'09". See also arxiv:0906.4411 preprint. text (pdf)

slides (pdf)

** June 21 — June 28: **
Visit of Joe Miller (Madison, Wisconsin), Laurent Bienvenu (Heidelberg)
Tutorial: K-trivial sequences,
LR- and LK-reductions. Discussion topic: constructive versions of
Kolmogorov 0-1-law and ergodic-type characterizations of randomness

** July 6 — 7: **
Visit of Adam Day (New Zealand)

A tutorial on the lower bound for the difference between
monotone and a priori complexity.

** July 6 — 9: **
Visit of Alexey Chernov (Royal Holloway, UK)

Gacs' proof on monotone complexity. Neutral measure and
universal prediction

** June 26 — July 29: **
Visit of Nikolay Vereshchagin
(Moscow, Poncelet Laboratory and Moscow State University)
Work on Kolmogorov complexity.

Participation in the CIRM conference (below),

Participation in
IEEE Conference on Computational Complexity 2009

Invited speaker at the conference
Computability in Europe 2009

extended abstract (pdf)

** June 13 — August 4: **
Visit of Pavel Karpovich
(Moscow, Poncelet Laboratory and Moscow State University)

Participation in 4th Conference on Logic, Complexity and Randomness
(see below)

Work on the lower and upper bounds for monotone and decision
complexity of tuples. Shown that monotone complexity of a pair
can exceed the sum of lengths while the decision complexity of a
triple does not exceed the sum of lengths.

draft

** June 26 — August 9: **
Visit of Vladimir Podolsky
(Moscow, Poncelet Laboratory and Moscow State University)

Participation in
IEEE Conference on Computational Complexity 2009

Lower bounds for weights of perceptrons were studied, A paper "A Uniform Lower
Bound on Weights of Perceptrons" prepared for journal publication.

draft (Russian)

International 4th Conference on Logic, Complexity and Randomness,

June 29 — July 3, 2009, organized by Bruno Durand, Laurent Bienvenu,
and Alexander Shen,
supported
by NAFIT.

Meeting of NAFIT participants
A.Rumyantsev, P.Karpovich, V.Vyugin, N.Vereshchagin
(Poncelet laboratory
and Kolmogorov seminar, Moscow)
G.Lafitte, B.Durand, A.Romashchenko, A.Shen (LIF)

** July 5 — 12: **
ICALP 2009 : 36th International Colloquium on Automata, Languages
and Programming, July 5-12, Rodos, Greece

Talk by Bruno Durand (see above)

** August 5: **
Paper on monotone complexity and decision complexity (P.Karpovich)
prepared while visiting LIF is finished
(to be submitted to arxiv):

pdf

** August 18 — 23: **
4th International Computer Science Symposium in Russia

Invited talk by N.K.Vereshchagin:
Kolmogorov Complexity and Model Selection

Talk by D.Musatov/A.Romashchenko/A.Shen, see above

** September 23 — 25: **
RP-09: Reachability problems (Ecole Polytechnique)

Invited talk by A.Shen
Algorithmic Information Theory and Foundations of Probability

** October 13: **
hal-00424024, arxiv:0910.2415
Bruno Durand, Andrei Romashchenko, Alexander Shen:
A long exposition of different applications of fixed-point tile set
constructions (aperiodic tilings, undecidability, shifts of finite
type, substitutions, strongly aperiodic tilings, tilings with any
computable density, tiling with high Kolmogorov complexity,
robustification, etc. (Tools: islands and bi-islands.)

** October 27 — November 11: **
A.Shen's visit to Moscow (Kolmogorov seminar, IITP, Poncelet
laboratory, Moscow State University, A.Rumyantsev thesis
defence)

** November: **

A paper "Set of k-independent strings" (Cling-Lueh Chang,
Yuh-Danh Lyuu, Yen-Wu Ti, Alexander Shen) submitted and accepted by
International Journal of the Foundations of Computer Science

pdf file

** December 1-4: **
FRAC - SDA2 - NAFIT meeting in Nice

Des nombres Omega de Chaitin, aux fonctions de Solovay, en
passant par les castors affaires (talk by Laurent Bienvenu)

revised version (July 2010)

Talk by Gregory Lafitte

Probabilistic Proofs, Kolmogorov Complexity and Laslo Lovasz
Local Lemma (a tutorial, given by A.Shen)
slides of a talk

Mutually independent strings in algorithmic information theory
(talk given by A.Shen)
slides of a talk

** December 12, 2009 — January 17, 2010:**
A.Shen's visit to Moscow (Poncelet lab, Moscow State University,
IITP)

** 2009 — 2010:**
Collaboration between Vereshchagin, Shen, Vovk on martingales
and randomness tests. The results are included in two papers:

A.Philip Dawid, Steven de Rooij, Glenn Shafer, Alexander Shen,
Nikolai Vereshchagin, Vladimir Vovk: Insuring against loss of
evidence in game-theoretic probability,

pdf file

Glenn Shafer, Alexander Shen,
Nikolai Vereshchagin, Vladimir Vovk: Martingales and p-values as
measures of evidence,

pdf file

** February 08—12: **
Math Info 2010: Towards new interactions between mathematics
and computer science.
Dynamics and Computation, workshop in CIRM.

Workshop "Randomness
in general spaces and uniform tests of randomness".

Talk by A.Shen:
Every one dimensional effectively closed subshift is a projection of
two-dimensional finite type subshift.

** February 15—19: **
Math Info 2010: Towards new interactions between mathematics
and computer science
Multi-Dimensional Subshifts and Tilings, workshop in CIRM.

Talk by Andrei Romashchenko.

** February 20 — April 24: **
A.Shen's visit to Penn State University (Shapiro program, host:
Steven Simpson) and Boston University (host: Peter Gacs).

Talks on Lovasz Local lemma and Medvedev degree of everywhere
complex sequences (result by Andrey Rumyantsev).

** March 25: **
The paper "Variations on Muchnik's Conditional Complexity
Theorem" by Daniil Musatov, Andrei Romashchenko and Alexander
Shen accepted for publication in Theory of Computing Systems.

** April: **
Vereshchagin and Shen participate in the Reading Committee of
Bruno Bauwens PhD defence; thesis involves online complexity
and algorithmic statistics

** May: **
Vereshchagin visits Ghent Univeristy for Bruno Bauwens PhD
defence and for work with him on total conditional complexity

** May 20—31: **
A.Shen's visit to Logic, Computablity and Randomness conference
(Notre Dame University)

Invited talk on ergodic characterizations of randomness (joint
work with L.Bienvenu, A.Day, I.Mezhirov).

** June 13—15: **
French – Russian workshop in Poncelet laboratory on algorithms,
complexity and applications

(A.Romashchenko, A.Shen, T.Kaced, N.Vereshchagin, T.Fernique et al.)

** June 16—20: **
Computer Science in Russia 2010 conference, Kazan, Russia

(Talks by N. Vereshchagin, P. Karpovich.
A.Shen: member of program committee)

slides of Karpovich's talk

** June 21—27: **
GTP2010: Third Workshop on Game-Theoretic Probability and Related Topics

(Talk by A.Shen on algorithmic on-line approach to randomness;
discussions with Alexey Chernov)

** June 29 — July 6: **
Computability in Europe 2010: Programs, Proofs, Processes

Workshop on Computability Theory 2010

Talks given by A.Shen on ergodic characterization of randomness
(joint work with L.Bienvenu, A.Day, I.Mezhirov, with
improvements by M.Hoyrup)

updated version, pdf ,
slides

and by I.Razenshteyn on domains of
plain and prefix decompressors (joint work with M.Andreev and
A.Shen)

pdf ,
slides

** June 25 — July 30: **
Visit of Alexander Kulikov (including CiE conference)

Kulikov's paper at CiE

** August 2010 **
Visit of Daniil Musatov (Moscow)

Work of Andrei Romashenko and Daniil Musatov: Using Nisan — Widgerson
pseudo-random generators and extractor-like property testing to
improve bounds in Muchnik's theorem for space-bounded conditional
descriptions

arxiv report

** September 17, 2010: **
G.Lafitte, A.Shen report on NAFIT progress at ANR

recommendations

** September 2010: **
Visit of A.Shen to Poncelet laboratory

Talk at the IITP RAS on the new proof of effective
ergodic theorem

** November 2010: **
Andrey Rumyantsev proved the infinite computable
version of Lovasz local lemma using Moser-Tardosh technique

draft (pdf)

** November 2010: **
Andrey Rumyantsev paper on Simpson problem (the Medvedev degree
of everywhere complex sequences is not weakly reducible to the Medvedev
degree of random sequences) is accepted by
STACS 2011

arxiv version

** 9-11 December 2010: **
Visit of A.Shen to Ekaterinburg (Russia): Six popular
lectures for Ekaterinburg's students and programmer:
"Selected topics of theoretical computer science"
(invited by Computer Science club, Ekaterinburg)

** November 2010: **
Papers on martingale calibrations (see above)
are accepted for publication
by "Statistical Science" (Test martingales, Bayes factores and
p-values) and "Statistics and Probability Letters" (Insuring
against loss of evidence in game-theoretic probability).

** 27 November 2010: **
Russion version of the book: V.A.Uspensky, N.K.Vereshchagin, A.Shen,
"Kolmogorov complexity and algorithmic randomness" is finished and
submitted for publication.

pdf file

** 15-17 December 2010 **
JAC 2010 conference (Turku)

B.Durand invited talk "1D Effectively closed subshifts
and 2D tilings"
(delivered by A.Shen)
pdf

A.Shen, talk: "Decomposition complexity"
pdf

A long paper where the randomness deficiency with respect to
non-computable measures and classes of measures is investigated,
is prepared by L.Bienvenu, P.Gacs, M.Hoyrup, C.Rojas, A.Shen and
submitted for publication.

pdf

An exposition of Andrej Muchnik's results on Kolmogorov complexity approach to cryptography is prepared by A.Chernov and A.Shen

A.Shen: visit to Poncelet laboratory.

Textbook on information theory (in Russian) prepared by
A. Romashchenko, A. Rumyantsev, and A. Shen is published (MCCME
Publishers, Moscow)

pdf

T.Kaced developed Kolmogorov complexity secret sharing
framework in the paper ``Almost-perfect secred sharing'',

http://arxiv.org/abs/1103.2544

T.Kaced and A.Romashchenko
found a new conditional non-Shannon inequality for information
and showed that there exist essentially non-conditional inequalities
in the paper
``On essentially conditional information ineequalities''

http://arxiv.org/pdf/1103.2545

The paper "Variations on Muchnik's Conditional Complexity Theorem" by Daniil Musatov, Andrei Romashchenko and Alexander Shen published in Theory of Computing Systems (Springer), Volume 49, Number 2, pp. 227–245 (2011). The paper is available electronically on SpringerLink: http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/s00224-011-9321-z. Preliminary version: arXiv:0904.3116.

Workshop ``Computability and Randomness in Paris''
supported (in part) by NAFIT

A.Shen: talk ``Intuitionistic logic and Kolmogorov complexity''

F.Givors' talk

** June 14—18 2011 **
The 6th International Computer Science Symposium in Russia

Program Committee chair: N. Vereshchagin

A.Shen, invited talk: "Kolmogorov complexity as language",
http://arxiv.org/abs/1102.5418, pdf,
slides, pdf

A.Romashchenko, contributed talk: "Pseudo-random graphs and bit probe schemes
with one-sided error", http://arxiv.org/abs/1102.5538v3, pdf,
slides, pdf

D.Musatov, contributed talk: "Improving the Space-Bounded version of
Muchnik's Conditional Complexity Theorem via "Naive" Derandomization",
http://arxiv.org/abs/1102.5538v3, pdf,
slides, pdf

The latter paper (D.Musatov) got the best student paper prize

** July 2011 **
Visit of Peter Gacs; discussion on common information and error correction in cellular automata

** July 25 — 29 2011 **
International Mathematical Conference "**50 years of IPPI**"

A.Romashchenko, contributed talk: "Two applications of pseudo-random graphs"

** July 31 —August 5 2011 **
IEEE International Symposium on Information Theory (ISIT 2011)

T.Kaced, contributed talk: "Almost-perfect secret sharing", http://arxiv.org/abs/1103.2544, pdf
slides, pdf

A.Romashchenko, T.Kaced, contributed talk: "On essentially conditional information inequalities",
http://arxiv.org/abs/1103.2545, pdf,
slides, pdf

A final version of the paper on randomness deficiency with
respect to non-computable measures and classes of measures (L.Bienvenu, P.Gacs, M.Hoyrup,
C.Rojas, A.Shen)
is published in Proceeding of Steklov Mathematical Institute
(Springer-Verlag) in English and Russian

english pdf

russian pdf

A final version of the
exposition of Andrej Muchnik's results on Kolmogorov complexity
approach to cryptography prepared by A.Chernov and A.Shen
is published in Proceeding of Steklov Mathematical Institute
(Springer-Verlag) in English and Russian

english pdf

russian pdf

A paper "Fixed-point tile sets and their applications" accepted by JCSS

pdf

Visit of Laurent Bienvenu and Rupert Holzl (LIAFA) to LIRMM

A paper on adding random axioms to formal theories (in particular, axioms saying that some strings have high complexity) is posted in arxiv

A paper "Fixed-point tile sets and their applications" accepted by JCSS

pdf

Visit of Laurent Bienvenu, Antoin Tavenaux, Stijn Vermeeren (LIAFA) and
Bruno Bauwens (Univ. Porto) to LIRMM.

Paper with the O(1)-precision formula for plain complexity of pairs
is posted in arxiv and submitted

arxiv version

More about random axioms: what happens if we select some
infinite random sequence and add an axiom saying that this
sequence in random? (Paper in preparation).

A.Shen's visit to Poncelet laboratory and Kolmogorov seminar.

Talks on Kolmogorov seminar on additivity formula.

November 26: Lecture for high school students (Moscow State
University): "2D problems and 3D solutions".

November 30 - December 1:
Lectures in Nizhny Novgorod (Russia): seminar of the N.N. State
University Applied Math laboratory ("Computational and
descriptional complexity"), popular lecture for high school
students ("Theoretical computer science: what is it and what is
it for?") and a talk for physicists ("What is algorithmic
randomness?")

** January 2012, 8-13 **
Computability, complexity and randomness. Seminar 12021, Dagshtuhl.

NAFIT people among the participants:
Bruno Bauwens, Laurent Bienvenu, Benoit Monin, Andrei Romashchenko,
Alexander Shen, Antoine Tavenaux, Stijn Vermeeren.

** February 2012, 22-23 **
Winter FRAC 2012

NAFIT people among the participants and their talks:
Fabien Givors (Subcomputabilities),
Alexander Shen (Topological arguments for Kolmogorov Complexity),
Laurent Bienvenu (On absolutely undecidable sets),
Gregori Lafitte (Computability and what not).
Emmanuel Jeandel, Tarik Kaced, Pascal Vanier, Antoine Tavenaux, Rupert Holzl.

Paper published: Bruno Bauwens, Alexander Shen, An additivity theorem for plain Kolmogorov complexity, Theory of Computing Systems, Online First, February 2012.

** March 2012, 5-6 **
Journées Calculabilités, Paris.

NAFIT people among the participants and their talks:

- Mathieu Hoyrup : Computability in ergodic theory, slides.
- Emmanuel Jeandel : Effective dynamical systems, slides.
- Tarik Kaced : Essentially conditional information inequalities.
- Antoine Taveneaux : The axiomatic power of Kolmogorov complexity, slides.

** April 2012 **
A revised version of the paper "Limit complexities revisited" is
posted in
arxiv (1204.1201v1, "Limit complexities revisited [once more]")

It includes a simple proof of Bruno Bauwens of Conidis' result
that simplifies significantly the original arguments, and some
generalizations.

Visit of LIAFA team: L.Bienvenu, R.Holzl, B.Monin, L.Patey

Working group on computability and complexity: tutorial about constructive
ordinals (Monin), Gacs--Kucera theorem (Holzl)

Visit of Bruno Bauwens:

Work on the criterions of 2-randomness using plain and prefix complexities

Turing centennary celebrations

L.Bienvenu: Logique et calculabilite. L'influence de Turing aujourd'hui

A.Shen: Following the path of Turing Invited talks:

Laurent Bienvenu talk on random axioms

slides

Alexander Shen talk on game-theoretic approach to computability theory (Game arguments in Computability Theory and Algorithmic Information Theory. How the world computes, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 2012, Proceedings. LNCS 7318, p. 655-666, 2012. Springer-Verlag.)

arxiv slides

Contributed talks:

Bruno Bauwens: complexity of complexity

Antoine Tavenaux: blind martingale randomness

Benoit Monin: transforming sequences that are random with respect to a class of measures into uniformly random sequences

A.Shen's visit to Royal Holloway College research group (V.Vovk, A.Chernov)

Seminar talk: quantitative approaches to randomness (randomness deficiency for
infinite sequences

Computability, Complexity and Randomness workshop (Newton Institute, Cambridge)

A.Shen's talk on topological arguments in complexityarxiv

slides

Bruno Bauwens: criterions of 2-randomness with plain and prefix complexity, simplified proof and quantitative version

** July 2012 **

Paper: A constructive version of Birkhoff's ergodic theorem for
Martin-Lof random points, Information and Computation, 210
(2012), 21-30 published

** August 2012 **

21-30: A.Shen,
ISSMYS, Lyon,
lecture on Kolmogorov complexity

Visit of N.~Vereshchagin, A.~Makhlin

Preparation of the final version of a monograph on Kolmogorov complexity that covers some results of NAFIT project

book

Visit of V.~Podolsky

Tropical operations and games

Visit of M.~Dektyarev

Work on djvu software (halftonal originals conversion to multilayer djvu)

github page

Visit of B.~Bauwens

On-line complexity is not additive (the complexity of odd and
even bits prediction may come close to the complexity of the
entire string).

** September 2012 **

Information theory conference (Sept. 2-7, Switzerland)

Andrei Romashchenko, Tarik Kaced; talk on the non-robustness of essentially conditional
non-Shannon-type inequalities for entropy

paper

slides

poster

AUTOMATA 2012 conference (Sept. 19-21, 2012, Bastia)

Andrei Romashchenko, Alexander Shen: Topological arguments in
complexity (improved version, with Muchnik-type arguments)

paper

slides

RuFiDim II conference (Sept. 25-28, 2012)

Alexander Shen invited talk:
Probabilistic construction of computable object (with Andrei Rumyantsev)

paper

slides

A.Shen: crash course on theoretical computer science (20 hours in two weekends) (St. Petersburg computer science club)

Muchnik, Shen, Vyugin, long version of the game-theoretic paper
(new proof of Levin-Epstein theorem, unpublished result of
Muchnik and Vyugin et al.)

paper

** October 2012 **

Alexander Shen's visit to Moscow (Poncelet lab, Kolmogorov seminar)

Oct. 1: Seminar talk on Kari's aperiodic tiling

notes (English)

Oct.17: Aperiodic tilings: an expository talk at Raigorodsky's
seminar in MFTI

Oct. 18: Moscow Mathematical GLOBUS seminar talk: Computer
science: why it is sound mathematics? (A survey of main results
of computer science for mathematicians.)

backup slides

Oct. 20: Popular talk for high school children

** November 2012 **

Long version of the random axiom paper submitted for the special APAL issue

pdf

NAFIT visit: Hayato Takahashi (van Lambalgen theorem on pairs
for conditional co probabilities).

NAFIT visit: Bruno Bauwens (on-line complexities, algorithmic
statistics)

Final version of the monograph "Kolmogorov complexity and
algorithmic randomness" (Shen -- Uspensky -- Vereshchagin) is
submitted to the printer (to be published in 2012)

pdf

** December 2012 **

Reviewers: E.Asarin, F.Matus, K.Makarychev

thesis (pdf)

** January 2013 **

Dec.24--Jan.14 (2013): A.Shen visit to Poncelet laboratory (Moscow), Dinastiya grant committee meeting. Paper with A.Rumyantsev:

** February 2013 **

February 06: A.Romashchenko's visit to Poncelet lab and Kolmogorov seminar (Moscow)

February 25 -- March 01: B.Bauwens' visit February 28 -- March 01:

FRAC: A.Shen's talk on Kari aperiodic tiling (simplified version); B.Bauwens' talk on algorithmic statistics.

** March 2013 **

A.Shen's visit to Poncelet laboratory and Kolmogorov seminar

Talk at IPPI seminal (L.Bassalygo):Information theory and computer science: three problems.

Talk at MCCME seminar (A.Gasnikov): Foundations of probability theory and algorithmic information theory (March 23).

Postnauka (web site on popular science): Kolmogorov complexity and Turing machines (March 27).

Talk at the Shekhtman anniversary conference (IPPI, March 29) on knowledge and protocols in computer science.

Talk on Kolmogorov complexity (Moscow Huawei research center, April 03).

Lectures on tilings for undegraduate students (March 14, April 04). Talk at the Math. Dept.( VShE) seminar on fixed point tilings. (April 05).

Popular lecture on complexity theory and its application (ZIL cultural center, April 08).

** April 2013 **

April 15 -- April 21. A.Shen's visit to LIAFA (L.Bienvenu group). Talks on algorithmic statistics, uniform ergodic theorem.

April 22 -- April 26: visit of Antoine Tavenaux: Algorithmic statistics and random axioms.

** May 2013 **

Itsykson's talk: group de travail, May 13. May 01 -- May 31: visit of Vsevolod Oparin (Saint-Petersburg, Academic University): Search problems (query complexity, reductions) Paper of Itsykson and Oparin accepted for CSR 2013 conference. (pdf)

Paper about complexity of complexity (Bruno Bauwens, with some additions by A.Shen) accepted for publication in the Journal of Symbolic logic

** June 2013 **

Algorithmcs, complexity and applications

June 25 -- July 2: Computer Science in Russia 2013 conference, CSR 2013;

Summer School for graduate students, A.Shen's tutorial on Kolmogorov complexity