# Publications

We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most *N*, where the number *N* depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on *N* that, in the special case of algebras with more than (|A|2)(|A|2) basic operations, improves an earlier result of K. Kearnes and Á. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a *k*-ary near unanimity operation if and only if it contains a *k*-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.

Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obtain a number of sufficient conditions for membership in AC0, L, NL, and P. Our main result is a complete syntactic AC0/NL/P/CONP tetrachotomy of path queries under the assumption that the covering classes are disjoint.

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. The standard way to parameterize interesting subclasses of the constraint satisfaction problem is via finite constraint languages. The main problem is to classify those subclasses that are solvable in polynomial time and those that are NP-complete. It was conjectured that if a constraint language has a weak near-unanimity polymorphism then the corresponding constraint satisfaction problem is tractable; otherwise, it is NP-complete.

In the article, we present an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture.

A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding 1-Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of 1-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.

We study the algorithmic complexity of solving subtraction games in a fixed dimension with a finite difference set. We prove that there exists a game in this class such that solving the game is (formula presented)-complete and requires time (formula presented), where n is the input size. This bound is optimal up to a polynomial speed-up. The results are based on the construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata. © Springer Nature Switzerland AG 2020.

This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation m that satisfies the minority equations m(y,x,x)≈m(x,y,x)≈m(x,x,y)≈y . We show that a common polynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.

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 consider the notion of information distance between two objects x and y introduced by Bennett, Gács, Li, Vitanyi, and Zurek [C. H. Bennett et al., 1998] as the minimal length of a program that computes x from y as well as computing y from x, and study different versions of this notion. In the above paper, it was shown that the prefix version of information distance equals max (K(x|y),K(y|x)) up to additive logarithmic terms. It was claimed by Mahmud [Mahmud, 2009] that this equality holds up to additive O(1)-precision. We show that this claim is false, but does hold if the distance is at least logarithmic. This implies that the original definition provides a metric on strings that are at superlogarithmically separated.

A major goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems *f*:({0, 1}^*n*)^*k* → {0, 1} with *k* > log *n* parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every *k* ≥ log *n*, showing in both cases that Θ(1 + ⌈log *n*⌉/ log ⌈1 + *k*/ log *n*⌉) bits are necessary and sufficient. In particular, these problems admit constant-cost protocols if and only if the number of parties is *k* ≥ *n*ϵ for some constant ϵ > 0.

In this paper we study decision tree models with various types of queries. For a given function it is usually not hard to determine the complexity in the standard decision tree model (each query evaluates a variable). However in more general settings showing tight lower bounds is substantially harder. Threshold functions often have non-trivial complexity in such models and can be used to provide interesting examples.

Standard decision trees can be viewed as a computational model in which each query depends on only one input bit. In the first part of the paper we consider natural generalization of standard decision tree model: we address decision trees that are allowed to query any function depending on two input bits. We show the first lower bound of the form n−o(n)n−o(n) for an explicit function (namely, the majority function) in this model. We also show that in the decision tree model with AND and OR queries of arbitrary fan-in the complexity of the majority function is n−1n−1.

In the second part of the paper we address parity decision trees that are allowed to query arbitrary parities of input bits. There are various lower bound techniques for parity decision trees complexity including analytical techniques (degree over F2F2, Fourier sparsity, granularity) and combinatorial techniques (generalizations of block sensitivity and certificate complexity). These techniques give tight lower bounds for many natural functions. We give a new inductive argument tailored specifically for threshold functions. A combination of this argument with granularity lower bound allows us to provide a simple example of a function for which all previously known lower bounds are not tight.

We consider the game of proper NIM, in which two players alternately move by taking stones from *n* piles. In one move a player chooses a proper subset (at least one and at most n−1n−1) of the piles and takes some positive number of stones from each pile of the subset. The player who cannot move is the loser. Jenkyns and Mayberry (Int J Game Theory 9(1):51–63, 1980) described the Sprague–Grundy function of these games. In this paper we consider the so-called selective compound of proper NIM games with certain other games, and obtain a closed formula for the Sprague–Grundy functions of the compound games, when n≥3n≥3. Surprisingly, the case of n=2n=2 is much more complicated. For this case we obtain several partial results and propose some conjectures.

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 give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Γ, QCSP(Γ), where Γ is a finite language over 3 elements which contains all constants. In particular, such problems are either in P, NP-complete, co-NP-complete or PSpace-complete. Our classification refutes the hitherto widely-believed Chen Conjecture.

Additionally, we show that already on a 4-element domain there exists a constraint language Γ such that (Γ) is DP-complete (from Boolean Hierarchy), and on a 10-element domain there exists a constraint language giving the complexity class Θ2*P*.

Meanwhile, we prove the Chen Conjecture for finite conservative languages Γ. If the polymorphism clone of such Γ has the polynomially generated powers (PGP) property then QCSP(Γ) is in NP. Otherwise, the polymorphism clone of Γ has the exponentially generated powers (EGP) property and QCSP(Γ) is PSpace-complete.

