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
 A.Milovanov "#P and ⊕P completeness of counting roots of a sparse polynomial" submitted to arxiv
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", talk slides
 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
 July 28: Computability, complexity and randomness 2017 (Mysore, India) , A.Milovanov (RaCAF visitor) talk: slides
 July 69 Computation Complexity Conference 2017, A.Milovanov (RaCAF visitor) and N.Vereshchagin (RaCAF visitor) talk "Stochasticity in Algorithmic Statistics for Polynomial Time", proceedings
 July 1014, ICALP (Warsaw), Olivier Bournez (with A.Pouly) talk "A Universal Ordinary Differential Equation", pdf
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
 2024 October: D.Musatov (RaCAF visitor): talk at the conference in Maikop (Russia), "Probabilistic and Kolmorogorov extractors with several sources", Proceeding of the Second International Conference "Autumn Workshop in Adygee", p. 165170. 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
 A.Milovanov (RACAF's visitor) paper "On algorithmic statistics for spacebounded algorithms" published by Theory of Computing Systems reprint
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)
April
 10 April: A.Shen's talk at Computer Science Dept., University of Chicago, Toyota Institute, "Forbidden factors: tetris proof"
 11 April: A.Shen's talk at NWU: "Kolmogorov complexity as language"
 19 April: A.Shen's talk at Boston University on Kolmogorov complexity
May
 25 April  20 May: Gleb Posobin (master student at HSE, Moscow, thesis advisor A.Shen) visit to LIRMM. Random noise increases Kolmogorov complexity, master thesis
 10 May: Julien Destombes, A.Romashchenko, ResourceBounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts, submitted to arxiv
 31 May: "Algorithms and geometric constructions" (with Vladimir A. Uspenskiy, Moscow) submitted to arxiv
June
 2 June  15 June: A.Shen's visit to Moscow (program committee member for Computer Science in Russia 2018")
 A.Shen: work with Bruno Bauwens (Moscow) on the information distance
 15 June  30 August: A.Milovanov's visit to LIRMM
July
 23 July, LIX: calculability group and RaCAF meeting (Olivier Bournez, Laurent Bienvenu,Gregory Lafitte, Andrei Romashchenko, Alexander Shen) homepage
 G.Lafitte, Higher order computability musings and absoluteness abstract
 A.Shen, Random noise and Kolmogorov complexity abstract slides
 A.Romashchenko, Le problème d'agrément de clé secrète et une caractérisation de l'information mutuelle, abstract
 913 July: A.Shen, invited talk at a school "Mathematical physics of nonperiodic structures" (on fixedpoint tilings), Bedlewo, Poland site
 9 July  13 July: Andrei Romashchenko's talk "An operational characterization of mutual information in algorithmic information theory" at ICALP paper
 12 July  30 July: Alexey Vinogradov (master student, Moscow University) visit to LIRMM, work on randomness tests master thesis (in Russian, Moscow State University)
 29 July: Paper "Information distance revisited" submitted to arxiv
August
 30 July  3 August: Computability in Europe 2018 (Kiel) site
 A.Shen's talk: "Algorithms and Geometric Constructions" paper; talk
 A.Milovanov's talk "Algorithmic Statistics and Prediction for polynomial timebounded algorithms" paper
 14 august: G.Posobin, A.Shen, Random noise increases Kolmogorov complexity and Hausdorff dimension, submitted to arxiv

2731 August: Mathematical Foundations of Computer Science, 2018 (Liverpool) site
 A.Shen, Mikhail Andreev (RaCAF visitor), Plain stopping time and conditional complexities revisited paper, talk
September
 115 September: A.Shen's visit to Poncelet laboratory (Moscow)
 34 September: Anniversary conference program talk "Three approaches to the quantitative definition of information"
 Kolmogorov seminar talk: Kolmogorov complexity and games
 1415 September: Mathematics Education Workshop (Moscow 57th school)
 A.Shen's paper on algorithms of geometric constructions is published by Mathematical Intelligencer shareable link
