RaCAF project: diary
2016
January

Andrei Romashchenko: paper "On the combinatorial version of the SlepianWolf problem" (with Daniyar Chumbalov)
arxiv
submitted

Andrei Romashchenko: paper "Conditional Information Inequalities and Combinatorial Applications"
(with Tarik Kaced and Nikolay Vereshchagin)
arxiv
submitted
February

Andrei Romashchenko: report "Coding in the fork network in the framework of Kolmogorov complexity"
arxiv
 Nexus of Information and Computation Theories
program information

February 1720: STACS 2016.
homepage
Alexey Milovanov (RaCAF visitor)
pdf
April

Journees calculabilites 2016 a Nice (partially supported by RaCAF)
homepage
timetable
abstracts
Talks:

A further introduction to forcing (L.Bienvenu, G.Lafitte)

Computing and Programming with Continuous Dynamical Systems (O.Bournez)

The busy beaver functions, Chaitin's number, and combinatorial properties of Kolmogorov complexity (A.Romashchenko)

A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods (Anael Grandjean)

A resolution of the Gamma question (B.Monin)

Some ordinal time algortihmics (S.Ouazzani)

Higher Randomness et caracterisation des hKtriviaux (P.E.A.d'Auriac)

Alexander Shen: Popular lecture for high school students (Moscow): Fair randomness: what is it and how to get it?
May

Olivier Bournez: a course at DIGICOSME SPRINGSCHOOL 2016 / MAY 913 / ENSTA PARISTECH
Hybrid systems

Olivier Bournez: a CIRM talk "Calculer avec des equations differentielles: calculabilite, complexite"
CIRM video

Hilbert's Sixth Problem (workshop, University of Leicester)
homepage
Alexander Shen's invited talk
slides

Alexander Shen: talk at Brunel University seminar (UK)

Alexander Shen: Popular lecture for high school students (London, UK)

EQUINOCS concluding workshop
homepage
Alexander Shen's invited talk "Three approaches to information theory: Shannon, Kolmogorov and combinatorial"
(blackboard talk)

Alexey Milovanov (RaCAF visitor): Algorithmic statistics: Normal
Objects and Universal Models,
accepted paper for CSR 2016 conference (proceeding: LNCS 9691, 280293)
arxiv,
conference version
June

June 419: Rod Downey visits the LIRMM. Works with Laurent Bienvenu
and gives a talk (Logic for Algorithms) at the team seminar.

Transversal aspects of tilings (Oleron)
homepage
Week 1: Computation.

Andrei Romashchenko's minicourse: Embedding computations in tilings

Alexander Shen's talk: Fixed points and subaction (blackboard)

Computability, Randomness and Applications, June 2024, 2016 (CIRM)
homepage
Andrei Romashchenko's talk: On centauric subshifts
slides

Alexey Milovanov (RaCAF visitor): paper "Some properties of antistochastic strings" published in Theory of Computing Systems
reprint

June 29: Vsevolod Oparin (RaCAF visitor) talk: "Tight bounds on splitting with linear combinations for pigeonhole principle"
slides

June 27  July 1: Computability in Europe conference

Olivier Bournez: paper ``Axiomatizing Analog Algorithms'' (with N.Dershowitz, P.Neron)
pdf
(best paper award)

Mikhail Andreev (RaCAF visitor): paper ``Busy beavers and Kolmogorov complexity''
pdf
presented (best student paper award)
July

ICALP 2016
conference
Olivier Bournez: paper "Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length. The General Purpose Analog Computer and Computable Analysis are two efficiently equivalent models of computations"
pdf
(best Track B paper award)

Alexander Shen:
Chapter "Algorithmic Information Theory" (The Routledge Handbook
of philosophy of information, Routledge, 2016, edited by
L.Floridi, 3744) published
preliminary version

Alexander Shen:
Paper "Conditional probabilities and van Lambalger theorem revisited"
(with B.Bauwens, H.Takahashi)
(submitted)
arxiv version

Alexander Shen, Laurent Bienvenu:
Paper "Layerwise computation and image randomness"
(with M.Hoyrup)
(submitted)
arxiv version

Alexander Shen:
Paper accepted for Downey's volume
(with N.Vereshchagin)
Algorithmic statistics: forty years later (accepted for publication)
arxiv version
August

Laurent Bienvenu gives the Barry Cooper Lecture at the Logic
Colloquium
slides

Guilhem Marion (ENS, stagiere): Le hasard et sa production, rapport finale de stage pdf
September

Laurent Bienvenu:
Paper "On the logical strengths of partial solutions to mathematical
problems" (joint with Paul Shafer and Ludovic
Patey) accepted for publication in Transactions of the London
Mathematical Society
arxiv version

Olivier Bournez:
Paper "On The Complexity of Bounded Time Reachability for Piecewise Affine Systems" (with H.Bazille, W.Gomaa, A.Pouly)
pdf accepted for publication by Theoretical Computer Science

Olivier Bournez:
Analog models of Computation, invited talk, Ecole Polytechnique (September 22)
October

7 October: RaCAF meeting (Montpellier):
Olivier Bournez,
Bruno Durand,
Gregory Lafitte,
Andrei Romashchenko,
Alexander Shen
program

10 october: A.Shen's mission Moscow Higher School of Economics
computer science department (till 2017)
November

