Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined by Andrew Yao in [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. It has been ... more >>>

The Merlin-Arthur class of languages MA is included into Arthur-Merlin class AM, and into PP. For a standard transformation of a given MA protocol with Arthur's message (= random string) of length $a$ and Merlin's message of length $m$ to a PP machine, the latter needs $O(ma)$ random bits. The ... more >>>

A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for $x$ if it looks likely that $x$ was drawn at random with respect to that distribution. In this paper, we ... more >>>

The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$, and they want to compute or approximate
more >>>

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to ... more >>>

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,
we usually do not specify how to encode instances by binary strings.
This relies on the empirical observation that the truth of a statement of the form ``CIRCUIT-SAT belongs to a complexity class $C$''
more >>>

We express some criticism about the definition of an algorithmic sufficient statistic and, in particular, of an algorithmic minimal sufficient statistic. We propose another definition, which has better properties.

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 ... 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 ... 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,
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 ... 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.

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).

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 ... 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 ... 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 ... more >>>