October
 D.Musatov (RaCAF visitor), "Approximate Coalitional Equilibria in the Bipolar World", joint work with Andrei Golman, OPTIMA 2018, CCIS 974 Proceedings, Springer pdf
November
 A.Shen's visit to National Research University Higher School of Economics (Moscow)
 26, 30 November: Short course: "Interactive Proofs" (8 hours)
 19 November: Logic Seminar talk "The life and work of Vladimir A. Uspensky"
 20, 24, 27 November: popular talks for high school children on probability theory, measure theory and tilings (57th school, Moscow)
December
 December 1,2,8,9: A.Shen course (Computer Science Club in Saint Petersburg): Basic Notions and Tools in Computer Science (16 hours)
 A.Shen: Visit to International Science Center in Kazan (Russia): talks on Kolmogorov complexity and applications to recursion theory
slides
 December 10: Talk at the Logic Seminar in Saint Petersbourg (Matiyasevich group): Kolmogorov complexity, Shannon entropy and noise
 G.Posobin, A.Shen submission to STACS (Random noise increases Kolmogorov complexity and Hausdorff dimension) accepted
 J.Destombes, A.Romashchenko submission to STACS (ResourceBounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts) accepted
2019
January
 Alexander Kozachinsky (HSE Moscow) visit, work on finite state dimension characterization
 January 16: Alexander Kozachinsky's talk on parity game and finite automata (ECO/ESCAPE seminar)
February
 Ruslan Ishkuvatov, RaCAF CDD research engineer (2019) joined RaCAF team in Montpellier
 A.Milovanov (RaCAF visitor) paper "#Pcompleteness of counting roots of a sparse polynomial" accepted by Information Processing Letters, Volume 142, February 2019, Pages 7779, link pdf
 February 6: A.Romashchenko's talk on inequalities for entropies and secret sharing (ECO/ESCAPE seminar)
 February 13: Emirhan Gürpinar (RaCAF stagiere, ENS Lyon)'s talk on inequalities for entropies and secret sharing (ECO/ESCAPE seminar, joint work with A.Romashchenko)
 O.Bournez (with François Fages, Guillaume Le Guludec, Amaury Pouly) got La Recherche prix for the paper "Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed AnalogDigital Programs" (CMSB 2017)
March
 B.Durand, A.Shen, N.Vereshchagin's paper On the Structure of Ammann A2 Tilings is published in Discrete and Computational Geometry
 G.Posobin, A.Shen: STACS 2019 talk (Random noise increases Kolmogorov complexity and Hausdorff dimension) paper
 J.Destombes, A.Romashchenko: STACS 2019 talk (ResourceBounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts) paper arxiv version slides
 R.Ishkuvatov's talk: Approximating Kolmogorov complexity is as difficult as computing it (ECO/ESCAPE seminar) slides
 R.Ishkuvatov and D.Musatov (RaCAF visitor) paper on approximation of Kolmogorov complexity is accepted by CiE 2019
April
 Visit of Alexander Smal (POMI RAS, St.Petersburg)
 Revised version of paper by A.Romashchenko and M.Zimand submitted to JACM, arxiv version
 April 112: A.Romashchenko, visit to Moscow, Higher School of Economics: minicourse on secret sharing, talk on Shannon entropy in combinatorial problems slides
May
 A.Shen: visit to Moscow (10 May  30 June)
 May 10, 18, 30, 31: A.Shen, popular talks for high school children
 May 20: A.Shen, A.Kozachinsky (RaCAF visitor) paper accepted by FCT2019 submitted pdf
 May 26: A.Shen, invited talk "Complexity of universal statements and Kolmogorov complexity" at St. Petersburg Days of Logic and Computability talk slides
 A.Romashchenko, M.Zimand, "On a conditional inequality in Kolmogorov complexity and its applications in communication complexity", preprint submitted to arxiv
