# Publications

The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence $\alpha$: $C^{0'}(\alpha )$, defined as the minimal length of a program with oracle $0'$ that prints $\alpha$, and $\MM(\alpha)$, defined as $\limsup C(\alpha_{1:n}|n)$, where $\alpha_{1:n}$ denotes the length-$n$ prefix of $\alpha$ and $C(x|y)$ stands for conditional Kolmogorov complexity. We show that $C^{0'}(\alpha )\le \MM(\alpha)+O(1)$ and $\MM(\alpha)$ is not bounded by any computable function of $C^{0'}(\alpha )$, even on the domain of computable sequences.

We establish a structure theorem for the family of Ammann A2 tilings of the plane. Using that theorem we show that every Ammann A2 tiling is self-similar in the sense of Solomyak (Discret Comput Geom 20:265–279, 1998). By the same techniques we show that Ammann A2 tilings are not robust in the sense of Durand et al. (J Comput Syst Sci 78(3):731–764, 2012).

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G=(V,E), with local rewards r:E→Z, and three types of positions: black VB, white VW, and random VR forming a partition of *V*. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when |VR|=0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper,1 we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with |VR|=O(1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in |VW|+|VB|, the maximum absolute local reward, and the common denominator of the transition probabilities.

We study the following computational problem: for which values of *k*, the majority of *n* bits MAJ*n* can be computed with a depth two formula whose each gate computes a majority function of at most *k* bits? The corresponding computational model is denoted by MAJ*k* ∘ MAJ*k*. We observe that the minimum value of *k* for which there exists a MAJ*k* ∘ MAJ*k* circuit that has high correlation with the majority of *n* bits is equal to Θ(*n*1/2). We then show that for a randomized MAJ*k* ∘ MAJ*k* circuit computing the majority of *n* input bits with high probability for every input, the minimum value of *k* is equal to *n*2/3 + *o*(1). We show a worst case lower bound: if a MAJ*k* ∘ MAJ*k* circuit computes the majority of *n* bits correctly on all inputs, then *k* ≥ *n*13/19 + *o*(1).

A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minimal) binary solutions to a linear equation (resp., inequality) with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce in this paper the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it. In particular, we obtain bounds on the size of 1-Sperner hypergraphs and their transversal hypergraphs, show that the characteristic vectors of the hyperedges are linearly independent over the reals, and prove that 1-Sperner hypergraphs are both threshold and equilizable. The study of 1-Sperner hypergraphs is motivated also by their applications in graph theory, which we present in a companion paper.

The operation of Minkowski addition of geometric figures has a discrete analog, addition of subsets of a Boolean cube viewed as a vector space over the two-element field. Subsets of the Boolean cube (or multivariable Boolean functions) form a monoid with respect to this operation. This monoid is of interest in classical discrete analysis as well as in a number of problems related to information theory. We consider several complexity aspects of this monoid, namely structural, algorithmic, and algebraic.

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from “classical” algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 10).

t is known (from *Counting curves and their projections* by Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski [1, part 4]) that counting the number of points on a curve where is a sparse polynomial over

is #P-complete under randomized reductions.

We give a simple proof of a stronger result: counting roots of a sparse *univariate* polynomial over

is #P-complete under *deterministic* reductions.

Consider the following decision problem: for a given monotone Boolean function *f* decide, whether *f* is read-once. For this problem, it is essential how the input function *f* is represented. Elbassioni et al. (J. Comb. Optim. 22(3), 293–304, 2011) proved that this problem is coNP-complete when *f* is given by a depth-4 read-2 monotone Boolean formula. Gurvich (2010) proved that this problem is coNP-complete even when the input is the following expression: *C* ∨ *D**n*, where *D**n* = *x*1*y*1 ∨ … ∨ *x**n**y**n* and *C* is a monotone CNF over the variables *x*1, *y*1, … , *x**n*, *y**n*(note that this expression is a monotone Boolean formula of depth 3; in Gurvich (2010) nothing is said about the readability of *C*, but the proof is valid even if *C* is read-2 and thus the entire formula is read-3). We show that we can test in polynomial-time whether a given expression *C*∨ *D* computes a read-once function, provided that *C* is a read-once monotone CNF and *D* is a read-once monotone DNF and all the variables of *C* occur also in *D* (recall that due to Gurvich, the problem is coNP-complete when *C* is read-2). We also observe that from the so-called Sausage Lemma of Boros et al. (2009) it follows that the problem of recognizing read-once functions is coNP-complete when the input formula is depth-3 read-2.

A discrete function of n variables is a mapping g:X1×…×Xn→A, where X1,…,Xn, and A are arbitrary finite sets. Function g is called *separable* if there exist n functions gi:Xi→A for i=1,…,n, such that for every input x1,…,xn the function g(x1,…,xn) takes one of the values g1(x1),…,gn(xn). Given a discrete function g, it is an interesting problem to ask whether g is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of n variables is known only for n=2. In this paper we will show that a slightly more general recognition problem, when g is not fully but only partially defined, is NP-complete for n≥3. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for n≥4.