30 november: V.Oparin (RaCAF visitor) thesis defence (A.Shen's review)
St.Petersbourg, Russia
December

A.Shen: Talk: Automatic Complexity, High School of Economics.

A.Shen: Introductory minicourse on complexity for undergraduate students (HSE)
2017
January

January, 1  January, 29: Visit of N.K.Vereshschagin (Moscow University, HSE),
A.Milovanov (Moscow University, HSE)

An extended version of the survey paper on algorithmic statistics (with proofs)
arxiv

Alexey Milovanov: "On Algorithmic Statistics for spacebounded
algorithms" submitted (Update: accepted) to CSR 2017 conference
arxiv
February
 February 16: A.Shen: Normal numbers and Automatic Complexity, talk at Mathematics Department, Strasbourg University
talk slides
arxiv

Feb. 1924: L. Bienvenu and A. Shen attend the Dagstuhl Seminar
"Computability Theory" in Germany.

L. Bienvenu: deep effectively
closed sets
 A. Shen on stopping time complexity
abstract
slides
March

March 9: A.Shen, invited talk for CiE 2017, "Compressibility and probabilistic proofs" (tetris proof, forbidden string, amortized analysis and the inequality \( \sum a_n x^n \le 2x1 \)) arxiv
 A.Romashchenko: STACS 2017 talk (with Dmitry Itsykson, Alexander Knop, Dmitry Sokolov) pdf (HAL archive)
April
 Bruno Durand, Andrei Romashchenko, "On the expressive power of quasiperiodic SFT" (submitted), arxiv
 D.Musatov (Moscow, MIPT) visit: 21 April  30 May
June
 Computability in Europe conference
 A.Shen: invited talk pdf slides
 Merlin Carl, Bruno Durand, Gregory Lafitte and Sabrina Ouazzani. Admissibles in gaps
 Oscar Defrain, Bruno Durand and Gregory Lafitte. Infinite time busy beavers
 G.Novikov (RaCAF visitor): Randomness deficiencies pdf
 Computer Science in Russia 2018, A.Milovanov (RaCAF's visitor) talk "On Algorithmic Statistics for spacebounded algorithms"
 A.Shen: Visit to St.Petesbourg (Steklov Institute, laboratory of mathematical logic), 19 juin5 juillet
 B.Bauwens, A.Shen, H.Takahashi: paper on conditional probabilities published (Theory of computing systems )
 L.Bienvenu, M.Hoyrup, A.Shen: paper on layerwise computable mappings and image randomness (Theory of computing systems)
 A.Shen: Automatic complexity and normality (accepted by FCT 2017 conference) pdf
 Bruno Durand, Andrei Romashchenko, "On the expressive power of quasiperiodic SFT" accepted by MFCS
 G.Lafitte (with J.Cervelle) : On shiftinvariant maximal filters and hormonal cellular automata, talk at LICS 2017, doi, HAL
July
August
 A.Shen: updated version of normality and automatic complexity paper, arxiv
 Visit of Mikhail Andreev (graduate student from Moscow)
 M.Andreev, G.Posobin, A.Shen, Plain stopping time and conditional complexities revisited, arxiv
 MFCS 2017 (2125 August) B.Durand, A.Romashchenko, "On the expressive power of quasiperiodic SFTs", arxiv pdf, conference version, talk
September
October
 Arrival of a postdoctoral visitor (University of Turky), Illka Törmä (August 3, 2017  July 31, 2018
 A.Shen's visit to National Research University High School of Economics Computer Department (Moscow) till the end of 2017
 A.Shen: popular talk for high school students: The Importance of Formal Definitions: case study
 A.Romashchenko (with M.Zimand) "An operational characterization of mutual information in algorithmic information theory", arxiv pdf
November
 November 22: A.Shen's talk on algorithmic statistion at Moscow Probability Theory Seminar (invited by A.Shiryaev)
 November 27: A.Shen's minicourse at HSE on pseudorandomness generators (in YaoBlumMicali sense)
 O.Bournez: paper (with D.Graça, A.Pouly) "Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length" published in Journal of ACM link, see also arxiv version
December
 A.Shen popular talk for high school students in Moscow: Continuity arguments and other topics
 A.Shen: collaboration with Gleb Posobin (master student, HSE) about increasing Kolmogorov complexity by randomly changing bits
 A.Shen, V.Uspensky, N.Vereshchagin (RaCAF visitor) book "Kolmogorov complexity and algorithmic randomness" published by American Mathematical Society link, preliminary version
2018
January
 Dimension 1 sequences are close to randoms, paper (N.Greenberg, J.Miller, A.Shen, L.Westrick) appeared in Theoretical Computer Science (link to journal arxiv version)
 A.Shen, ``Hilbert's Error'', arxiv submitted to Mathematical Intelligencer
February
 B.Durand, A.Romashchenko: "The expressiveness of quasiperiodic and minimal shifts of finite type, arxiv pdf (a detailed exposition including MFCS 2017 resuts, 46 pp., 19 ill.), submitted to a journal
 "Algorithms and Geometric Constructions" (V.A.Uspensky, A.Shen) pdf submitted to CiE 2018
 "Making randomness tests more robust", A.Shen, HAL link
 A.Romashchenko (with RaCAF visitor N.Vereshchagin, T.Kaced) "A conditional information inequality and its combinatorial applications", accepted by IEEE Transactions om Information Theory, link
March
 March 4: A.Romashchenko (with M.Zimand) "An operational characterization of mutual information in algorithmic information theory" accepted by ECCC TR18043
 22 March ANR meeting at Paris
talk
pdf
 23 March  30 April: A.Shen's visit to University of Chicago (K.Makarychev, Yu.Makarychev) and Boston (P.Gacs)