
We introduce tropical NewtonPuiseux polynomials admitting rational
exponents. A resolution of a tropical hypersurface is defined by means of a
tropical NewtonPuiseux polynomial. A polynomial complexity algorithm for
resolubility of a tropical curve is designed. The complexity of resolubility of
tropical prevarieties of arbitrary codimensions is studied. Tropical
NewtonPuiseux rational functions are introduced, and we prove that any
tropical polynomial has a resolution in tropical NewtonPuiseux rational
functions (this can be treated as a tropical analog of the algebraic closedness
of the field of NewtonPuiseux series).

Semiring complexity is the version of arithmetic circuit complexity that
allows only two operations: addition and multiplication. We show that when the
number of variables is fixed, the semiring complexity of a Schur polynomial
$s_\lambda$ is $O(log(\lambda_1))$; here $\lambda_1$ is the largest part of the
partition $\lambda$.

We prove upper bounds on the sum of Betti numbers of tropical prevarieties in
dense and sparse settings. In the dense setting the bound is in terms of the
volume of Minkowski sum of Newton polytopes of defining tropical polynomials,
or, alternatively, via the maximal degree of these polynomials. In sparse
setting, the bound involves the number of the monomials.

The paper studies the operation $A^\perp$ of tropical orthogonalization,
applied to a subset $A$ of a vector space $({\mathbb R} \cup \{ \infty \})^n$,
and iterations of this operation. Main results include a criterion and an
algorithm, deciding whether a tropical linear prevariety is a tropical linear
variety, formulated in terms of a duality between $A^\perp$ and $A^{\perp
\perp}$. We give an example of a countable family of tropical hyperplanes such
that their intersection is not a tropical prevariety.

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.

We investigate models of the mitogenactivated protein kinases (MAPK) network,
with the aim of determining where in parameter space there exist multiple
positive steady states. We build on recent progress which combines various
symbolic computation methods for mixed systems of equalities and inequalities.
We demonstrate that those techniques benefit tremendously from a newly
implemented graph theoretical symbolic preprocessing method. We compare
computation times and quality of results of numerical continuation methods with
our symbolic approach before and after the application of our preprocessing.

We consider the problem of determining multiple steady states for positive
real values in models of biological networks. Investigating the potential for
these in models of the mitogenactivated protein kinases (MAPK) network has
consumed considerable effort using special insights into the structure of
corresponding models. Here we apply combinations of symbolic computation
methods for mixed equality/inequality systems, specifically virtual
substitution, lazy real triangularization and cylindrical algebraic
decomposition. We determine multistationarity of an 11dimensional MAPK network
when numeric values are known for all but potentially one parameter. More
precisely, our considered model has 11 equations in 11 variables and 19
parameters, 3 of which are of interest for symbolic treatment, and furthermore
positivity conditions on all variables and parameters.

For a tropical prevariety in ${R}^n$ given by a system of $k$ tropical
polynomials in $n$ variables with degrees at most $d$, we prove that its number
of connected components is less than ${k+7n1 \choose 3n} \cdot
\frac{d^{3n}}{k+n+1}$. On a number of $0$dimensional connected components a
better bound ${k+4n \choose 3n} \cdot \frac{d^n}{k+n+1}$ is obtained, which
extends the Bezout bound due to B.~Sturmfels from the the case $k=n$ to an
arbitrary $k\ge n$. Also we show that the latter bound is close to sharp, in
particular, the number of connected components can depend on $k$.

We propose a new geometric approach to describe the qualitative dynamics of
chemical reactions networks. By this method we identify metastable regimes,
defined as low dimensional regions of the phase space close to which the
dynamics is much slower compared to the rest of the phase space. Given the
network topology and the orders of magnitude of kinetic parameters, the number
of such metastable regimes is finite. The dynamics of the network can be
described as a sequence of jumps from one metastable regime to another. We show
that a geometrically computed connectivity graph restricts the set of possible
jumps. We also provide finite state machine (Markov chain) models for such
dynamic changes. Applied to signal transduction models, our approach unravels
dynamical and functional capacities of signaling pathways, as well as
parameters responsible for specificity of the pathway response. In particular,
for a model of TGF$\beta$ signalling, we find that the ratio of TGFBR1 to
TGFBR2 concentrations can be used to discriminate between metastable regimes.
Using expression data from the NCI60 panel of human tumor cell lines, we show
that aggressive and nonaggressive tumour cell lines function in different
metastable regimes and can be distinguished by measuring the relative
concentrations of receptors of the two types.

