RaCAF project: diary

2016

• Andrei Romashchenko: paper "On the combinatorial version of the Slepian-Wolf problem" (with Daniyar Chumbalov) arxiv submitted
• Andrei Romashchenko: paper "Conditional Information Inequalities and Combinatorial Applications" (with Tarik Kaced and Nikolay Vereshchagin) arxiv submitted

• Andrei Romashchenko: report "Coding in the fork network in the framework of Kolmogorov complexity" arxiv
• Nexus of Information and Computation Theories program information
  • February 1:
    • Alexander Shen's talk: Different versions of Kolmogorov complexity and a priori probability: an introduction, video, part 1
    • Alexander Shen's talk: Different versions of Kolmogorov complexity and a priori probability: an introduction, video, part 2
    • (Slides, but most of the talk was on the blackboard)
  • February 2: Andrei Romashchenko's talk: On Parallels between Shannon's and Kolmogorov's Information Theories (where the parallelism fails and why), video
    slides
  • February 17-20: STACS 2016. homepage Alexey Milovanov (RaCAF visitor) pdf

• 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?

• Olivier Bournez: a course at DIGICOSME SPRINGSCHOOL 2016 / MAY 9-13 / 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, 280-293) arxiv, conference version

• June 4-19: 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
    • Introduction
    • Part 1
    • Part 2
    • Part 3
  • Alexander Shen's talk: Fixed points and subaction (blackboard)
• Computability, Randomness and Applications, June 20-24, 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)

• 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, 37-44) 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

• 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

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

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

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

• A.Shen: Talk: Automatic Complexity, High School of Economics.
• A.Shen: Introductory mini-course on complexity for undergraduate students (HSE)

2017

• 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 space-bounded algorithms" submitted (Update: accepted) to CSR 2017 conference arxiv

• February 16: A.Shen: Normal numbers and Automatic Complexity, talk at Mathematics Department, Strasbourg University talk slides arxiv
• Feb. 19-24: 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 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 2x-1 \)) arxiv
• A.Romashchenko: STACS 2017 talk (with Dmitry Itsykson, Alexander Knop, Dmitry Sokolov) pdf (HAL archive)

• Bruno Durand, Andrei Romashchenko, "On the expressive power of quasiperiodic SFT" (submitted), arxiv
• D.Musatov (Moscow, MIPT) visit: 21 April - 30 May

• 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 space-bounded algorithms", talk slides
• A.Shen: Visit to St.Petesbourg (Steklov Institute, laboratory of mathematical logic), 19 juin-5 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 shift-invariant maximal filters and hormonal cellular automata, talk at LICS 2017, doi, HAL

• July 2-8: Computability, complexity and randomness 2017 (Mysore, India) , A.Milovanov (RaCAF visitor) talk: slides
• July 6-9 Computation Complexity Conference 2017, A.Milovanov (RaCAF visitor) and N.Vereshchagin (RaCAF visitor) talk "Stochasticity in Algorithmic Statistics for Polynomial Time", proceedings
• July 10-14, ICALP (Warsaw), Olivier Bournez (with A.Pouly) talk "A Universal Ordinary Differential Equation", pdf

• 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 (21-25 August) B.Durand, A.Romashchenko, "On the expressive power of quasiperiodic SFTs", arxiv pdf, conference version, talk

• A.Shen: FCT 2017 conference, Bordeaux, site; slides
• Intermediate report (with publications list)
• Dimension 1 sequences are close to randoms (N.Greenberg, J.Miller, A.Shen, L.Westrick) arxiv preprint, accepted for publication in Theoretical Computer Science

• 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
• 20-24 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. 165-170. pdf

• 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 Yao-Blum-Micali 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

• 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

• 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

• 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 space-bounded algorithms" published by Theory of Computing Systems reprint

• March 4: A.Romashchenko (with M.Zimand) "An operational characterization of mutual information in algorithmic information theory" accepted by ECCC TR18-043
• 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)

• 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

• 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, Resource-Bounded 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

• 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