June
July
 July 712: 2019 IEEE International Symposiun on Information Theory (Paris), E.Gürpınar (RaCAF intern), A.Romashchenko. How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma. Proceedings of IEEE International Symposium on Information Theory (ISIT) 2019, pp. 13771381 arxiv version slides
 July 19, R.Ishkuvatov (RaCAF CDD) at Computability in Europe, 2019, Durham, On approximate uncomputability of the Kolmogorov complexity function, paper slides (joint work with D.Musatov)
 July 19, G.Lafitte at Computability in Europe, 2019, Durham An algorithmic approach to characterizations of admissibles (joint work with B.Durand)
August
September
 Emirhan Gürpınar, previous RaCAF stagiere, started his Ph.D program
 A.Shen, A.Kozachinskiy paper on normality and randomness published in arxiv (as a replacement of the previous paper)
 Device from ubld.it for generating random bits (about 50 kbytes/s) bought, experiments started
 Paper by A.Romashchenko and M.Zimand published by Journal of the ACM link to the paper at ACM site (paywall)
October
 Device from www.gniibe.org (open source, based on a microprocessor device, but voltage and temperature are only source of randomness, access to raw bits available) arrived
 Ordered devices:
chaoskey,
araneus,
bitbabbler ("white"),
1337.org,
ubld.it: True rng pro (faster device, 3.2 mbits/s with access to raw bits),
SwiftRNG LE faster device (20 mbits/sec),
ID quantique 4 mbits/sec of true "quantum randomness"
 dieharder suite analyzed: errors in bitstream test found
 October 7: CIEL talk by A.Shen slides: Normality and Randomness
November
 November  December 2019: visit of A.Shen to Higher School of Economics Computer Science Department (Moscow, Russia)
 Devices:
chaoskey, arrived, installed without ptoblems, basic health tests OK
araneus, arrived software compiled, installed without problems after deleting chaoskey module, basic health tests OK
bitbabbler ("white"), arrived, installed bitbabbler, bitbabblerdbg with apt, basic health tests OK, raw bits consistent with the model
ID quantique true quantum randomness device arrived, tested, ent test fails for the standard output (no randomness extraction step with multiplication by random matrix)
1337.org "infinite noise" device , arrived, downloaded and installed packages from the site, raw bits consistent with the model
ubld.it: True rng pro (faster device, 3.2 mbits/s with access to raw bits) arrived, raw bits look like Gaussian noise
Moonbase OneRNG device ordered
 November 13: Moscow State University Mathematics Department, Logic and Algorithms group seminar: talk on random bits (A.Shen)
 November 11, 18: Kolmogorov seminar (Moscow)  talk of practical randomness (A.Shen)
 November 2527: GDR Computability and RaCAF meeting: villa Finaly (Florence). Talk by A.Shen slides : Random btis in practice and theory
December
 December 1: Higher School of Economics workshop (Moscow): A.Shen's talk on randomness
 Devices:
SwiftRNG LE faster device (20 mbits/sec), arrived, installed without problems, basic health tests OK, raw bits accessed
ID quantique true quantum randomness questions about the functioning of device prepared, support contract purchased (needed to ask them)
Moonbase OneRNG device arrived, visible nonrandomness in zener noise, both in raw and whitened, better results for RF noise
 A survey on the random bits generators and tests prepared (the general part, test results and recommendations to be added later): pdf
2020
January
 Paper by Bruno Durand and Andrei Romashenko "The Expressiveness of Quasiperiodic and Minimal Shifts of Finite Type" published in "Ergodic theory and dynamical systems" journal link, arxiv link
 SwiftRNG LE analysis of the raw bits and exchanges with the company: they are 8 least significant bits of avalanche noise of Zener diodes (and therefore have distribution close to uniform but not enough uniform to pass tests before XORing)
 SwiftRNG PRO device ordered (it is claimed to produce 16 bits from each noise source that pass the tests without loss of entropy by XOR or other conditioning)
 Fabian Givors hired as research engineer to work on Dieharder tests improvements (starting from February)
 Jamuary 30: Demonstrations for HCERES evaluation of the lab