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

Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity, and that lossless compression algorithms fall short at characterizing patterns other than statistical ones not different to entropy estimations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure $m$ calculated from the output distribution of small Turing machines. We introduce and justify finite...

This is a survey of open problems in different parts of combinatorial and additive number theory. The paper is based on lectures at the Centre de Recerca Matematica in Barcelona on January 23 and January 25, 2008.

Here we give a short survey of our new results. References to the complete proofs can be found in the text of this article and in the litterature.

We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds. To illustrate the approach we consider three problems of this type of unknown complexity that were introduced by Mahajan, Raman and Sikdar (J. Comput. Syst. Sci. 75, 2009). We show that a generalization of one of the problems and non-trivial special cases of the other two are fixed-parameter tractable.

This collection of problems and conjectures is based on a subset of the open problems from the seminar series and the problem sessions of the Institut Mitag-Leffler programme Graphs, Hypergraphs, and Computing. Each problem contributor has provided a write up of their proposed problem and the collection has been edited by Klas Markstr\"om.

In this paper we prove the existence of Sidon sets which are asymptotic bases of order 4 by using probabilistic methods.

This paper has been withdrawn. See published paper http://arxiv.org/math.HO/0512390

A sequence of non-negative integers is called a B_k sequence if all the sums of arbitrary k elements are different. In this paper, we will present a new estimation for the upper bound of B_k sequences.

We present a natural restriction of Hindman's Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman's Theorem with an...

The paper presents a course on Combinatorial Algorithms that is based on the drafts of the author that he used while teaching the course in the Department of Informatics and Applied Mathematics of Yerevan State University, Armenia from February 2007 to June 2007.