• 2-3 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
• 9-13 July: A.Shen, invited talk at a school "Mathematical physics of non-periodic structures" (on fixed-point 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

• 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 time-bounded algorithms" paper
• 14 august: G.Posobin, A.Shen, Random noise increases Kolmogorov complexity and Hausdorff dimension, submitted to arxiv
• 27-31 August: Mathematical Foundations of Computer Science, 2018 (Liverpool) site
  • A.Shen, Mikhail Andreev (RaCAF visitor), Plain stopping time and conditional complexities revisited paper, talk

• 1-15 September: A.Shen's visit to Poncelet laboratory (Moscow)
  • 3-4 September: Anniversary conference program talk "Three approaches to the quantitative definition of information"
  • Kolmogorov seminar talk: Kolmogorov complexity and games
  • 14-15 September: Mathematics Education Workshop (Moscow 57th school)
• A.Shen's paper on algorithms of geometric constructions is published by Mathematical Intelligencer shareable link

• D.Musatov (RaCAF visitor), "Approximate Coalitional Equilibria in the Bipolar World", joint work with Andrei Golman, OPTIMA 2018, CCIS 974 Proceedings, Springer pdf

• 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 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 (Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts) accepted

2019

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

• Ruslan Ishkuvatov, RaCAF CDD research engineer (2019) joined RaCAF team in Montpellier
• A.Milovanov (RaCAF visitor) paper "#P-completeness of counting roots of a sparse polynomial" accepted by Information Processing Letters, Volume 142, February 2019, Pages 77-79, 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 Analog-Digital Programs" (CMSB 2017)

• 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 (Resource-Bounded 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

• Visit of Alexander Smal (POMI RAS, St.Petersburg)
• Revised version of paper by A.Romashchenko and M.Zimand submitted to JACM, arxiv version
• April 1-12: A.Romashchenko, visit to Moscow, Higher School of Economics: mini-course on secret sharing, talk on Shannon entropy in combinatorial problems slides

• 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 9-11 A.Shen, participation in Russian Workshop on Complexity and Model Theory, MIPT, Moscow
• June 12-14 A.Shen, participation in Randomness, Information, Complexity, (A.Romashchenko, organizer) , G.Posobin (RaCAF visitor) talk: slides

• July 7-12: 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. 1377-1381 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 1-10: A.Milovanov's visit
• August 11-15: Logic Colloquium (Prague), A.Shen: special session organizer, L.Bienvenu: invited speaker
• August 19-23: Andrei Romashchenko: invited speaker at the Memorial Workshop dedicated to Frantisek Matus, see talk

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

• 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"),
  13-37.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 - 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, bitbabbler-dbg 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) 13-37.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 25-27: GDR Computability and RaCAF meeting: villa Finaly (Florence). Talk by A.Shen slides : Random btis in practice and theory
• November 30: Random bits in practice and theory (RaCAF project findings, Moscow) slides

• 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 non-randomness 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

• Paper by Bruno Durand and Andrei Romashchenko "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 poster

February 28: Institute Henri Poincare: Complexity and a priori probability (A.Shen's talk), Learning theory tutorial (L.Bienvenu's talk) program

• April 6, 8: A.Romashchenko's talk on spectral analysis of common information (Kolmogorov seminar) slides
• Complexity of majorants (A.Shen) arxiv
• April 26: A.Shen's talk on random generators and their testing (RaCAF findings) at Computer Science seminar, St.Petersbourg (Russia, online) pdf

• Yurifest: conference dedicated to the anniversary of Yury Gurevich talk slides (A.Shen)
  Report of RaCAF (A.Shen): Randomness Tests: Theory and Practice. LNCS 12180, 258-290 (2020) pdf

• August 6: Mathematical works of Vladimir A. Uspensky: A commentary (A.Shen) arxiv
• August 10-14: American Institute of Mathematics Randomness workshop announcement
  Finite-state algorithmic information theory and normal numbers (A.Shen, A.Kozachinskiy, R.Ishkuvatov) slides
• August 18: popular talk about cryptography (in Russian) board notes
• August 20: What is randomness (popular lecture for high school students, SIGMACAMP, US (online) board notes
• August 24: an extended version of the paper "Automatic Kolmogorov complexity, normality and finite state dimension revisited" arxiv
• August 24-28: 45th International Symposium on Mathematical Foundations of Computer Science 2020, Prague (online this year). E.Gürpinar presented the paper "Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory", a joint work with A.Romashchenko, see proceedings and an extended version on arXiv

Final version of the paper "Automatic Kolmogorov complexity, normality and finite state dimension revisited" submitted to JCSS.

• October 20: A.Romashchenko, A.Shen (with Peter Gacs): Inequalities for space-bounded complexity, arxiv
• October 21: Space-bounded complexity (ESCAPE talk, online) board

• December 16: ESCAPE talk: unexpected drill paradox and second Goedel theorem (Raz, Kritchman) board
• Paper: "Automatic Kolmogorov complexity, normality and finite state dimension revisited" accepted by JCSS

2021

January 6: JCSS publication (A.Kozachinskiy, A.Shen, Automatic Kolmogorov complexity, normality and finite-state dimension revisited) appeared online final journal version (JCSS, 118, june 2021, 75-107)

Software tools for:
• spectral testing (eigenvalues of random graphs)
• Kolmogorov-Smirnov two-sample exact computation
• Robust tests using reference generator
• Auxiliary tools (files conversion, graphic tools)

Final month of the project
• Preparing a final report (103 pp.)
• Software tools github repository zip file