The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? We give a relativized ... more >>>

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings require Omega(sqrt(n)) bit flips. For a given m, we also give bounds for increasing ... more >>>

We introduce the study of Kolmogorov complexity with error. For a metric d, we define C_a(x) to be the length of a shortest program p which prints a string y such that d(x,y) \le a. We also study a conditional version of this measure C_{a,b}(x|y) where the task is, given ... more >>>

Let a program p on input a output b. We are looking for a shorter program p' having the same property (p'(a)=b). In addition, we want p' to be simple conditional to p (this means that the conditional Kolmogorov complexity K(p'|p) is negligible). In the present paper, we prove that ... more >>>

Solovay has proven that the minimal length of a program enumerating a set A is upper bounded by 3 times the absolute value of the logarithm of the probability that a random program will enumerate A. It is unknown whether one can replace the constant 3 by a smaller constant. ... more >>>

We invistigate what is the minimal length of a program mapping A to B and at the same time mapping C to D (where A,B,C,D are binary strings). We prove that it cannot be expressed in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C), ..., their triples (A,B,C), ... more >>>

We define Kolmogorov complexity of a set of strings as the minimal Kolmogorov complexity of its element. Consider three logical operations on sets going back to Kolmogorov and Kleene: (A OR B) is the direct sum of A,B, (A AND B) is the cartesian product of A,B, (A --> B) ... more >>>

We study different notions of descriptive complexity of computable sequences. Our main result states that if for almost all n the Kolmogorov complexity of the n-prefix of an infinite binary sequence x conditional to n is less than m then there is a program of length m^2+O(1) that for almost ... more >>>

Assume that for almost all n Kolmogorov complexity of a string x conditional to n is less than m. We prove that in this case there is a program of size m+O(1) that given any sufficiently large n outputs x. more >>>

We present a simplified proof of Solovay-Calude-Coles theorem stating that there is an enumerable undecidable set with the following property: prefix complexity of its initial segment of length n is bounded by prefix complexity of n (up to an additive constant). more >>>

A string $p$ is called a program to compute $y$ given $x$ if $U(p,x)=y$, where $U$ denotes universal programming language. Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$ is defined as minimum length of a program to compute $y$ given $x$. Let $K(x)$ denote $K(x|\text{empty string})$ (Kolmogorov complexity of $x$) ... more >>>

The very first Kolmogorov's paper on algorithmic information theory was entitled `Three approaches to the definition of the quantity of information'. These three approaches were called combinatorial, probabilistic and algorithmic. Trying to establish formal connections between combinatorial and algorithmic approaches, we prove that any linear inequality involving Kolmogorov complexities could ... more >>>

Assume that A, B are finite families of n-element sets. We prove that there is an element that simultaneously belongs to at least |A|/2n sets in A and to at least |B|/2n sets in B. We use this result to prove that for any inconsistent DNF's F,G with OR of ... more >>>

It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones (N.~Nisan, SIAM Journal on Computing, 20(6):999--1007, 1991). Motivated by a question if randomization can significantly speed up a nondeterministic computation via a boolean decision tree, we address structural properties of Arthur-Merlin games in ... more >>>