Publications

  1. Kolmogorov's algorithms are stronger than Turing machines. - Notes of Scientific Seminars of LOMI, vol.60, 1976, p.29-37 (in Russian) (English translation in J.Soviet Math., vol.14, N 5, 1980). (pdf)
  2. An application of separability and independence notions for proving lower bounds of circuit complexity. - in the same vol., p.38-48 (English translation in J. Soviet Math., vol.14, N 5, 1980, p.1450-1456). (pdf)
  3. Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms. - Soviet Math. Dokl., 1977, vol.18, N 3, p.588-592. (pdf)
  4. On a nonlinear lower bound for circuit complexity of a set of disjunctions in monotone boolean basis. - Notes of Scientific Seminars of LOMI, vol.68, 1977, p.19-25 (in Russian) (English translation in J.Soviet Math., vol.15, N 1, 1981, p.11-13). (pdf)
  5. Some new bounds on tensor rank. - Preprint LOMI, E-2-78, 1978, 12 p. (pdf)
  6. Mutiplicative complexity of a pair of bilinear forms and of the polynomial multiplication. - Lecture Notes Computer Science, 1978, vol.64, p.250-256. (pdf)
  7. Relation between the rank and the multiplicative complexity of a bilinear form over a noetherian commutative ring. - Notes of Scientific Seminars of LOMI, vol.86, 1979, p.66-81 (in Russian) (English translation in J.Soviet Math., vol.17, 1981, p.1987-1998). (pdf)
  8. The algebraic computational complexity of a set of bilinear forms. - Journal of Computational Math. and Mathematical Physics, 1979, vol.19, N 3, p. 563-580 (in Russian) (English translation in USSR Comput. Math. and Math. Physics, vol.19, 1980, p.1-20). (pdf)
  9. Time bounds of multidimensional Turing machines. - Notes of Scientific Seminars of LOMI, vol. 88, 1979, p.47-55 (in Russian) (English translation in J.Soviet Math., vol.20, 1982, p.2290-2295). (pdf)
  10. Two reductions of graph isomorphism to problems for polynomials. - in the same volume, p.56-61 (English translation in J.Soviet Math., vol.20, 1982, p.2296-2298). (pdf)
  11. On the Eisenbud-Levine formula over a perfect field (jointly with N.Ivanov). - Soviet Math. Dokl., 1980, vol.21, N 3, p.662-664. (pdf)
  12. Analogy of Bruhat decomposition for the closure of a cone of Chevalley group of a classical serie. - Soviet Math. Dokl., 1981, vol.23, N 2, p.393-397. (pdf)
  13. On the complexity of the ``wild'' matrix problems, of the isomorphism of algebras and graphs. - Notes of Scientific Seminars of LOMI, 1981, vol.105, p.10-17 (in Russian) (English translation in J.Soviet Math., vol.22, 1983, p.1285-1289). (pdf)
  14. Isomorphism of graphs with bounded eigenvalue multiplicity. - Proc.14 ACM Symp. Th. Comput., 1982, p.310-324 (jointly with L.Babai, D.Mount). (pdf)
  15. Multiplicative complexity of a bilinear form over a commutative ring. - Lecture Notes Computer Science, 1981, vol.118, p.281-286. (pdf)
  16. Additive complexity in directed computations. - Theoretical Computer Science, 1982, vol.19, p.39-67. (pdf)
  17. Lower bounds in algebraic complexity. - Notes of Scientific Seminars of LOMI, vol.118, 1982, p.25-82 (in Russian) (English translation in J.Soviet Math., vol.29, 1985, p.1388-1425). (pdf) (pdf)
  18. Polynomial-time factoring of the multivariable polynomials over a global field. - Preprint LOMI E-5-82, 1982, 39 p. (jointly with A.Chistov).
  19. Subexponential-time solving systems of algebraic equations. I, II. - Preprint LOMI E-9-83, E-10-83, 119 p. (jointly with A.Chistov).
  20. Polynomial factoring over a finite field and solving systems of algebraic equations. - Notes of Scientific Seminars of LOMI, vol.137, 1984, p.20-79 (in Russian) (English translation in J. Soviet Math., 1986, vol.34, p.1762-1803). (pdf)
  21. Fast decomposition of polynomials into irreducible ones and the solution of systems of algebraic equations. - Soviet Math. Dokl., vol.29, 1984, p.380-383 (jointly with A.Chistov). (pdf)
  22. Complexity of quantifier elimination in the theory of algebraically closed fields. - Lecture Notes Computer Science, 1984, vol.176, p.17-31 (jointly with A.Chistov).(pdf)
  23. Finding real solutions of systems of algebraic inequalities in subexponential time. - Soviet Math. Dokl., 1985, vol.32, N 1, p.316-320 (jointly with N.Vorobjov(jr.)). (pdf)
  24. Complexity of deciding the first-order theory of algebraically closed fields. - Izvestia of Academy of Sciences of the USSR, 1986, vol. 50, N 5, p.1106-1120 (in Russian) (English translation in Math. USSR Izvestia, vol.29, N 2, 1987, p.459-475). (pdf)
  25. Computational complexity in polynomial algebra. - Proc. of International Congress of Mathematicians, 1986, Berkeley, vol.2, p.1452-1460.
    26. (pdf)
  26. The matching problem for bipartite graphs with polynomially bounded permanents is in NC. - Proc.28 Symp. Found. Comput. Sci., IEEE, 1987, p.166-172 (jointly with M.Karpinski).(pdf)
  27. Solving systems of polynomial inequalities in subexponential time. - J. Symp. Comput., 1988, vol.5, p.37-64 (jointly with N.Vorobjov (jr.)).(pdf)
  28. Complexity of deciding Tarski algebra. - J. Symp. Comput., 1988, vol.5, p.65-108.(pdf)
  29. Complexity of quantifier elimination in the theory of ordinary differential equations. - Lecture Notes Computer Science, 1989, vol.378, p.11-25.(pdf)
  30. Complexity of factoring an ordinary linear differential operator. - Soviet Math. Dokl., 1989, vol.38, N 3, p.452-457.
  31. Complexity of factoring and GCD calculating of ordinary linear differential operators. - J. Symp. Comput., 1990, vol.10, N 1, p.7-37. (pdf).
  32. Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields - SIAM J. Comput., 1990, vol.19, N 6, p.1059-1063 (jointly with M.Karpinski, M.Singer). (pdf)
  33. Solving ordinary differential equations in the series with real exponents. - Trans. AMS, 1991, vol.327, N 1, p.329-351 (jointly with M.Singer). (pdf)
  34. Complexity of calculating characteristics and genre of a system of exterior differential equations. - Soviet Math. Dokl., 1989, vol.39, N 3, p.432-436.(pdf)
  35. Computational complexity in commutative algebra. - Math. Notes, 1989, vol.46, N 1, p.563-568.
  36. Complexity of computing the characteristics and the genre of a system of exterior differential equations. - Lecture Notes Computer Science, 1989, vol.358, p.534-543.(pdf)
  37. Complexity of irreducibility testing for a system of linear ordinary differential equations. - Proc. Int. Symp. on Symb. Algebr. Comput., ACM, 1990, Japan, p.225-230.(pdf)
  38. How to test in subexponential time whether two points can be connected by a curve in a semialgebraic set. - Ibid., p.104-105.(pdf)
  39. Complexity of solving systems of linear equations over the rings of differential operators. - Proc. Int. Symp. Effective Methods in Algebraic Geometry, 1990, Italy, Birkhauser, Progr. in Math., vol.94, p.195-202.(pdf)
  40. Interpolating of sparse rational functions without knowing bounds on exponents. - Proc.31 IEEE Symp. FOCS, 1990, p.840-846 (jointly with M.Karpinski, M.Singer). (pdf)
  41. The interpolation problem for k-sparse sums of eigenfunctions of operators. - Adv. Appl. Math., 1991, vol. 12, p. 76-81 (jointly with M.Karpinski, M.Singer). (pdf)
  42. Comptage des composantes connexes d'un ensemble semi-algebrique en temps simplement exponentiel. - Compte-Rendus de l'Acad. des Sci. Paris, 1990, t. 311, Serie I, p.879-882 (jointly with J.Heintz, M.F.Roy, P.Solerno, N.N.Vorobjov (jr.)).
  43. Determination of the number of connected components of a semialgebraic set in subexponential time. - Soviet Math. Dokl., 1991, vol.42, N 2, p.563-566 (jointly with N.N.Vorobjov(jr.)).
  44. Counting connected components of a semialgebraic set in subexponential time. - Computational Complexity, 1992, vol.2, N 2, p. 133-186 (jointly with N.N.Vorobjov (jr.)).(pdf)
  45. Finding connected components of a semialgebraic set in subexponential time. - Appl. Algebra in Engineering, Communication and Computing, 1992, v.2, p.217-238 (jointly with J.Canny, N.N.Vorobjov (jr.)). (pdf)
  46. Algorithms for sparse rational interpolation. - Proc. Int. Symp. on Symb. Algebr. Comput., ACM, 1991, Bonn, p.7-13 (jointly with M.Karpinski).(pdf)
  47. Existence of short proofs for nondivisibility of sparse polynomials under the Extended Riemann Hypothesis. - Proc. ACM Int. Symp. Symb. Alg. Comput., Berkeley, 1992, p.117-122 (jointly with M.Karpinski, A.Odlyzko).(pdf)
  48. An approximation algorithm for the number of zeroes of arbitrary polynomials over GF[q] - Proc.32 IEEE Symp. FOCS, 1991, p.662-669 (jointly with M.Karpinski). (pdf)
  49. Computational complexity of sparse real algebraic function interpolation. - ``Computational Algebraic Geometry,'' edited by A. Galligo. - Progress in Mathematics, Birkhauser, 1993, vol.109, p. 91-104 (jointly with M.Karpinski, M.Singer). (pdf)
  50. A zero-test and an interpolation algorithm for the shifted sparse polynomials. - Proc. Int. Conf. Appl. Algebra and Error Correcting Codes, Puerto Rico, May 1993, LNCS 673, p.162-169 (jointly with M.Karpinski). (pdf, ps).
  51. Computational complexity of sparse rational interpolation. - SIAM J. Comput., 1994, vol.23, N 1, p.1-11 (Jointly with M.Karpinski, M.Singer). (pdf, ps)
  52. Computing the additive complexity for algebraic circuits with root extracting. - SIAM J.Comput., 1998, vol.27, 3, p.694-701 (jointly with M.Karpinski) (pdf, ps).
  53. On computing algebraic functions using logarithms and exponentials. - SIAM J.Comput., 1995, 2, p.242-246 (jointly with M.Singer, A.Yao). (pdf, ps).
  54. Deviation theorems for solutions of linear ordinary differential equations and applications to parallel complexity of sigmoids. - St.Petersburg Math. J., 1995, 6, N 1, p.89-106. (pdf, ps).
  55. Deviation theorems for pfaffian sigmoids. - St.Petersburg Math. J., 1995, 6, N 1, p.107-112. (pdf, ps).
  56. Deviation theorems for solutions of differential equations and applications to lower bounds on parallel complexity of sigmoids. - Theor.Comp. Sci., 1994, vol.133, 1, p.23-33. (pdf, ps).
  57. NC solving of a system of linear differential equations in several unknowns. - Theor.Comput.Sci., 1996, vol.157, 1, p.79-90. (pdf, ps).
  58. Complexity lower bounds on testing membership to a polyhedron by algebraic decision trees. - Proc.ACM Symp. Th. Comput., Montreal, 1994, p.635-644 (jointly with M.Karpinski, N.Vorobjov). (pdf, ps).
  59. Complexity lower bounds for computation trees with elementary transcendental function gates. - Proc.IEEE Symp. Found. Comput. Sci., Santa Fe, 1994, p.548-552 (jointly with N.Vorobjov). (pdf, ps).
  60. On the power of real Turing machines over binary inputs. - SIAM J. Comput., 1997, 1, p.243-254 (jointly with F.Cucker). (pdf, ps).
  61. Improved lower bound on testing membership to a polyhedron by algebraic decision trees. - Proc.IEEE Symp. Found. Comput.Sci., Milwaukee, 1995, p.258-265 (jointly with M.Karpinski, N.Vorobjov). (pdf, ps).
  62. Algorithms for computing sparse shifts for multivariate polynomials. - Proc.Intern.Symp. Symbol.Algebr.Comput., ACM, 1995, Montreal, p.96-103 (jointly with Y.Lakshman). (pdf).
  63. Algorithms for computing sparse shifts for multivariate polynomials. - Appl.Algebra in Eng., Communic., Comput., 2000, 11, 1, p. 43-67 (jointly with Y.Lakshman). (pdf, ps).
  64. Complexity lower bounds for computation trees with elementary transcendental function gates. - Theor.Comput.Sci., 1996, vol.157, 2, p.185-214 (jointly with N.Vorobjov). (pdf, ps).
  65. Testing shift-equivalence of polynomials using quantum machines. - Proc.Intern.Symp. on Symb.Algebr.Comput., ACM, 1996, Zurich, p.49-54 (pdf, ps).
  66. A lower bound for randomized algebraic decision trees. - Proc.ACM Symp. Th.Comput., Philadelphia, 1996, p.612-619 (jointly with M.Karpinski, F.Meyer auf der Heide, R.Smolensky) (pdf, ps).
  67. An exponential lower bound on the size of algebraic decision trees for MAX problem. - Computational Complexity, 1998, vol.7, p.193-203 (jointly with M.Karpinski, A.Yao) (pdf, ps).
  68. Randomization and the computational power of analytic and algebraic decision trees -- Computational Complexity, 1997, vol.6, 4, p.376-388 (jointly with M.Karpinski, R.Smolensky) (pdf, ps).
  69. A lower bound for randomized algebraic decision trees. - ibid., p.357-375 (jointly with M.Karpinski, F.Meyer auf der Heide, R.Smolensky) (pdf).
  70. Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. - Theor.Comput.Sci., 1997, vol.180, p.217-228 (pdf, ps).
  71. Nearly sharp complexity bounds for multiprocessor algebraic computations. - J. Complexity, 1997, vol.13, 1, p.50-64 (pdf, ps).
  72. Quadratic complexity lower bound for randomized computation trees solving the knapsack problem. - Proc.ACM Symp. Th.Comput., El Paso 1997, p.76-85 (jointly with M.Karpinski) (pdf, ps).
  73. Lower bound on testing membership to a polyhedron by algebraic decision and computation trees. - Discrete and Computational Geometry, 1997, vol.17, 2, p.191-215 (jointly with M.Karpinski, N.Vorobjov) (pdf, ps).
  74. Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. - Lect.Notes Comput.Sci., 1997, vol.1255, p.114-129 (jointly with A.Slissenko) (pdf, ps).
  75. Complexity Lower Bounds for Randomized Computation Trees Over Algebraically Closed Fields. - Computational Complexity, 1999, 8, 4, p.316-329 (pdf, ps).
  76. Randomized Complexity Lower Bounds for Arrangements and Polyhedra. - Discrete and Computational Geometry, 1999, vol.21, p.329-344 (pdf, ps).
  77. Polytime Algorithm for the Shortest Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. - Proc. ACM Intern.Conf.Symbolic and Algebraic Computations, Rostock, Germany 1998, p.17-24 (jointly with A.Slissenko) (pdf, ps).
  78. Exponential Lower Bound on the Size of Depth 3 Arithmetic Circuit Computing Determinant over a Finite Field. - Proc.ACM Symp. Th.Comput., Dallas 1998, p.577-582 (jointly with M.Karpinski) (pdf, ps).
  79. Randomized Complexity Lower Bounds. - Proc.ACM Symp. Th.Comput., Dallas 1998, p.219-223 (pdf, ps).
  80. Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. - Proc.IEEE Symp. Found.Comput.Sci., Palo Alto, 1998, p.269-278 (jointly with A.Razborov) (pdf, ps).
  81. Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. - Appl.Algebra in Eng.,Communic.,Comput., 2000, 10, 6, p.465-487 (jointly with A.Razborov) (pdf, ps).
  82. Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. - Proc.IEEE Symp. Found.Comput.Sci., Palo Alto, 1998, p.648-652 (pdf, ps).
  83. Complexity Lower Bounds for Approximation Algebraic Computation Trees. - J.Complexity, 1999, vol. 15, 4, p.499-512 (jointly with F.Cucker) (pdf, ps).
  84. Topological Complexity of the Range Searching. - J.Complexity, 2000, vol. 16, p.50-53 (pdf, ps).
  85. Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. - Proc. ACM Symp. Th. Comput., Atlanta, 1999, p.547-556 (jointly with S.Buss, R.Impagliazzo, T.Pitassi) (dvi, pdf).
  86. Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. - J. Comput. Syst. Sci., 2001, vol. 62, p.267-289 (jointly with S.Buss, R.Impagliazzo, T.Pitassi) (pdf).
  87. Complexity of Null- and Positivstellensatz Proofs. - Ann. Pure and Appl. Logic, 2001, vol. 113, 1-3, p.153-160 (jointly with N.Vorobjov) (pdf, ps).
  88. Bounds on numbers of vectors of multiplicities for polynomials which are easy to compute. - Proc. ACM Intern.Conf.Symbolic and Algebraic Computations, Scotland, 2000, p.137-145 (jointly with N.Vorobjov) (pdf, ps).
  89. Linear Lower Bound on Degrees of Positivstellensatz Calculus Proofs for the Parity. - Theor. Comput. Sci., 2001, vol. 259, p.613-622 (pdf, ps).
  90. Complexity of Positivstellensatz proofs for the knapsack. - Computational Complexity, 2001, vol.10, p.139-154 (pdf, ps).
  91. Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems. - in Contemporary Math., AMS, 2001, vol. 286, p.115-120 (pdf, ps).
  92. Approximation and complexity: Liouvillean type theorems for linear differential equations on an interval. - Foundations in Computational Mathematics, 2001, vol. 1, p.289-295 (pdf, ps).
  93. There are no sparse NPW -hard sets. - SIAM J. Comput., 2001, vol. 31, p. 193-198 (jointly with F.Cucker) (ps, pdf).
  94. Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. -- Theor. Comput. Sci. 2004, vol. 315, p. 371--404 (jointly with D.Burago, A.Slissenko) (pdf, ps)
  95. Algebraic proof systems over formulas. - Theor. Comput. Sci., 2003, vol. 303, p. 83--102 (jointly with E.Hirsch) (pdf, ps)
  96. Approximation and complexity II: iterated integration. - Found. of Comput. Mathematics, 2002, vol. 2, p. 295-304 (pdf, ps)
  97. Complexity of semi-algebraic proofs. - Lect. Notes Comput. Sci., 2002, vol. 2285, p. 419-430 (jointly with E.Hirsch, D.Pasechnik) (pdf)
  98. Exponential lower bound for static semi-algebraic proofs. - Lect. Notes Comput. Sci., 2002, vol. 2380, p. 257-268 (jointly with E.Hirsch, D.Pasechnik) (pdf)
  99. Homomorphic public-key cryptosystems and encrypting boolean circuits. - Applicable Algebra in Engin., Communic. and Comput., 2006, vol. 17, p. 239--255. (jointly with I.Ponomarenko) (pdf)
  100. Public-key cryptography and invariant theory. - J. Math. Sci., 2005, vol. 126, 3, p. 1152-1157. (pdf, ps)
  101. Algorithmic aspects of genetic sequences and relative Kolmogorov complexity. -- Intern. J. Pure Appl. Math., 2004, vol.11, 3, p. 283--292 (jointly with A.Grigorieva) (pdf)
  102. Algorithms and complexity in biological pattern formation problem. - Ann. Pure Appl. Logic, 2006, vol. 141, p. 412--428 (jointly with S.Vakoulenko) (pdf)
  103. Homomorphic public-key cryptosystems over groups and rings. - Quaderni di Mathematica, 2004, vol. 13, p. 305--325 (jointly with I.Ponomarenko) (pdf, ps)
  104. Weak Bezout inequality for D-modules. - J. Complexity, 2005, vol. 21, p. 532--542. (pdf, ps)
  105. Factoring and solving linear partial differential equations. - Computing, 2004, vol. 73, p. 179-197 (jointly with F.Schwarz) (pdf)
  106. Complexity of gene circuits, Pfaffian functions and morphogenesis problem. - Comptes-Rendus Acad.Sci., 2003, ser. 1, vol. 337, issue 11, p. 721-724 (jointly with S.Vakulenko) (pdf)
  107. Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets. - Computational Complexity, 2005, vol. 14, p.20-52 (jointly with D.Pasechnik) (pdf)
  108. Loewy- and primary- decompositions of D-modules - Adv. Appl. Math., 2007, vol. 38, p. 526-541 (jointly with F.Schwarz) (pdf)
  109. Quantum optical device accelerating dynamic programming. - Physics of Particles and Nuclei Letters, 2007, vol. 4, p. 141--142 (jointly with A.Kazakov, S.Vakulenko) (pdf)
  110. Constructions in public-key cryptography over matrix groups. (jointly with I.Ponomarenko) Contemporary Math., AMS, 2006, vol.418, p. 103-119 (pdf)
  111. Time hierarchies for cryptographic function inversion with advice. - J. Math. Sci.,2009, vol. 158, p. 633-644 (jointly with E.Hirsch, K.Pervyshev) (pdf)
  112. Evolution in random environment and structural instability. - J. Math. Sci., 2006, vol. 138, p. 5644-5662 (jointly with S.Vakulenko)(pdf)
  113. A complete public-key cryptosystem - Groups, Complexity, Cryptology, 2009, vol. 1, p. 1-12 (jointly with E,Hirsch, K.Pervyshev) (pdf)
  114. Probabilistic communication complexity over the reals. - Computational Complexity, 2008, vol. 17, p. 536-548 (pdf)
  115. Complexity of standard basis of a D-module. - St. Petersburg Math. J., 2009, vol. 20, p. 709-736 (jointly with A.Chistov) (pdf)
  116. Instability, evolution and morphogenesis. - in Progress in Math. Biology Research, Nova publ., 2008, p. 55-100 (jointly with S. Vakulenko) (pdf)
  117. Newton-Puiseux series for non-holonomic D-modules and factoring linear partial differential operators. - Moscow Math. J., 2009, vol. 9, p. 775--800 (pdf)
  118. Invariant-based cryptosystems and their security against provable worst-case break. - St. Petersburg Math. J., 2009, vol. 20, p. 937-953 (jointly with A. Kojevnikov, S. Nikolenko) (pdf)
  119. Zero-knowledge authentication schemes from actions on graphs, groups, or rings. - Ann. Pure Appl. Logic, 2010, vol. 162, p. 194-200 (jointly with V. Shpilrain) (pdf)
  120. Loewy decomposition of linear third-order PDE's in the plane. - Proc. ACM Int. Symp. Symb. Algebr. Comput., Austria, 2008, p. 277-286 (jointly with F. Schwarz) (pdf)
  121. Universal stratifications and a Bertini-type Theorem. - Adv. Math., 2012, vol. 231, p. 2491-2525 (jointly with P. Milman) (pdf)
  122. Authentication from matrix conjugation. - Groups, Complexity, Cryptology, 2009, vol. 1, p. 199-205 (jointly with V. Shpilrain) (pdf)
  123. Non-holonomic ideals in the plane and absolute factoring. - Proc. ACM Int. Symp. Symb. Algebr. Comput., Munich, 2010, p. 93-97 (jointly with F. Schwarz) (pdf)
  124. Instability, Complexity and evolution. - J. Math. Sci., 2009, vol. 158, p. 787-808 (jointly with S. Vakulenko) (pdf)
  125. Nash desingularization for binomial varieties as Euclidean division in dim >0. Polynomial complexity in dim <3. - Adv. Math., 2012, vol. 231, p. 3389-3428 (jointly with P. Milman) (pdf)
  126. Zero-knowledge authentication by the Sherlock Holmes method. - Groups, Complexity, Cryptology, 2012, vol. 4, p. 177-189 (jointly with V. Shpilrain) (pdf)
  127. A low complexity probabilistic test for integer multiplication. - J. Complexity, 2010, vol. 26, p. 263--267 (jointly with G. Tenenbaum) (pdf)
  128. Effective Hironaka resolution and its complexity. - Asian J. Math., volume dedicated to H. Hironaka, 2011, vol. 15, p. 193--228 (jointly with E. Bierstone, P. Milman, J. Wlodarczyk) (pdf)
  129. Complexity and stable evolution of circuits. - in Proofs, Categories and Computations. Essays in honor of Grigori Mints. Edited by Solomon Feferman and Wilfried Sieg. College Publications. Tributes Series. Dov Gabbay, 2010, p. 279-296 (jointly with S.Vakulenko) (pdf)
  130. Complexity of solving tropical linear systems. - Comput. Complexity, 2013, vol. 22, p. 71-88 (pdf)
  131. Secrecy without one-way functions. - Groups, Complexity, Cryptology, 2013, vol. 5, p. 31-52 (jointly with V. Shpilrain). - (pdf)
  132. Tropical cryptography (jointly with V. Shpilrain). - Communic. Algebra, 2014, vol. 42, p. 2624-2632 (pdf)
  133. Continuous hard-to-invert functions with applications to biometric authentication. - Groups, Complexity, Cryptology, 2012, vol. 4, p. 19-32 (jointly with S. Nikolenko). (pdf)
  134. On a tropical dual Nullstellensatz. - Adv. Appl. Math., 2012, 48, p. 457-464 (pdf)
  135. Tropicalization and tropical equilibration of chemical reactions. - Contemporary Math., 2014, vol. 616, p. 261-275 (jointly with V. Noel, O. Radulesku, S. Vakulenko). - (pdf)
  136. Tensor rank: matching polynomials and Schur rings. - Found. Comput. Math., 2014, vol. 14, p. 457-481 (jointly with M. Muzychuk, I. Ponomarenko). (pdf)
  137. Complexity of Solving Systems of polynomial equations with Few Independent Monomials and Applications to Mass-action Kinetics. - Lect. Notes Comput. Sci.,2012, vol. 7442, p. 143-154 (jointly with A. Weber). - (pdf)
  138. Complexity of tropical and min-plus linear prevarieties (jointly with V. Podolskii). - Comput. Complexity, 2015, vol. 24, p.31-64 (pdf)
  139. Polynomial complexity of solving systems of few algebraic equations with small degrees. - Lect. Notes Comput. Sci., 2013, vol. 8136, p. 136-139 (pdf)
  140. Computing divisors and common multiples of quasi-linear ordinary differential equations. - Lect. Notes Comput. Sci., 2013, vol. 8136, p. 140-147 (jointly with F. Schwarz). (pdf)
  141. Secure information transmission based on physical principles. - Lect. Notes Comput. Sci., 2013, vol. 7956, p. 113-124 (jointly with V. Shpilrain). - (pdf)
  142. Detection of Hopf bifurcations in chemical reaction networks using convex coordinates. - J. Computational Physics, 2015, vol. 291, p. 279-302 (jointly with H. Errami, M. Eiswirth, W. Seiler, T. Sturm, A. Weber). - (pdf)
  143. Subtraction-free complexity, cluster transformations, and spanning trees. - Found. Comput. Math., 2016, vol. 16, p. 1-31 (jointly with S. Fomin, G. Koshevoy). - (pdf)
  144. Complexity of tropical Schur polynomials. - J. Symb. Comput., 2016, vol. 74, p. 46-54 (jointly with G. Koshevoy). - (pdf)
  145. Yao's millionaires" problem and decoy-based public key encryption by classical physics. - Int. J. Found. Comput. Sci., 2014, vol. 25, p. 409-417 (jointly with V. Shpilrain). - (pdf)
  146. Punctuated evolution and robustness in morphogenesis. - BioSystems, 2014, vol. 123, p. 106-113 (jointly with J. Reinitz, S. Vakulenko, A. Weber). - (pdf)
  147. Tropical effective primary and dual Nullstellensaetze. - Discr. Comput. Geom., 2018, vol. 59, p. 507--552 (jointly with V. Podolskii). - (pdf)
  148. Tropical differential equations. - Adv. Appl. Math., 2017, vol. 82, p. 120-128 (pdf)
  149. Reduction methods and chaos for quadratic systems of differential equations. - Studies Appl. Math., 2015, vol. 135, issue 3, p. 225--247 (jointly with S. Vakulenko, A. Weber) (pdf)
  150. Model reduction of biochemical reaction networks by tropical analysis methods - Math. Model. Natur. Phenom., 2015, vol. 10, N 3, p. 124--138 (jointly with O. Radulesku, S. Vakulenko) (pdf)
  151. Polynomial complexity recognizing a tropical linear variety.- Lect. Notes Comput. Sci., 2015, vol. 9301, p. 152-157 (pdf)
  152. Computing highest-order divisors for a class of quasi-linear partial differential equations. - Lect. Notes Comput. Sci., 2015, vol. 9301, p. 158-165 (jointly with F. Schwarz). (pdf)
  153. Algorithms to study large metabolic network dynamics - Math. Model. Natur. Phenom., 2015, vol. 10, N 5, p. 100-118 (jointly with S. Samal, S. Vakulenko, A. Weber) (pdf)
  154. Symbolic dynamics of biochemical pathways as finite states machines - Lect. Notes Bioinformatics, vol. 9308, 2015, p.104-120 (jointly with O. Radulescu, S. Samal, A. Naldi, A. Weber) (pdf)
  155. Bounds on the number of connected components for tropical prevarieties - Discr. Comput. Geom., 2017, vol. 57, N 2, p. 470-493 (jointly with A. Davydow) (pdf)
  156. Analysis of Reaction Network Systems Using Tropical Geometry - Lect. Notes Comput. Sci., vol. 9301, 2015, p. 424-439 (jointly with O. Radulescu, S. Samal, H. Froelich) (pdf)
  157. A Geometric Method for Model Reduction of Biochemical Networks with Polynomial Rate Functions - Bull. Math. Biol., 2015, vol. 77, N 12, p. 2180-2211 (jointly with O. Radulescu, S. Samal, H. Froelich, A. Weber) (pdf)
  158. Yao millionaires' problem and public-key encryption without computational assumptions - Int. J. Found. Comput. Sci., 2017, vol.28, p. 379-389 (jointly with L. Kish, V. Shpilrain) (pdf)
  159. A Geometric analysis of pathways dynamics: application to versality of TGF-beta receptors - Biosystems, 2016, vol. 149, p. 3-14 (jointly with O. Radulescu, S. Samal, A. Naldi, N. Theret, A. Weber) (pdf)
  160. On semiring complexity of Schur polynomials - Comput. Complexity, 2018, vol.27, p. 595--616 (jointly with S. Fomin, D. Nogneng, E. Schost ) (pdf)
  161. Tropical Newton-Puiseux polynomials - Proc. Int. Conf. Computer Algebra Sci. Comput., 2018, Lille, Lect. Notes Comput. Sci., vol. 11077, p. 177--186 (pdf)
  162. A Case Study on the Parametric Occurrence of Multiple Steady States. - Proc. Intern. Symp. Symb. Algebr. Comput., Kaiserslautern, ACM, 2017, p. 45--52 (jointly with R. Bradford, J. H. Davenport, M. England, H. Errami, V. Gerdt, C. Hoyt, M. Kosta, O. Radulescu, T. Sturm, A. Weber) (pdf)
  163. Tropical combinatorial Nullstellensatz and fewnomials testing - Found. Comput. Math., 2020, vol. 20, p. 753--781 (jointly with V. Podolskii) (pdf)
  164. Symbolic versus numerical computation and vizualization of parameter regions for multistationarity of biological networks. - Proc. Intern. Symp. Comp. Algebr. Symb. Comput., Beijing, 2017, Lect. Notes Comput. Sci., vol. 10490, p. 93--108 (jointly with M. England, H. Errami, O. Radulescu, T. Sturm, A. Weber) (pdf)
  165. Probabilistic solution of Yao's millionaires' problem - Studies in Computational Intelligence, Springer, 2020, vol. 835, p. 401--411 (jointly with M. Bessonov, V. Shpilrain) (pdf)
  166. Upper bounds on Betti numbers of tropical prevarieties - Arnold Math. J., 2018, vol. 4, p. 127--136 (jointly with N. Vorobjov) (pdf)
  167. Complexity of deciding whether a tropical linear prevariety is a tropical variety - Appl. Alg. Eng. Commun. Comput., 2021, vol. 32, p. 157--174 (jointly with N. Vorobjov) (pdf)
  168. A framework for unconditionally secure public-key decryption (with possible decryption errors) - Proc. Int. Congress Math. Software, 2018, Notre Dame, USA, Lect. Notes Comput. Sci., vol. 10931, p.45--54 (jointly with M. Bessonov, V. Shpilrain) (pdf)
  169. Tropical recurrent sequences - Adv. Appl. Math., vol. 116, 2020 (pdf)
  170. Tropical cryptography II: extensions by homomorphisms - Communic. Algebra, 2019, vol. 47, p. 4224--4229 (jointly with V. Shpilrain) (pdf)
  171. Decomposing tropical rational functions. - J. Symbol. Comput., 2020, vol. 101, p. 61--72 (pdf)
  172. Identifying the parametric occurrence of multiple steady states for some biological networks. - J. Symb. Comput., 2020, vol.98, p. 84--119 (jointly with R. Bradford, J. H. Davenport, M. England, H. Errami, V. Gerdt, C. Hoyt, M. Kosta, O. Radulescu, T. Sturm, A. Weber) (pdf)
  173. RSA and redactable blockchains. - International Journal of Computer Mathematics: Computer Systems Theory, 2021, vol. 6, p. 1--6 (jointly with V. Shpilrain) (pdf)
  174. On a tropical version of the Jacobian conjecture. - J. Symbol. Comput., 2022, vol. 109, p. 399--403 (jointly with D. Radchenko) (pdf)
  175. Key agreement based on automaton groups. - Groups, Compl. Crypt., 2019, vol. 11, p. 77--81 (jointly with R. Grigorchuk) (pdf)
  176. Semi-Algebraic Proofs, IPS Lower Bounds and the tau-Conjecture: Can a Natural Number be Negative?. - SIAM J. Comput., 2024, vol. 53, p. 648--700 (jointly with Y. Alekseev, E. Hirsch, I. Tzameret) (pdf)
  177. Efficiently and effectively recognizing toricity of steady state varieties. - Math. in Comput. Sci., 2021, vol. 15, p. 199--232 (jointly with A. Iosif, H. Rahkooy, T. Sturm, A. Weber) (pdf)
  178. Entropy of tropical holonomic sequences. - J. Symbol. Comput., 2022, vol. 108, p. 91--97 (pdf)
  179. Entropy of radical ideal of a tropical curve. - Adv. Appl. Math., 2024, vol. 153 (pdf)
  180. Tropical Newton-Puiseux polynomials II. - J. Symbol. Comput., 2023, vol. 115, p. 316--319. (pdf)
  181. Probability theory and public-key cryptogrqphy. - International Journal of Computer Mathematics: Computer Systems Theory, 2021, vol. 6, p. 285--290 (jointly with M. Bessonov, V. Shpilrain) (pdf)
  182. A tropical version of Hilbert polynomial (in dimension one). - Beitraege zur Algebra und Geometrie (jointly with N. Elizarov) (pdf)
  183. Digital signature schemes using non-square matrices or scrap automorphisms. - Int. J. Comput. Math. Comput. Syst. Th., 2024, vol. 9, p. 65--73. (jointly with J. Chen, V. Shpilrain) (pdf)
  184. BASS: Boolean Automorphisms Signature Scheme. - Lect. Notes Comput. Sci., 2024, vol. 14534, p. 1--12. (jointly with I. Ilmer, A. Ovchinnikov, V. Shpilrain) (pdf)
  185. .Tropical cryptography III: digital signatures. - J. Math. Cryptology, 2024, vol. 18. (jointly with J. Chen, V. Shpilrain) (pdf)