### Article

## The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a, b} and a⊗b=a+b. Let A be a tropical matrix and k a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^{m×k} and C∈R^{k×n} satisfying B⊗C=A. We show that no algorithm for TMF is likely to work in polynomial time for every fixed k, thus resolving a problem proposed by Barvinok in 1993.

This book constitutes the proceedings of the 13th International Computer Science Symposium in Russia, CSR 2018, held in Moscow, Russia, in May 2018.

The 24 full papers presented together with 7 invited lectures were carefully reviewed and selected from 42 submissions. The papers cover a wide range of topics such as algorithms and data structures; combinatorial optimization; constraint solving; computational complexity; cryptography; combinatorics in computer science; formal languages and automata; algorithms for concurrent and distributed systems; networks; and proof theory and applications of logic to computer science.

We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.

This volume contains the proceedings of the International Workshop on Tropical and Idempotent Mathematics, held at the Independent University of Moscow, Russia, from August 26-31, 2012. The main purpose of the conference was to bring together and unite researchers and specialists in various areas of tropical and idempotent mathematics and applications. This volume contains articles on algebraic foundations of tropical mathematics as well as articles on applications of tropical mathematics in various fields as diverse as economics, electroenergetic networks, chemical reactions, representation theory, and foundations of classical thermodynamics. This volume is intended for graduate students and researchers interested in tropical and idempotent mathematics or in their applications in other areas of mathematics and in technical sciences

We investigate the Kapranov rank functions of tropical matrices for different ground fields. For any infinite ground field we show that the rank-product inequality holds for Kapranov rank, and we prove that the Kapranov rank respects Green’s preorders on the semigroup of tropical *n*-by-*n *matrices. The rank-product inequality is shown to fail for Kapranov rank over any finite ground field. We provide an example of a 7-by-7 01-matrixwhose Kapranov rank is independent of a ground field, equals 6, and exceeds tropical rank.

We present an example of a 6x6 matrix A with tropical rank equal to 4 and Kapranov rank equal to 5. This disproves the conjecture formulated by M. Chan, A. Jensen, and E. Rubei.

Boolean games are an expressive and natural formalism through which to investigate problems of strategic interaction in multiagent systems. Although they have been widely studied, almost all previous work on Nash equilibria in Boolean games has focused on the restricted setting of pure strategies. This is a shortcoming as finite games are guaranteed to have at least one equilibrium in mixed strategies, but many simple games fail to have pure strategy equilibria at all. We address this by showing that a natural decision problem about mixed equilibria: determining whether a Boolean game has a mixed strategy equilibrium that guarantees every player a given payoff, is NEXP-hard. Accordingly, the epsilon variety of the problem is NEXP-complete. The proof can be adapted to show coNEXP-hardness of a similar question: whether all Nash equilibria of a Boolean game guarantee every player at least the given payoff.

We study the following computational problem: for which values of k, the majority of n bits MAJn 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 MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19+o(1). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k = O(n2/3) can compute MAJn correctly on all inputs.

We define and study the Hochschild (co)homology of the second kind (known also as the Borel-Moore Hochschild homology and the compactly supported Hochschild cohomology) for curved DG categories. An isomorphism between the Hochschild (co)homology of the second kind of a CDG-category B and the same of the DG category C of right CDG-modules over B, projective and finitely generated as graded B-modules, is constructed. Sufficient conditions for an isomorphism of the two kinds of Hochschild (co)homology of a DG-category are formulated in terms of the two kinds of derived categories of DG-modules over it. In particular, a kind of “resolution of the diagonal” condition for the diagonal CDG-bimodule B over a CDG-category B guarantees an isomorphism of the two kinds of Hochschild (co)homology of the corresponding DG-category C. Several classes of examples are discussed. In particular, we show that the two kinds of Hochschild (co)homology are isomorphic for the DG-category of matrix factorizations of a regular function on a smooth affine variety over a perfect field provided that the function has no other critical values but zero.

Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.