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

This is a survey of using Minsky machines to study algorithmic problems in semigroups, groups and other algebraic systems.

The technique of guessing can be very fruitful when dealing with sequences which arise in practice. This holds true especially when guessing is performed algorithmically and efficiently. One highly useful tool for this purpose is the package named $\texttt{gfun}$ in the software Maple. In this text we explore and explain some of $\texttt{gfun}$'s possibilities and illustrate them on two examples from recent mathematical research by the author and his collaborators.

This paper has been merged with arXiv:0908.3765

We give polynomial-time randomized algorithms for computing the girth and the cogirth of binary matroids that are low-rank perturbations of graphic matroids.

Extremal Combinatorics is among the most active topics in Discrete Mathematics, dealing with problems that are often motivated by questions in other areas, including Theoretical Computer Science and Information Theory. This paper contains a collection of problems and results in the area, including solutions or partial solutions to open problems suggested by various researchers. The topics considered here include questions in Extremal Graph Theory, Coding Theory and Social Cho...

We establish a lower bound of 2/p(p-1) for the asymptotic density of the Motzkin numbers divisible by a general prime number p > 3. We provide a criteria for when this asymptotic density is actually 1. We also provide a partial characterisation of those Motzkin numbers which are divisible by a prime p > 3. All results are obtained using the automata method of Rowland and Yassawi.

The Frobenius number $g(S)$ of a set $S$ of non-negative integers with $\gcd 1$ is the largest integer not expressible as a linear combination of elements of $S$. Given a sequence ${\bf s} = (s_i)_{i \geq 0}$, we can define the associated sequence $G_{\bf s} (i) = g(\{ s_i,s_{i+1},\ldots \})$. In this paper we compute $G_{\bf s} (i)$ for some classical automatic sequences: the evil numbers, the odious numbers, and the lower and upper Wythoff sequences. In contrast with the us...

We propose a new type of approximate counting algorithms for the problems of enumerating the number of independent sets and proper colorings in low degree graphs with large girth. Our algorithms are not based on a commonly used Markov chain technique, but rather are inspired by developments in statistical physics in connection with correlation decay properties of Gibbs measures and its implications to uniqueness of Gibbs measures on infinite trees, reconstruction problems and...

Zaremba's conjecture (1971) states that every positive integer number $d$ can be represented as a denominator (continuant) of a finite continued fraction $\frac{b}{d}=[d_1,d_2,...,d_{k}],$ whose partial quotients $d_1,d_2,...,d_{k}$ belong to a finite alphabet $\A\subseteq\N.$ In this paper it is proved for an alphabet $\A,$ such that the Hausdorff dimension $\delta_{\A}$ of the set of infinite continued fractions whose partial quotients belong to $\A,$ that the set of number...

We provide bounds on the compression size of the solutions to 22 problems in computer science. For each problem, we show that solutions exist with high probability, for some simple probability measure. Once this is proven, derandomization can be used to prove the existence of a simple solution.