• ### Tropical Newton-Puiseux polynomials(1704.03842)

Aug. 27, 2018 math.AG
We introduce tropical Newton-Puiseux polynomials admitting rational exponents. A resolution of a tropical hypersurface is defined by means of a tropical Newton-Puiseux 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 Newton-Puiseux rational functions are introduced, and we prove that any tropical polynomial has a resolution in tropical Newton-Puiseux rational functions (this can be treated as a tropical analog of the algebraic closedness of the field of Newton-Puiseux series).
• ### On semiring complexity of Schur polynomials(1608.05043)

May 19, 2018 math.CO, cs.CC
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$.
• ### Upper bounds on Betti numbers of tropical prevarieties(1709.08594)

March 9, 2018 math.AG
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.
• ### Orthogonal tropical linear prevarieties(1803.01068)

March 2, 2018 math.AG
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 Combinatorial Nullstellensatz and Sparse Polynomials(1706.00080)

April 25, 2019 math.AG, cs.CC
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 non-zero polynomial with at most $k$ monomials has a non-root among these inputs? 4. 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.
• ### Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks(1706.08794)

June 27, 2017 cs.SC
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.
• ### A Case Study on the Parametric Occurrence of Multiple Steady States(1704.08997)

April 28, 2017 cs.SC
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 mitogen-activated 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 11-dimensional 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.
• ### Bounds on the number of connected components for tropical prevarieties(1511.06609)

Nov. 20, 2015 math.AG
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+7n-1 \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$.
• ### Geometric analysis of pathways dynamics: application to versatility of TGF-{\beta} receptors(1511.05599)

Nov. 17, 2015 q-bio.MN
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 non-aggressive tumour cell lines function in different metastable regimes and can be distinguished by measuring the relative concentrations of receptors of the two types.
• ### A geometric method for model reduction of biochemical networks with polynomial rate functions(1510.04716)

Oct. 23, 2015 q-bio.MN
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.
• ### Analysis of Reaction Network Systems Using Tropical Geometry(1508.05717)

Aug. 24, 2015 q-bio.MN
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.
• ### Symbolic dynamics of biochemical pathways as finite states machines(1504.07833)

July 5, 2015 q-bio.MN
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 Effective Primary and Dual Nullstellens\"atze(1409.6215)

June 4, 2015 math.AG, cs.SC
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 min-plus and tropical linear dualities. We also observe a close connection between tropical and min-plus polynomial systems.
• ### Model reduction of biochemical reactions networks by tropical analysis methods(1503.01414)

May 26, 2015 math.AG, q-bio.MN
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 max-plus 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.
• ### Polynomial complexity recognizing a tropical linear variety(1503.06126)

March 20, 2015 math.AG, cs.SC
A polynomial complexity algorithm is designed which tests whether a point belongs to a given tropical linear variety.
• ### Tropical differential equations(1502.08010)

Feb. 27, 2015 math.AG, cs.SC
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 non-linear 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.
• ### Subtraction-free complexity, cluster transformations, and spanning trees(1307.8425)

Sept. 28, 2014 math.CO, cs.CC
Subtraction-free 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 subtraction-free 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 subtraction-free computations, "division can be exponentially powerful." Finally, we give a simple example where the gap between ordinary and subtraction-free complexity is exponential.
• ### Yao's millionaires' problem and decoy-based public key encryption by classical physics(1312.1160)

We use various laws of classical physics to offer several solutions of Yao's millionaires' problem without using any one-way 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 decoy-based cryptography, as opposed to "traditional" complexity-based cryptography. In particular, our protocols do not employ any one-way functions.
• ### Tropicalization and tropical equilibration of chemical reactions(1303.3963)

May 27, 2013 math.AG, q-bio.MN
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.
• ### Secrecy without one-way functions(1301.5069)

Jan. 22, 2013 cs.IT, math.IT, cs.CR
We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way 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 one-way 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 one-way 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 well-known concept of a "trusted third party". We also suggest a protocol, without using a one-way 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.
• ### Tropical cryptography(1301.1195)

Jan. 7, 2013 cs.CR, math.RA
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.
• ### Effective Hironaka resolution and its Complexity (with appendix on applications in positive characteristic)(1206.3090)

June 14, 2012 math.AG
Building upon works of Hironaka, Bierstone-Milman, 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).
• ### Complexity of tropical and min-plus linear prevarieties(1204.4578)

April 20, 2012 math.AG, cs.CC
A tropical (or min-plus) 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 min-plus 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 polynomial-time reduction to mean payoff games and are also equivalent to analogous problems in min-plus 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 min-plus linear algebra. On the other hand we show that computing the dimension of the solution space of a tropical linear system and of a min-plus linear system are $\mathsf{NP}$-complete. We also extend some of our results to the systems of min-plus linear inequalities.
• ### Tropical geometries and dynamics of biochemical networks. Application to hybrid cell cycle models(1109.4085)

Sept. 20, 2011 math.AG, q-bio.MN
We use the Litvinov-Maslov 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 quasi-equilibrium QE reactions and quasi-steady 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
• ### On a tropical dual Nullstellensatz(1108.0519)

Aug. 2, 2011 math.CO, math.AC
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.