A. Rumyantsev

most citedInfinite computable version of Lovasz Local Lemma

5 citations · 9 across the 5 of their papers we have counts for

collaborators

5 papers

cs.DS2010★ 5 cited

Infinite computable version of Lovasz Local Lemma

Andrey Rumyantsev

Lovász Local Lemma (LLL) is a probabilistic tool that allows us to prove the existence of combinatorial objects in the cases when standard probabilistic argument does not work (the…

math.CO2010

Kolmogorov complexity, Lovasz local lemma and critical exponents

Andrey Rumyantsev

D. Krieger and J. Shallit have proved that every real number greater than 1 is a critical exponent of some sequence. We show how this result can be derived from some general statem…

math.CO2010

Forbidden substrings, Kolmogorov complexity and almost periodic sequences

Andrey Rumyantsev, Maxim Ushakov

Assume that for some $α < 1$ and for all nutural $n$ a set $F_{n}$ of at most $2^{α n}$ "forbidden" binary strings of length $n$ is fixed. Then there exists an infinite binary sequence…

math.CO2010★ 3 cited

Everywhere complex sequences and probabilistic method

Andrey Rumyantsev

The main subject of the paper is everywhere complex sequences. An everywhere complex sequence is a sequence that does not contain substrings of Kolmogorov complexity less than $αn-…

math.CO2010★ 1 cited

Upper bound for the generalized repetition threshold

Andrey Rumyantsev

Let $A$ be an $a$ -letter alphabet. We consider fractional powers of $A$ -strings: if $x$ is a $n$ -letter string, $x^{r}$ is a prefix of $xxxx ...$ having length $n r$ . Let $l$ be a posi…