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)
  27. 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).(ps)
  28. Solving systems of polynomial inequalities in subexponential time. - J. Symp. Comput., 1988, vol.5, p.37-64 (jointly with N.Vorobjov (jr.)).(pdf)
  29. Complexity of deciding Tarski algebra. - J. Symp. Comput., 1988, vol.5, p.65-108.(pdf)
  30. Complexity of quantifier elimination in the theory of ordinary differential equations. - Lecture Notes Computer Science, 1989, vol.378, p.11-25.(pdf)
  31. Complexity of factoring an ordinary linear differential operator. - Soviet Math. Dokl., 1989, vol.38, N 3, p.452-457.
  32. Complexity of factoring and GCD calculating of ordinary linear differential operators. - J. Symp. Comput., 1990, vol.10, N 1, p.7-37. (pdf).
  33. 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)
  34. 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)
  35. 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)
  36. Computational complexity in commutative algebra. - Math. Notes, 1989, vol.46, N 1, p.563-568.
  37. 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)
  38. 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)
  39. How to test in subexponential time whether two points can be connected by a curve in a semialgebraic set. - Ibid., p.104-105.(pdf)
  40. 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)
  41. 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)
  42. 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)
  43. 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.)).
  44. 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.)).
  45. 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)
  46. 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)
  47. Algorithms for sparse rational interpolation. - Proc. Int. Symp. on Symb. Algebr. Comput., ACM, 1991, Bonn, p.7-13 (jointly with M.Karpinski).(pdf)
  48. 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)
  49. 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)
  50. 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)
  51. 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). (dvi, ps).
  52. Computational complexity of sparse rational interpolation. - SIAM J. Comput., 1994, vol.23, N 1, p.1-11 (Jointly with M.Karpinski, M.Singer). (dvi, ps)
  53. Computing the additive complexity for algebraic circuits with root extracting. - SIAM J.Comput., 1998, vol.27, 3, p.694-701 (jointly with M.Karpinski) (dvi, ps).
  54. On computing algebraic functions using logarithms and exponentials. - SIAM J.Comput., 1995, 2, p.242-246 (jointly with M.Singer, A.Yao). (dvi, ps).
  55. 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. (dvi, ps).
  56. Deviation theorems for pfaffian sigmoids. - St.Petersburg Math. J., 1995, 6, N 1, p.107-112. (dvi, ps).
  57. 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. (dvi, ps).
  58. NC solving of a system of linear differential equations in several unknowns. - Theor.Comput.Sci., 1996, vol.157, 1, p.79-90. (dvi, ps).
  59. 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). (dvi, ps).
  60. 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). (dvi, ps).
  61. On the power of real Turing machines over binary inputs. - SIAM J. Comput., 1997, 1, p.243-254 (jointly with F.Cucker). (dvi, ps).
  62. 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). (dvi, ps).
  63. Algorithms for computing sparse shifts for multivariate polynomials. - Proc.Intern.Symp. Symbol.Algebr.Comput., ACM, 1995, Montreal, p.96-103 (jointly with Y.Lakshman). (ps).
  64. Algorithms for computing sparse shifts for multivariate polynomials. - Appl.Algebra in Eng., Communic., Comput., 2000, 11, 1, p. 43-67 (jointly with Y.Lakshman). (dvi, ps).
  65. 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). (dvi, ps).
  66. Testing shift-equivalence of polynomials using quantum machines. - Proc.Intern.Symp. on Symb.Algebr.Comput., ACM, 1996, Zurich, p.49-54 (dvi, ps).
  67. 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) (dvi, ps).
  68. 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) (dvi, ps).
  69. 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) (dvi, ps).
  70. A lower bound for randomized algebraic decision trees. - ibid., p.357-375 (jointly with M.Karpinski, F.Meyer auf der Heide, R.Smolensky) (pdf).
  71. Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. - Theor.Comput.Sci., 1997, vol.180, p.217-228 (dvi, ps).
  72. Nearly sharp complexity bounds for multiprocessor algebraic computations. - J. Complexity, 1997, vol.13, 1, p.50-64 (dvi, ps).
  73. 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) (dvi, ps).
  74. 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) (dvi, ps).
  75. 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) (dvi, ps).
  76. Complexity Lower Bounds for Randomized Computation Trees Over Algebraically Closed Fields. - Computational Complexity, 1999, 8, 4, p.316-329 (dvi, ps).
  77. Randomized Complexity Lower Bounds for Arrangements and Polyhedra. - Discrete and Computational Geometry, 1999, vol.21, p.329-344 (dvi, ps).
  78. 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) (dvi, ps).
  79. 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) (dvi, ps).
  80. Randomized Complexity Lower Bounds. - Proc.ACM Symp. Th.Comput., Dallas 1998, p.219-223 (dvi, ps).
  81. 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) (dvi, ps).
  82. 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) (dvi, ps).
  83. Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. - Proc.IEEE Symp. Found.Comput.Sci., Palo Alto, 1998, p.648-652 (dvi, ps).
  84. Complexity Lower Bounds for Approximation Algebraic Computation Trees. - J.Complexity, 1999, vol. 15, 4, p.499-512 (jointly with F.Cucker) (dvi, ps).
  85. Topological Complexity of the Range Searching. - J.Complexity, 2000, vol. 16, p.50-53 (dvi, ps).
  86. 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, ps).
  87. 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) (ps).
  88. Complexity of Null- and Positivstellensatz Proofs. - Ann. Pure and Appl. Logic, 2001, vol. 113, 1-3, p.153-160 (jointly with N.Vorobjov) (dvi, ps).
  89. 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) (dvi, ps).
  90. Linear Lower Bound on Degrees of Positivstellensatz Calculus Proofs for the Parity. - Theor. Comput. Sci., 2001, vol. 259, p.613-622 (dvi, ps).
  91. Complexity of Positivstellensatz proofs for the knapsack. - Computational Complexity, 2001, vol.10, p.139-154 (dvi, ps).
  92. Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems. - in Contemporary Math., AMS, 2001, vol. 286, p.115-120 (dvi, ps).
  93. Approximation and complexity: Liouvillean type theorems for linear differential equations on an interval. - Foundations in Computational Mathematics, 2001, vol. 1, p.289-295 (dvi, ps).
  94. There are no sparse NPW -hard sets. - SIAM J. Comput., 2001, vol. 31, p. 193-198 (jointly with F.Cucker) (dvi, ps).
  95. 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) (dvi, ps)
  96. Algebraic proof systems over formulas. - Theor. Comput. Sci., 2003, vol. 303, p. 83--102 (jointly with E.Hirsch) (dvi, ps)
  97. Approximation and complexity II: iterated integration. - Found. of Comput. Mathematics, 2002, vol. 2, p. 295-304 (dvi, ps)
  98. Complexity of semi-algebraic proofs. - Lect. Notes Comput. Sci., 2002, vol. 2285, p. 419-430 (jointly with E.Hirsch, D.Pasechnik) (ps)
  99. Exponential lower bound for static semi-algebraic proofs. - Lect. Notes Comput. Sci., 2002, vol. 2380, p. 257-268 (jointly with E.Hirsch, D.Pasechnik) (ps)
  100. 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) (ps)
  101. Public-key cryptography and invariant theory. - J. Math. Sci., 2005, vol. 126, 3, p. 1152-1157. (dvi, ps)
  102. 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) (ps)
  103. Algorithms and complexity in biological pattern formation problem. - Ann. Pure Appl. Logic, 2006, vol. 141, p. 412--428 (jointly with S.Vakoulenko) (ps)
  104. Homomorphic public-key cryptosystems over groups and rings. - Quaderni di Mathematica, 2004, vol. 13, p. 305--325 (jointly with I.Ponomarenko) (dvi, ps)
  105. Weak Bezout inequality for D-modules. - J. Complexity, 2005, vol. 21, p. 532--542. (dvi, ps)
  106. Factoring and solving linear partial differential equations. - Computing, 2004, vol. 73, p. 179-197 (jointly with F.Schwarz) (ps)
  107. 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) (ps)
  108. Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets. - Computational Complexity, 2005, vol. 14, p.20-52 (jointly with D.Pasechnik) (ps)
  109. Loewy- and primary- decompositions of D-modules - Adv. Appl. Math., 2007, vol. 38, p. 526-541 (jointly with F.Schwarz) (ps)
  110. 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)
  111. Constructions in public-key cryptography over matrix groups. (jointly with I.Ponomarenko) Contemporary Math., AMS, 2006, vol.418, p. 103-119 (ps)
  112. Time hierarchies for cryptographic function inversion with advice. - J. Math. Sci.,2009, vol. 158, p. 633-644 (jointly with E.Hirsch, K.Pervyshev) (ps)
  113. Evolution in random environment and structural instability. - J. Math. Sci., 2006, vol. 138, p. 5644-5662 (jointly with S.Vakulenko)(ps)
  114. A complete public-key cryptosystem - Groups, Complexity, Cryptology, 2009, vol. 1, p. 1-12 (jointly with E,Hirsch, K.Pervyshev) (ps)
  115. Probabilistic communication complexity over the reals. - Computational Complexity, 2008, vol. 17, p. 536-548 (pdf)
  116. Complexity of standard basis of a D-module. - St. Petersburg Math. J., 2009, vol. 20, p. 709-736 (jointly with A.Chistov) (ps)
  117. Instability, evolution and morphogenesis. - in Progress in Math. Biology Research, Nova publ., 2008, p. 55-100 (jointly with S. Vakulenko) (ps)
  118. Newton-Puiseux series for non-holonomic D-modules and factoring linear partial differential operators. - Moscow Math. J., 2009, vol. 9, p. 775--800 (pdf)
  119. 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)
  120. 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)
  121. 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)
  122. Universal stratifications and a Bertini-type Theorem. - Adv. Math., 2012, vol. 231, p. 2491-2525 (jointly with P. Milman) (pdf)
  123. Authentication from matrix conjugation. - Groups, Complexity, Cryptology, 2009, vol. 1, p. 199-205 (jointly with V. Shpilrain) (pdf)
  124. 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)
  125. Instability, Complexity and evolution. - J. Math. Sci., 2009, vol. 158, p. 787-808 (jointly with S. Vakulenko) (pdf)
  126. 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)
  127. Zero-knowledge authentication by the Sherlock Holmes method. - Groups, Complexity, Cryptology, 2012, vol. 4, p. 177-189 (jointly with V. Shpilrain) (pdf)
  128. A low complexity probabilistic test for integer multiplication. - J. Complexity, 2010, vol. 26, p. 263--267 (jointly with G. Tenenbaum) (pdf)
  129. 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)
  130. 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)
  131. Complexity of solving tropical linear systems. - Comput. Complexity, 2013, vol. 22, p. 71-88 (pdf)
  132. Secrecy without one-way functions. - Groups, Complexity, Cryptology, 2013, vol. 5, p. 31-52 (jointly with V. Shpilrain). - (pdf)
  133. Tropical cryptography (jointly with V. Shpilrain). - Communic. Algebra, 2014, vol. 42, p. 2624-2632 (pdf)
  134. Continuous hard-to-invert functions with applications to biometric authentication. - Groups, Complexity, Cryptology, 2012, vol. 4, p. 19-32 (jointly with S. Nikolenko). (pdf)
  135. On a tropical dual Nullstellensatz. - Adv. Appl. Math., 2012, 48, p. 457-464 (pdf)
  136. Tropical geometries and dynamics of biochemical networks. Application to hybrid cell cycle models. - Electronic Notes in Theoretical Computer Science, 2012, 284, p. 75-91 (jointly with V. Noel, O. Radulesku, S. Vakulenko). - (pdf)
  137. Tensor rank: matching polynomials and Schur rings (jointly with M. Muzychuk, I. Ponomarenko). - to appear in Found. Comput. Math. (pdf)
  138. 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)
  139. Complexity of tropical and min-plus linear prevarieties (jointly with V. Podolskii). - to appear in Comput. Complexity (pdf)
  140. Polynomial complexity of solving systems of few algebraic equations with small degrees. - Lect. Notes Comput. Sci., 2013, vol. 8136, p. 136-139 (pdf)
  141. 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)
  142. Secure information transmission based on physical principles. - Lect. Notes Comput. Sci., 2013, vol. 7956, p. 113-124 (jointly with V. Shpilrain). - (pdf)
  143. Efficient methods to compute Hopf bifurcations in chemical reaction networks using reaction coordinates. - Lect. Notes Comput. Sci., 2013, vol. 8136, p. 88-99 (jointly with H. Errami, M. Eiswirth, W. Seiler, T. Sturm, A. Weber). - (pdf)
  144. Subtraction-free complexity, cluster transformations, and spanning trees. - (jointly with S. Fomin, G. Koshevoy). - (pdf)
  145. Complexity of tropical Schur polynomials. - (jointly with G. Koshevoy). - (pdf)