
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:
1. 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?
2. 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?
3. Given an integer $k$, for which $s$ there is a set of $s$ inputs such that
any nonzero polynomial with at most $k$ monomials has a nonroot among these
inputs?
4. How many integer roots can have a one variable polynomial given by a
tropical algebraic circuit?
In the classical algebra wellknown 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.

Our concern is the overhead of answering OWL 2 QL ontologymediated queries
(OMQs) in ontologybased data access compared to evaluating their underlying
treeshaped and bounded treewidth conjunctive queries (CQs). We show that OMQs
with boundeddepth ontologies have nonrecursive datalog (NDL) rewritings that
can be constructed and evaluated in LOGCFL for combined complexity, even in NL
if their CQs are treeshaped with a bounded number of leaves, and so incur no
overhead in complexitytheoretic terms. For OMQs with arbitrary ontologies and
boundedleaf CQs, NDLrewritings are constructed and evaluated in LOGCFL. We
show experimentally feasibility and scalability of our rewritings compared to
previously proposed NDLrewritings. On the negative side, we prove that
answering OMQs with treeshaped CQs is not fixedparameter tractable if the
ontology depth or the number of leaves in the CQs is regarded as the parameter,
and that answering OMQs with a fixed ontology (of infinite depth) is
NPcomplete for treeshaped and LOGCFL for boundedleaf CQs.

We study the following computational problem: for which values of $k$, the
majority of $n$ bits $\text{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 $\text{MAJ}_k \circ
\text{MAJ}_k$. We observe that the minimum value of $k$ for which there exists
a $\text{MAJ}_k \circ \text{MAJ}_k$ circuit that has high correlation with the
majority of $n$ bits is equal to $\Theta(n^{1/2})$. We then show that for a
randomized $\text{MAJ}_k \circ \text{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
$\text{MAJ}_k \circ \text{MAJ}_k$ circuit computes the majority of $n$ bits
correctly on all inputs, then $k\geq n^{13/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(n^{2/3})$ can compute $\text{MAJ}_n$ correctly on all inputs.

We show that, for OWL 2 QL ontologymediated queries with (i) ontologies of
bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of
bounded depth and boundedleaf treeshaped conjunctive queries, and (iii)
arbitrary ontologies and boundedleaf treeshaped conjunctive queries, one can
construct and evaluate nonrecursive datalog rewritings by, respectively,
LOGCFL, NL and LOGCFL algorithms, which matches the optimal combined
complexity.

Tropical algebra is an emerging field with a number of applications in
various areas of mathematics. In many of these applications appeal to tropical
polynomials allows to study properties of mathematical objects such as
algebraic varieties and algebraic curves from the computational point of view.
This makes it important to study both mathematical and computational aspects of
tropical polynomials.
In this paper we prove a tropical Nullstellensatz and moreover we show an
effective formulation of this theorem. Nullstellensatz is a natural step in
building algebraic theory of tropical polynomials and its effective version is
relevant for computational aspects of this field.
On our way we establish a simple formulation of minplus and tropical linear
dualities. We also observe a close connection between tropical and minplus
polynomial systems.

Ontologybased data access is an approach to organizing access to a database
augmented with a logical theory. In this approach query answering proceeds
through a reformulation of a given query into a new one which can be answered
without any use of theory. Thus the problem reduces to the standard database
setting.
However, the size of the query may increase substantially during the
reformulation. In this survey we review a recently developed framework on
proving lower and upper bounds on the size of this reformulation by employing
methods and results from Boolean circuit complexity.

An integer polynomial $p$ of $n$ variables is called a \emph{threshold gate}
for a Boolean function $f$ of $n$ variables if for all $x \in \zoon$ $f(x)=1$
if and only if $p(x)\geq 0$. The \emph{weight} of a threshold gate is the sum
of its absolute values.
In this paper we study how large a weight might be needed if we fix some
function and some threshold degree. We prove $2^{\Omega(2^{2n/5})}$ lower bound
on this value. The best previous bound was $2^{\Omega(2^{n/8})}$ (Podolskii,
2009).
In addition we present substantially simpler proof of the weaker
$2^{\Omega(2^{n/4})}$ lower bound. This proof is conceptually similar to other
proofs of the bounds on weights of nonlinear threshold gates, but avoids a lot
of technical details arising in other proofs. We hope that this proof will help
to show the ideas behind the construction used to prove these lower bounds.

For matrix games we study how small nonzero probability must be used in
optimal strategies. We show that for nxn winlosedraw games (i.e. (1,0,1)
matrix games) nonzero probabilities smaller than n^{O(n)} are never needed. We
also construct an explicit nxn winlose game such that the unique optimal
strategy uses a nonzero probability as small as n^{Omega(n)}. This is done by
constructing an explicit (1,1) nonsingular nxn matrix, for which the inverse
has only nonnegative entries and where some of the entries are of value
n^{Omega(n)}.

A tropical (or minplus) semiring is a set $\mathbb{Z}$ (or $\mathbb{Z \cup
\{\infty\}}$) endowed with two operations: $\oplus$, which is just usual
minimum, and $\odot$, which is usual addition. In tropical algebra the vector
$x$ is a solution to a polynomial $g_1(x) \oplus g_2(x) \oplus...\oplus
g_k(x)$, where $g_i(x)$'s are tropical monomials, if the minimum in
$\min_i(g_{i}(x))$ is attained at least twice. In minplus algebra solutions of
systems of equations of the form $g_1(x)\oplus...\oplus g_k(x) =
h_1(x)\oplus...\oplus h_l(x)$ are studied.
In this paper we consider computational problems related to tropical linear
system. We show that the solvability problem (both over $\mathbb{Z}$ and
$\mathbb{Z} \cup \{\infty\}$) and the problem of deciding the equivalence of
two linear systems (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$)
are equivalent under polynomialtime reduction to mean payoff games and are
also equivalent to analogous problems in minplus algebra. In particular, all
these problems belong to $\mathsf{NP} \cap \mathsf{coNP}$. Thus we provide a
tight connection of computational aspects of tropical linear algebra with mean
payoff games and minplus linear algebra. On the other hand we show that
computing the dimension of the solution space of a tropical linear system and
of a minplus linear system are $\mathsf{NP}$complete.
We also extend some of our results to the systems of minplus linear
inequalities.