Book

B. Monin, L. Patey Calculabilité
Calvage et Mounet

Abstract : We survey the main results of computability, algorthmic randomness, reverse mathematics and higher computability


Book Chapter

B. Monin Higher randomness
Lecture notes in logic : Algorithmic Randomness : Progress and Prospects, to appear
[PDF]

Abstract : We survey the main results in the field of Higher randomness, especially on Pi11-randomness and Delta11-randomness and classes in between.

Journal papers

L. Bienvenu, N. Greenberg, B. Monin Bad oracles in higher computability and randomness
Israel Journal of mathematics, to appear
[PDF]

Abstract : Computations and c.e. operators are continuous processes, but their higher analogues are not. If A hyperarithmetically computes B, any bit of B may depend on infinitely many bits of A. We investigate continuous restrictions of higher computations, and the oracles which are ill-behaved with respect to these restrictions. Our main result is the construction of an oracle A such that there is no universal Martin-Löf test which is continuously Pi11 in A.

B. Monin, A. Nies Muchnik degrees and cardinal characteristics
Journal of Symbolic Logic, 4 sept. 2020, Accepted manuscript, p. 1-28.
[PDF]

Abstract : Let IOE(F) be the set of functions which equals infinitely often every computable function bounded by F. Let AED(F) be the dual notion : the set of functions which differs almost everywhere from every computable function bounded by F. We study the connection between the Medvedev and Muchnik degrees of the classes IOE(F) and AED(F), with respect to Coarse computability and with respect to set theory and cardinal characteristics. We also use a new forcing notion with trees, to show that for any computable F, there exists a computable G > F such that IOE(F) is strictly Muchnik below IOE(G).

B. Monin, L. Patey Pigeons do not jump high
Advances in Mathematics, 2019, vol. 352, p. 1066-1095
[PDF]

Abstract : We show that for any set A of integers, there is an infinite subset of A or of the complement of A which is not of high degree. We use for that a new forcing notion which is an enhancement of computable Mathias forcing, in order to control the truth of the double jump. We discuss the implications in reverse mathematics, and we use our forcing notion to give a simple proof of Liu's theorem, that RT22 does not imply WKL.

P.E. Angles d'Auriac, B. Monin Genericity and randomness with ITTMs
Journal of Symbolic Logic, 2019, vol. 84, p. 1670-1710
[PDF]

Abstract : We study genericity and randomness with respect to infinite time Turing machines. To do so, we develop a framework to study randomness in Godel's constructible hierarchy. We then answer several open questions, and ask a new one : does randomness over L_Sigma coincinde with ITTM-randomness?

L. Liu, B. Monin, L. Patey A computable analysis of variable word theorems
Proceedings of the American Mathematical Society, 2019, vol. 147, p. 823-834
[PDF]

Abstract : The variable word theorem asserts that given any finite coloring of the strings, there is an infinite sequence with infinitely many variables such that for every valuation, some specific set of initial segments is homogeneous. We show that the variable word theorem is provable in ACA.

B. Monin, L. Patey Pi^0_1 encodability and omniscient reduction
Notre Dame Journal of Formal Logic, 2019 vol. 60, n. 01, p. 1-12
[PDF]

Abstract : We introduce the notion of omniscient reduction to study the structural difference of mathematical theorems. We show that WWKL is not omnisciently reducible to Ramsey's theorem, answering a quesiton of Hirschfeldt and Jockusch.

L. Bienvenu, S. Figueira, B. Monin, A. Shen Algorithmic identifiation of probabilities is hard
Journal of Computer and System Sciences, 2018, vol. 95, p. 98-108
[PDF]

Abstract : Suppose that we are given an infinite binary sequence which is random for a Bernoulli measure of parameter p. By the law of large numbers, the frequency of zeros in the sequence tends to p, and thus we can get better and better approximations of p as we read the sequence. We study in this paper a similar question, but from the viewpoint of inductive inference. We suppose now that p is a computable real, and one asks for more: as we are reading more and more bits of our random sequence, we have to eventually guess some specific algorithm which computes p. Can one do such a thing uniformly for all sequences that are random for computable Bernoulli measures, or even for a "large enough" fraction of them? In this paper, we give a negative answer to this question.

N. Greenberg, J. Miller, B. Monin, D. Turetsky Two More characterizations of K-triviality
Notre Dame Journal of Formal Logic, 2018, vol. 59, n. 02, p. 189-195
[PDF]

Abstract : We give new characterizations of K-triviality. In particular, we show that if for all Y such that Chaitin's Omega is Y-random, Omega is (Y+A)-random, then A is K-trivial. The proof uses a new cupping result : we prove that if A is not LR below B, then for every set X there is a B-random set Y such that X is computable from Y+A.

N. Greenberg, B. Monin Higher randomness and genericity
Forum of mathematics, Sigma, 2017, vol. 5, e. 31
[PDF]