Model reduction of biochemical networks relies on the knowledge of slow and
fast variables. We provide a geometric method, based on the Newton polytope, to
identify slow variables of a biochemical network with polynomial rate
functions. The gist of the method is the notion of tropical equilibration that
provides approximate descriptions of slow invariant manifolds. Compared to
extant numerical algorithms such as the intrinsic low dimensional manifold
method, our approach is symbolic and utilizes orders of magnitude instead of
precise values of the model parameters. Application of this method to a large
collection of biochemical network models supports the idea that the number of
dynamical variables in minimal models of cell physiology can be small, in spite
of the large number of molecular regulatory actors.

We discuss a novel analysis method for reaction network systems with
polynomial or rational rate functions. This method is based on computing
tropical equilibrations defined by the equality of at least two dominant
monomials of opposite signs in the differential equations of each dynamic
variable. In algebraic geometry, the tropical equilibration problem is
tantamount to finding tropical prevarieties, that are finite intersections of
tropical hypersurfaces. Tropical equilibrations with the same set of dominant
monomials define a branch or equivalence class. Minimal branches are
particularly interesting as they describe the simplest states of the reaction
network. We provide a method to compute the number of minimal branches and to
find representative tropical equilibrations for each branch.

We discuss the symbolic dynamics of biochemical networks with separate
timescales. We show that symbolic dynamics of monomolecular reaction networks
with separated rate constants can be described by deterministic, acyclic
automata with a number of states that is inferior to the number of biochemical
species. For nonlinear pathways, we propose a general approach to approximate
their dynamics by finite state machines working on the metastable states of the
network (long life states where the system has slow dynamics). For networks
with polynomial rate functions we propose to compute metastable states as
solutions of the tropical equilibration problem. Tropical equilibrations are
defined by the equality of at least two dominant monomials of opposite signs in
the differential equations of each dynamic variable. In algebraic geometry,
tropical equilibrations are tantamount to tropical prevarieties, that are
finite intersections of tropical hypersurfaces.

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.

We discuss a method of approximate model reduction for networks of
biochemical reactions. This method can be applied to networks with polynomial
or rational reaction rates and whose parameters are given by their orders of
magnitude. In order to obtain reduced models we solve the problem of tropical
equilibration that is a system of equations in maxplus algebra. In the case of
networks with nonlinear fast cycles we have to solve the problem of tropical
equilibration at least twice, once for the initial system and a second time for
an extended system obtained by adding to the initial system the differential
equations satisfied by the conservation laws of the fast subsystem. The two
steps can be reiterated until the fast subsystem has no conservation laws
different from the ones of the full model. Our method can be used for formal
model reduction in computational systems biology.

A polynomial complexity algorithm is designed which tests whether a point
belongs to a given tropical linear variety.

Tropical differential equations are introduced and an algorithm is designed
which tests solvability of a system of tropical linear differential equations
within the complexity polynomial in the size of the system and in its
coefficients. Moreover, we show that there exists a minimal solution, and the
algorithm constructs it (in case of solvability). This extends a similar
complexity bound established for tropical linear systems. In case of tropical
linear differential systems in one variable a polynomial complexity algorithm
for testing its solvability is designed.
We prove also that the problem of solvability of a system of tropical
nonlinear differential equations in one variable is $NP$hard, and this
problem for arbitrary number of variables belongs to $NP$. Similar to tropical
algebraic equations, a tropical differential equation expresses the (necessary)
condition on the dominant term in the issue of solvability of a differential
equation in power series.

