On a girth-free variant of the Bourgain-Gamburd machine

Recently, additive combinatorics has blossomed into a vibrant area in mathematical sciences. But it seems to be a difficult area to define - perhaps because of a blend of ideas and techniques from several seemingly unrelated contexts which are used there. One might say that additive combinatorics is a branch of mathematics concerning the study of combinatorial properties of algebraic objects, for instance, Abelian groups, rings, or fields. This emerging field has seen tremend...

We describe recent advances in the study of random analogues of combinatorial theorems.

In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are {\em algorithmically random}--there is no reason the bits should be the way they are, if we define ``reason'' to be a computable explanation smaller than the data itself. Since that time, only {\em two} explicit universal Chaitin machines have been proposed, both by Chaitin himself. ...

In this article we consider several probabilistic processes defining random grapha. One of these processes appeared recently in connection with a factorization problem in the symmetric group. For each of the probabilistic processes, we prove that the probability for the random graph to be a tree has an extremely simple expression, which is independent of most parameters of the problem. This raises many open questions.

In this paper we present several natural $q$-analogues of the poly-Bernoulli numbers arising in combinatorial contexts. We also recall some relating analytical results and ask for combinatorial interpretations.

The latest in a series of reports presenting the information-theoretic incompleteness theorems of algorithmic information theory via algorithms written in specially designed versions of LISP. Previously in this LISP code only one-character identifiers were allowed, and arithmetic had to be programmed out. Now identifiers can be many characters long, and arithmetic with arbitrarily large unsigned decimal integers is built in. This and many other changes in the software have ma...

This is the text accompanying my Bourbaki seminar on the work of Bloom and Sisask, Croot, Lev, and Pach, and Ellenberg and Gijswijt.

The following is a near complete set of notes of Bourgain's 1988 paper "Almost Sure Convergence and Bounded Entropy." Both entropy results are treated, as is one application. The proofs here are essentially those of Bourgain's.

This note is an addendum to the paper ''Mahler's method in several variables and finite automata''. It strengthens part (i) of Theorem 1.1 of the aforementioned paper.

We describe the Turing Machine, list some of its many influences on the theory of computation and complexity of computations, and illustrate its importance.