Abstract:
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.

Abstract:
Let $\{w_{i,j}\}_{1\leq i\leq n, 1\leq j\leq s} \subset L_m=F(X_1,...,X_m)[{\partial \over \partial X_1},..., {\partial \over \partial X_m}]$ be linear partial differential operators of orders with respect to ${\partial \over \partial X_1},..., {\partial \over \partial X_m}$ at most $d$. We prove an upper bound n(4m^2d\min\{n,s\})^{4^{m-t-1}(2(m-t))} on the leading coefficient of the Hilbert-Kolchin polynomial of the left $L_m$-module $<\{w_{1,j}, ..., w_{n,j}\}_{1\leq j \leq s} > \subset L_m^n$ having the differential type $t$ (also being equal to the degree of the Hilbert-Kolchin polynomial). The main technical tool is the complexity bound on solving systems of linear equations over {\it algebras of fractions} of the form $$L_m(F[X_1,..., X_m, {\partial \over \partial X_1},..., {\partial \over \partial X_k}])^{-1}.$$

Abstract:
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.

Abstract:
Deterministic and probabilistic communication protocols are introduced in which parties can exchange the values of polynomials (rather than bits in the usual setting). It is established a sharp lower bound $2n$ on the communication complexity of recognizing the $2n$-dimensional orthant, on the other hand the probabilistic communication complexity of its recognizing does not exceed 4. A polyhedron and a union of hyperplanes are constructed in $\RR^{2n}$ for which a lower bound $n/2$ on the probabilistic communication complexity of recognizing each is proved. As a consequence this bound holds also for the EMPTINESS and the KNAPSACK problems.

Abstract:
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.

Abstract:
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$.

Abstract:
We prove a double-exponential upper bound on the degree and on the complexity of constructing a Janet basis of a $D$-module. This generalizes a well known bound on the complexity of a Gr\"obner basis of a module over the algebra of polynomials. We would like to emphasize that the obtained bound can not be immediately deduced from the commutative case.

Abstract:
We propose a new homomorphic public-key cryptosystem over arbitrary nonidentity finite group based on the difficulty of the membership problem for groups of integer matrices. Besides, a homomorphic cryptosystem is designed for the first time over finite commutative rings.

Abstract:
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.