Abstract : We show in particular that sets which are low for Delta11 randomness are exactly the Delta11 sets, answering a long-standing open questions. We give a detailed study of various aspects of Pi11-randomness. We also study Sigma11-genericity and show its numerous connections and difference with Pi11-randomness. We also ask the question of lowness for Sigma11-genericity.

L. Bienvenu, N. Greenberg, B. Monin Continuous Higher randomness
Journal of Mathematical Logic, 2017, vol. 17, n. 01, p. 1750004
[PDF]

Abstract : We investigate the role of continuous reductions and continuous relativisation in the context of higher randomness. We give answer a long standing open question by giving a separation between higher weak-2-randomness and Pi11-randomness.

B. Monin Higher randomness and forcing with closed sets
Theory of computing system, 2017, vol. 60, n. 03, p. 421-437
[PDF]

Abstract : We show that a real is Pi11-random iff it is 1-generic for the topology generated by Sigma11-closed sets of positive measure. In particular the class of Pi11-random reals is Pi03 boldface.

Conference papers

B. Monin An answer to the Gamma question
(formerly "Asymptotic density and error-correcting codes") LICS 2018
Proceedings of the 33rd Annual IEEE Symposium on LICS, p. 730-738
[PDF]

Abstract : We solve an open question, showing that coarse computability induces a trichotomy in the Turing degree : we have the computable degree, Turing degrees in which the bit of every set can be correctly guessed by a program with probability 1/2 (and not above), and Turing degrees containing sets on which any program will incorrectly guess almost every of its bits for infinitely many of its prefixes. There are no other Turing degrees.

P.E. Angles d'Auriac, B. Monin Another characterization of the higher K-Trivials
MFCS 2017
Leibniz international proceedings in informatics, vol. 83
[PDF]

Abstract : We provide a new characterisation of the non Delta11 higher K-trivial sets.

B. Monin, A. Nies A unifying approach to the Gamma question
LICS 2015
Proceedings of the 30th Annual IEEE Symposium on LICS, p. 585-596
[PDF]

Abstract : We generalise the previous known exemples of sets with a Gamma value of 0, providing also new exemples of such sets. We also generalise the previous known exemples of sets with a Gamma value of 1/2, also providing more examples of such sets

L. Bienvenu, B. Monin, A. Shen Algorithmic identifiation of probabilities is hard
ALT 2014
International Conference on Algorithmic Learning Theory, p. 85-95, Springer
[PDF]

Abstract : Suppose that we are given an infinite binary sequence which is random for a Bernoulli measure of parameter p. By the law of large numbers, the frequency of zeros in the sequence tends to p, and thus we can get better and better approximations of p as we read the sequence. We study in this paper a similar question, but from the viewpoint of inductive inference. We suppose now that p is a computable real, and one asks for more: as we are reading more and more bits of our random sequence, we have to eventually guess some specific algorithm which computes p. Can one do such a thing uniformly for all sequences that are random for computable Bernoulli measures, or even for a "large enough" fraction of them? In this paper, we give a negative answer to this question.

B. Monin Higher randomness and forcing with closed sets
STACS 2014
Leibniz international proceedings in informatics, vol. 25
[PDF]

Abstract : We show that a real is Pi11-random iff it is 1-generic for the topology generated by Sigma11-closed sets of positive measure. In particular the class of Pi11-random reals is Pi03 boldface.

L. Bienvenu, B. Monin von Neumann's biased coin revisited
LICS 2012
Proceedings of the 27th Annual IEEE Symposium on LICS, p. 145-154
[PDF]

Abstract : A learnable class of measure is a class such that any sequence which is random for some measure in the class can compute one of the measure of the class it is random for. We show that the classes of Bernoulli measures and of Markov measures with fixed memory are learnable. We show how to use this to compute uniform random sequences from sequences which are random for an unkown probability measure.

Submitted

P-E Anglès d'Auriac, P. Cholak, D. Dzhafarov, B. Monin, L. Patey Milliken's tree theorem and its applications : a computability-theoretic perspective
[PDF]

Abstract : We investigate various infinite combinatorial results from the viewpoint of reverse mathematics.

B. Monin, L. Patey SRT22 does not imply COH omega-models
[PDF]

Abstract : We answer a long standing open question by showing that SRT22 does not imply COH omega-models.

B. Monin, L. Patey The weakness of the pigeonhole principle under hyperarithmetical reductions
[PDF]

Abstract : We show how to extends coputable Mathias forcing to control arbitrary computable iteration of the jump. We use that to show that for any set A, there is an infinite subset of A or of its complement which does not hyperarthmetically compute Kleene's O.

B. Monin, L. Yu On the Borelness of upper cones of hyperdegrees
[PDF]

Abstract : We show that for any X, The set {Y : Y hypearithmetically compute X} is Borel if and only if X is constructible.

Misc

Hdr Report : Mathias Forcing and the Ramsey theorem for pairs
[PDF]

PhD Report : Higher computability and randomness
[PDF]

Book in french (work in progress) : Calculabilité
[PDF]