The general recognition problem contains the above mentioned special case for n=2. This case is well-studied in the context of game theory, where (separable) discrete functions of n variables are referred to as (assignable) n-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of nvariables for any n, thus generalizing the above result known for n=2. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function g of nvariables one can construct separating functions g1,…,gn in polynomial time with respect to the size of the input function.

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 EXPNP, or even in EXP that are not computable by polynomial size circuits and hence are not reducible to a sparse set. In this paper we study this question in a more restricted setting: what is the computational complexity of sparse sets that are *selfreducible*? It follows from earlier work of Lozano and Torán (in: Mathematical systems theory, 1991) that EXPNP does not have sparse selfreducible hard sets. We define a natural version of selfreduction, tree-selfreducibility, and show that NEXP does not have sparse tree-selfreducible hard sets. We also construct an oracle relative to which all of EXP is reducible to a sparse tree-selfreducible set. These lower bounds are corollaries of more general results about the computational complexity of sparse sets that are selfreducible, and can be interpreted as super-polynomial circuit lower bounds for NEXP.

We consider a generalization of the classical game of Nim called hypergraph Nim. Given a hypergraph H on the ground set V={1,…,n} of *n* piles of stones, two players alternate in choosing a hyperedge H∈H and strictly decreasing all piles i∈H. The player who makes the last move is the winner. In this paper we give an explicit formula that describes the Sprague-Grundy function of hypergraph Nim for several classes of hypergraphs. In particular we characterize all 2-uniform hypergraphs (that is graphs) and all matroids for which the formula works. We show that all self-dual matroids are included in this class.

We consider a generalization of the classical game of Nim called hypergraph Nim. Given a hypergraph H on the ground set V={1,…,n} of *n* piles of stones, two players alternate in choosing a hyperedge H∈H and strictly decreasing all piles i∈H. The player who makes the last move is the winner. In 1980 Jenkyns and Mayberry obtained an explicit formula for the Sprague–Grundy function of the hypergraph Nim whose hypergraph contains as the hyperedges all proper subsets of *V* (that is, all except ∅ and *V* itself). Somewhat surprisingly, the same formula works for a very wide family of hypergraphs. In this paper we characterize symmetric hypergraphs in this family.

In this paper we provide two equivalent characterizations of the notion of finite-state dimension introduced by Dai, Lathrop, Lutz and Mayordomo [7]. One of them uses Shannon’s entropy of non-aligned blocks and generalizes old results of Pillai [12] and Niven – Zuckerman [11]. The second characterizes finite-state dimension in terms of superadditive functions that satisfy some calibration condition (in particular, superadditive upper bounds for Kolmogorov complexity). The use of superadditive bounds allows us to prove a general sufficient condition for normality that easily implies old results of Champernowne [5], Besicovitch [1], Copeland and Erdös [6], and also a recent result of Calude, Staiger and Stephan [4].

We show that the inequality H(A|B, X) + H(A|B, Y) ≤ H(A|B) for jointly distributed random variables A, B, X, Y, which does not hold in general case, holds under some natural condition on the support of the probability distribution of A, B, X, Y. This result generalizes a version of the conditional Ingleton inequality: if for some distribution I(X : Y|A) = H(A|X, Y) = 0, then I(A : B) ≤ I (A : B|X) + I(A : B|Y)+I(X : Y). We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K colors so that each two edges sharing a vertex have different colors and for each pair (left vertex x, right vertex y) there is at most one color a such both x and y are incident to edges with color a; assume further that the degree of each left vertex is at least L and the degree of each right vertex is at least R. Then K LR. The second application is a new method to prove lower bounds for biclique cover of bipartite graphs.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice as is because Kolmogorov complexity is not computable.

In recent years resource-bounded algorithmic statistics were created [7, 8]. In this paper we prove a polynomial-time version of the following result of ‘classic’ algorithmic statistics.

Assume that some data were obtained as a result of some unknown experiment. What kind of data should we expect in similar situation (repeating the same experiment)? It turns out that the answer to this question can be formulated in terms of algorithmic statistics [6]. We prove a polynomial-time version of this result under a reasonable complexity theoretic assumption. The same assumption was used by Antunes and Fortnow [1].

We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real εε, let us call a stochastic game εε-ergodic, if its values from any two initial positions differ by at most εε. The proposed new algorithm outputs for every ε>0ε>0 in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an εε-range, or identifies two initial positions *u* and *v* and corresponding stationary strategies for the players proving that the game values starting from *u* and *v* are at least ε/24ε/24 apart. In particular, the above result shows that if a stochastic game is εε-ergodic, then there are stationary strategies for the players proving 24ε24ε-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (Stochastic games with finite state and action spaces. PhD thesis, Centrum voor Wiskunde en Informatica, Amsterdam, 1980) claiming that if a stochastic game is 0-ergodic, then there are εε-optimal stationary strategies for every ε>0ε>0. The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.