Subtractionfree computational complexity is the version of arithmetic
circuit complexity that allows only three operations: addition, multiplication,
and division.
We use cluster transformations to design efficient subtractionfree
algorithms for computing Schur functions and their skew, double, and
supersymmetric analogues, thereby generalizing earlier results by P. Koev.
We develop such algorithms for computing generating functions of spanning
trees, both directed and undirected. A comparison to the lower bound due to M.
Jerrum and M. Snir shows that in subtractionfree computations, "division can
be exponentially powerful."
Finally, we give a simple example where the gap between ordinary and
subtractionfree complexity is exponential.

We use various laws of classical physics to offer several solutions of Yao's
millionaires' problem without using any oneway functions. We also describe
several informationally secure public key encryption protocols, i.e., protocols
secure against passive computationally unbounded adversary. This introduces a
new paradigm of decoybased cryptography, as opposed to "traditional"
complexitybased cryptography. In particular, our protocols do not employ any
oneway functions.

Systems biology uses large networks of biochemical reactions to model the
functioning of biological cells from the molecular to the cellular scale. The
dynamics of dissipative reaction networks with many well separated time scales
can be described as a sequence of successive equilibrations of different
subsets of variables of the system. Polynomial systems with separation are
equilibrated when at least two monomials, of opposite signs, have the same
order of magnitude and dominate the others. These equilibrations and the
corresponding truncated dynamics, obtained by eliminating the dominated terms,
find a natural formulation in tropical analysis and can be used for model
reduction.

We show that some problems in information security can be solved without
using oneway functions. The latter are usually regarded as a central concept
of cryptography, but the very existence of oneway functions depends on
difficult conjectures in complexity theory, most notably on the notorious "$P
\ne NP$" conjecture.
In this paper, we suggest protocols for secure computation of the sum,
product, and some other functions, without using any oneway functions. A new
input that we offer here is that, in contrast with other proposals, we conceal
"intermediate results" of a computation. For example, when we compute the sum
of $k$ numbers, only the final result is known to the parties; partial sums are
not known to anybody. Other applications of our method include voting/rating
over insecure channels and a rather elegant and efficient solution of Yao's
"millionaires' problem".
Then, while it is fairly obvious that a secure (bit) commitment between two
parties is impossible without a oneway function, we show that it is possible
if the number of parties is at least 3. We also show how our (bit) commitment
scheme for 3 parties can be used to arrange an unconditionally secure (bit)
commitment between just two parties if they use a "dummy" (e.g., a computer) as
the third party. We explain how our concept of a "dummy" is different from a
wellknown concept of a "trusted third party".
We also suggest a protocol, without using a oneway function, for "mental
poker", i.e., a fair card dealing (and playing) over distance. We also propose
a secret sharing scheme where an advantage over Shamir's and other known secret
sharing schemes is that nobody, including the dealer, ends up knowing the
shares owned by any particular player.
It should be mentioned that computational cost of our protocols is negligible
to the point that all of them can be executed without a computer.

We employ tropical algebras as platforms for several cryptographic schemes
that would be vulnerable to linear algebra attacks were they based on "usual"
algebras as platforms.

Building upon works of Hironaka, BierstoneMilman, Villamayor and Wlodarczyk,
we give an a priori estimate for the complexity of the simplified Hironaka
algorithm. As a consequence of this result, we show that there exists canonical
Hironaka embedded desingularization and principalization over fields of large
characteristic (relative to the degrees of generating polynomials).

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.

We use the LitvinovMaslov correspondence principle to reduce and hybridize
networks of biochemical reactions. We apply this method to a cell cycle
oscillator model. The reduced and hybridized model can be used as a hybrid
model for the cell cycle. We also propose a practical recipe for detecting
quasiequilibrium QE reactions and quasisteady state QSS species in
biochemical models with rational rate functions and use this recipe for model
reduction. Interestingly, the QE/QSS invariant manifold of the smooth model and
the reduced dynamics along this manifold can be put into correspondence to the
tropical variety of the hybridization and to sliding modes along this variety,
respectively

Since a tropical Nullstellensatz fails even for tropical univariate
polynomials we study a conjecture on a tropical {\it dual} Nullstellensatz for
tropical polynomial systems in terms of solvability of a tropical linear system
with the Cayley matrix associated to the tropical polynomial system. The
conjecture on a tropical effective dual Nullstellensatz is proved for tropical
univariate polynomials.