Introduction

The informal idea of "information" and "quantity of information" existed for centuries. In 1948 Claude Shannon gave probably the first mathematically sound version of these notions by defining the entropy of random variable. This notion is applicable to random objects; however, informally we still want to measure the amount of information in individual objects. Definition of this type appeared in 1960ies; the most clear and well developed was suggested by Andrei Nikolaevich Kolmogorov in 1965. He also noted the connection between this notion and foundations of probability theory, where the desire to define an individual random object goes back to Richard von Mises. Now algorithmic information and randomness theory is a rich field of research related to probability and information theory, computability theory, combinatorics etc. The NAFIT project is devoted to several topics in the field which are not well studied yet. Here is the short description of some of them.

Multisource algorithmic information theory

Multisource algorithmic information theory is a part of classical (probabilistic) information theory when there are many sources or destinations for information transfer. It is much less developed than one-source and one-destination setting. It turned out that many questions of algorithmic information theory also can be naturally reformulated as problems of information transfer (common information, Muchnik's theorem on conditional descriptions, non-simplifiable programs etc.) It seems also that there are connections even with circuit complexity which deserve further investigation.

On-line and prequential randomness

In "real life" we speak about randomness of events (say, coin tosses) in some context: if the outcomes of coin tosses made by a football referee are correlated with the results of previous games, we will not trust them, though there is no probabilistic assumption on the results. It would be natural to have a definition of algorithmic randomness in similar setting. This problem is closely related to the ideas of prequential randomness, where we get a sequence of probabilistic predictions (say, numbers p_i in [0,1]) and outcomes (bits b_i) and want to determine whether they match each other. (For example, we want to evaluate a pseudo-random number generator or a weather forecasting.) Note that we don't have the entire probabilistic distribution, just its restriction on one path. Still the notion have sense and can be developed both in Mises style (calibration tests) and Martin-Lof style. It seems that there are connection between notions developed earlier in algorithmic randomness (neutral measure) and much more recent topics in prediction theory (universal predictor).

On-line complexity

The on-line setting can be applied not only to randomness, but also to complexity, For example, for a bit string we may look for a program that reads it from left to right and predicts every other bit (say, predicts even bits reading odd bits). In this setting one needs to reconsider many questions that were solved for standard complexity. For example, one may ask whether the sum of on-line complexities of even and odd bits equals the complexity of the entire string (up to logarithmic terms). Recently Bruno Bauwens constructed a counterexample to this statement, but it needs to be understood.

Classes of measures and uniform randomness

There are natural classes of measures (e.g., Bernoulli measures, Markov measures, stationary (shift-invariant) measures); it has sense to ask which sequences are "random" with respect to such a class (e.g., for Bernoulli measures this question was considered in 1960ies by Martin-Lof who introduced the notion of Bernoulli sequence). Later, in 1970ies, Levin and Gacs suggested definitions of uniform randomness tests. Recently this question was reconsidered (e.g., the notion of "Hyppocratic", or "oblivious" randomess was introduces by Kjos-Hanssen; the generalization to metric spaces were suggested by Hoyrup and Rojas, etc.). Still many natural questions here remain unsolved (e.g., natural complexity characterization is not known even for Bernoulli sequences). It seems that the notion of a sparse sequence and a random closed subset may be related to class and uniform tests.

"Kolmogorov-style" cryptography

There are some questions about Kolmogorov complexity that have a natural "cryptographic" flavour. Sometimes it is just a motivation for a question that deals with purely theoretical time-unbounded questions, sometimes people try to transfer notions from cryptography, like one-way functions, into algorithmic information theory. For example, one may try to formulate the notion of secret sharing in complexity terms and establish its connection with probabilistic secret sharing (presumably approximate, which needs to be defined first).

2009

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

slides (pdf)

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.

text (pdf)

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.

text (pdf)

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

text (pdf)

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

Lecture notes (in Russian, pdf)

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

text (pdf)

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)

text (pdf)

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.

text (pdf, Russian)

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.)

text (pdf)

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

June 15: Paper "Algorithmic information theory and Foundations of Probability" (by Alexander Shen) is submitted as an invited talk for
LIX colloquium "Reachability problems'09". See also arxiv:0906.4411 preprint.

text (pdf)

June 26: An introductory talk on Kolmogorov complexity
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

2010

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.

text (pdf)

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

2011

January — February 2011

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

March 2011

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

April — May 2011

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.

June 7—8, 2011

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

September 2011

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

September 2011

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

October 2011

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

November 2011

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).

November-December 2011

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:

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.

May 2012, 4-13

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)

May 2012, 14-22

Visit of Bruno Bauwens:
Work on the criterions of 2-randomness using plain and prefix complexities

June 2012
Turing centennary celebrations
L.Bienvenu: Logique et calculabilite. L'influence de Turing aujourd'hui
A.Shen: Following the path of Turing

CiE conference (18-23 June)

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 complexity
arxiv
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

Dec.4: defence of Tarik Kaced's Ph.D thesis
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:
pdf

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

March 03 -- April 13:
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 17 -- April 18. Rencontres numerique, ANR event; NAFIT is selected for a poster presentation and a short talk
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

April 29 -- May 14: visit of Dmitry Itsykson (Saint-Petersburg, POMI): Complexity of proofs and search problems.
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
pdf

June 2013

June 21 -- June 23: French-Russian workshop at Poncelet laboratory:
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