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 \(hK\)triviaux (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
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
 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
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
September
October
 Arrival of a postdoctoral visitor (University of Turky), Illka Törmä (August 3, 2017  July 31, 2018
November
December