Consider the following one-player game. Take a well-formed sequence of opening and closing brackets (a Dyck word). As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its width: the maximum number of nonempty segments of symbols (separated by blank space) seen during the play.

For various initial sequences, we prove upper and lower bounds on the minimum width sufficient for re-pairing. (In particular, the sequence associated with the complete binary tree of height n admits a strategy of width sub-exponential in log n.) Our two key contributions are (1) lower bounds on the width and (2) their application in automata theory: quasi-polynomial lower bounds on the translation from one-counter automata to Parikh-equivalent nondeterministic finite automata. The latter result answers a question by Atig et al. (2016).

This special issue of Theory of Computing Systems consists of extended journal papers originally presented at the 13th International Computer Science Symposium in Russia (CSR 2018) held on June 6–10, 2018 in Moscow, Russia. The event was hosted by National Research University Higher School of Economics and chaired by Vladimir V. Podolskii. Preliminary versions of these papers presented at the conference appeared in LNCS 10846. The Program Committee, chaired by Fedor V. Fomin, invited several authors to submit extended journal versions of their papers to this special issue. All submissions were reviewed in accordance with customary high standards.

It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all *𝜀*<1/2, there exist no semicomputable functions that differ from N by at most *𝜀*. Moreover, for any computable function *f* such that |lim*𝑡**𝑓*(*𝑥*,*𝑦*,*𝑡*)−N(*𝑥*,*𝑦*)|≤*𝜀* and for all *n*, there exist strings *x*, *y* of length *n* such that

∑*_𝑡 *|*𝑓*(*𝑥*,*𝑦*,*𝑡*+1)−*𝑓*(*𝑥*,*𝑦*,*𝑡*)| ≥* 𝛺*(log *𝑛*)

This is optimal up to constant factors.

We also show that the maximal number of oscillations of a limit approximation of N is *𝛺*(*𝑛*/log*𝑛*). This strengthens the *𝜔*(1) lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, *Normalized information distance and the oscillation hierarchy*].

Tropical algebra emerges in many fields of mathematics such as algebraic geometry, mathematical physics and combinatorial optimization. In part, its importance is related to the fact that it makes various parameters of mathematical objects computationally accessible. Tropical polynomials play a fundamental role in this, especially for the case of algebraic geometry. On the other hand, many algebraic questions behind tropical polynomials remain open. In this paper, we address four basic questions on tropical polynomials closely related to their computational properties: Given a polynomial with a certain support (set of monomials) and a (finite) set of inputs, when is it possible for the polynomial to vanish on all these inputs? A more precise question, given a polynomial with a certain support and a (finite) set of inputs, how many roots can this polynomial have on this set of inputs? Given an integer , for which there is a set of inputs such that any nonzero polynomial with at most monomials has a non-root among these inputs? How many integer roots can have a one variable polynomial given by a tropical algebraic circuit? In the classical algebra well-known results in the direction of these questions are Combinatorial Nullstellensatz due to N. Alon, J. Schwartz-R. Zippel Lemma and Universal Testing Set for sparse polynomials, respectively. The classical analog of the last question is known as tau-conjecture due to M. Shub-S. Smale. In this paper, we provide results on these four questions for tropical polynomials.

We show that there exists a bitsequence that is not computably random for which the odd bits are computably random and the even bits are computably random relative to the odd bits.

Sequential reactive systems such as controllers, device drivers, computer interpreters operate with two data streams and transform input streams of data (control signals, instructions) into output streams of control signals (instructions, data). Finite state transducers are widely used as an adequate formal model for information processing systems of this kind. Since runs of transducers develop over time, temporal logics, obviously, could be used as both simple and expressive formalism for specifying the behavior of sequential reactive systems. However, the conventional applied temporal logics (HML, LTL, CTL, µ-calculus) do not suit this purpose well, since their formulae are interpreted over ω-languages, whereas the behavior of transducers are represented by binary relations on infinite sequences, i.e. by ω-transductions. To provide temporal logics with the ability to specify the property of transductions that characterize the behavior of reactive systems, we introduced new extensions of these logics. Two principal features distinguish these extension: 1) temporal operators are parameterized by sets of streams (languages) admissible for input, and 2) sets (languages) of expected output streams are used as basic predicates. In our previous papers we studied the expressive power and the model checking problem for Reg-LTL and Reg-CTL which are the extensions of LTL and CTL where the languages mentioned above are regular ones. We discovered that parametrization of this kind increases expressive power of temporal logics though retains the decidability of the model checking problem. Our next step in the systematic exploration of new extensions of temporal logics intended for specication and verication of sequential reactive systems is the study of the model checking problem for nite state transducers against Reg-CTL∗ formulae. In this paper we develop a model checking algorithm for Reg-CTL∗ and show that this problem is in ExpSpace.