Grigor'ev Dmitrii Yur'evich

Publications in Math-Net.Ru

1. Tropical Combinatorial Nullstellensatz and sparse polynomials
   
   Found. Comput. Math., 20 (2020),  753–781
2. Tropical effective primary and dual nullstellensätze
   
   Discrete Comput. Geom., 59:3 (2018),  507–552
3. Tropical Combinatorial Nullstellensatz and Fewnomials Testing
   
   Lecture Notes in Comput. Sci., 10472 (2017),  284–297
4. Complexity of tropical and min-plus linear prevarieties
   
   Comput. Complexity, 24:1 (2015),  31–64
5. Tropical effective primary and dual Nullstellensátz
   
   Leibniz Internat. Proc. in Inform., 30 (2015),  379–391
6. Analogue of Newton–Puiseux series for non-holonomic $D$-modules and factoring
   
   Mosc. Math. J., 9:4 (2009),  775–800
7. Algebraic cryptography: new constructions and their security against provable break
   
   Algebra i Analiz, 20:6 (2008),  119–147
8. Complexity of the Standard Basis of a $D$-Module
   
   Algebra i Analiz, 20:5 (2008),  41–82
9. Instability, complexity, and evolution
   
   Zap. Nauchn. Sem. POMI, 360 (2008),  31–69
10. Time hierarchies for cryptographic function inversion with advice
    
    Zap. Nauchn. Sem. POMI, 358 (2008),  54–76
11. Evolution in random environment and structural instability
    
    Zap. Nauchn. Sem. POMI, 325 (2005),  28–60
12. Complexity of semialgebraic proofs
    
    Mosc. Math. J., 2:4 (2002),  647–679
13. On non-abelian homomorphic public-key cryptosystems
    
    Zap. Nauchn. Sem. POMI, 293 (2002),  39–58
14. Public-key cryptography and invariant theory
    
    Zap. Nauchn. Sem. POMI, 293 (2002),  26–38
15. Testing the shift-equivalence of polynomials using quantum machines
    
    Itogi Nauki i Tekhniki. Sovrem. Mat. Pril. Temat. Obz., 34 (2001),  98–116
16. Double-exponential growth of the number of vectors of solutions of polynomial systems
    
    Zap. Nauchn. Sem. POMI, 277 (2001),  47–52
17. Computation of a path with a minimal number of links in a given homotopy class between semi-algebraic obstacles in the plane
    
    Algebra i Analiz, 10:2 (1998),  124–147
18. Deviation theorems for pfaffian sigmoids
    
    Algebra i Analiz, 6:1 (1994),  127–131
19. Deviation theorems for solutions of linear ordinary differential equations and applications to parallel complexity of sigmoids
    
    Algebra i Analiz, 6:1 (1994),  110–126
20. Complexity of irreducibility testing for a system of linear ordinary differential equations
    
    Zap. Nauchn. Sem. LOMI, 192 (1991),  60–68
21. Complexity of solving linears systems in the rings of differential operators
    
    Zap. Nauchn. Sem. LOMI, 192 (1991),  47–60
22. Finding connected components of a semialgebraic set in subexponential time
    
    Zap. Nauchn. Sem. LOMI, 192 (1991),  3–46
23. Determination of the number of connected components of a semi-algebraic set in subexponential time
    
    Dokl. Akad. Nauk SSSR, 314:5 (1990),  1040–1043
24. The complexity of computing the genus of a system of exterior differential equations
    
    Dokl. Akad. Nauk SSSR, 306:1 (1989),  26–30
25. Complexity of computations in commutative division of the USSR Academy of Sciences
    
    Mat. Zametki, 46:1 (1989),  96–104
26. Complexity of factoring and GCD calculating for linear ordinary differential operators
    
    Zap. Nauchn. Sem. LOMI, 176 (1989),  68–103
27. Complexity of quantifier elimination in the theory of ordinary differentially closed fields
    
    Zap. Nauchn. Sem. LOMI, 176 (1989),  53–67
28. Complexity of the factorization of a linear ordinary differential operator
    
    Dokl. Akad. Nauk SSSR, 303:1 (1988),  16–20
29. Complexity of deciding the first-order theory of real closed fields
    
    Zap. Nauchn. Sem. LOMI, 174 (1988),  53–100
30. Solving systems of polynomial inequalities over real closed fields in subexponential time
    
    Zap. Nauchn. Sem. LOMI, 174 (1988),  3–36
31. The complexity of the decision problem for the first order theory of algebraically closed fields
    
    Izv. Akad. Nauk SSSR Ser. Mat., 50:5 (1986),  1106–1120
32. Finding real solutions of systems of algebraic inequalities in subexponential time
    
    Dokl. Akad. Nauk SSSR, 283:6 (1985),  1294–1299
33. Fast factorization of polynomials into irreducible ones and the solution of systems of algebraic equations
    
    Dokl. Akad. Nauk SSSR, 275:6 (1984),  1302–1306
34. Factoring polynomials over a finite field and solving systems of algebraic equations
    
    Zap. Nauchn. Sem. LOMI, 137 (1984),  20–79
35. Lower hounds in the algebraic computational complexity
    
    Zap. Nauchn. Sem. LOMI, 118 (1982),  25–82
36. An analogue of the Bruhat decomposition for the closure of the cone of a Chevalley group of the classical series
    
    Dokl. Akad. Nauk SSSR, 257:5 (1981),  1040–1044
37. On the complexity of the “wild” matrix problems and of the isomorphism of algebras and of graphs
    
    Zap. Nauchn. Sem. LOMI, 105 (1981),  10–17
38. On the Eisenbud–Levine formula over a perfect field
    
    Dokl. Akad. Nauk SSSR, 252:1 (1980),  24–27
39. The rank of a pair of matrices and convolution
    
    Uspekhi Mat. Nauk, 34:2(206) (1979),  193–194
40. Two reductions of graph isomorphism to problems for polynomials
    
    Zap. Nauchn. Sem. LOMI, 88 (1979),  56–61
41. Time bounds of multidimensional Turing machines
    
    Zap. Nauchn. Sem. LOMI, 88 (1979),  47–55
42. Relation between rank and multiplicative complexity of a bilinear form over a commutative Noetherian ring
    
    Zap. Nauchn. Sem. LOMI, 86 (1979),  66–81
43. The algebraic complexity of computing a family of bilinear forms
    
    Zh. Vychisl. Mat. Mat. Fiz., 19:3 (1979),  563–580
44. Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms
    
    Dokl. Akad. Nauk SSSR, 234:1 (1977),  15–18
45. Problem of path connections in graphs
    
    Zap. Nauchn. Sem. LOMI, 68 (1977),  26–29
46. A lower bound for the computational complexity of a set of disjunctives in a monotone basis
    
    Zap. Nauchn. Sem. LOMI, 68 (1977),  19–25
47. Application of separability and independence notions for proving lower bounds of circuit complexity
    
    Zap. Nauchn. Sem. LOMI, 60 (1976),  38–48
48. Kolmogoroff algorithms are stronger than turing machines
    
    Zap. Nauchn. Sem. LOMI, 60 (1976),  29–37
49. On the algebraic complexity of a pair of bilinear forms
    
    Zap. Nauchn. Sem. LOMI, 47 (1974),  159–163


50. Nikolai Aleksandrovich Shanin (obituary)
    
    Uspekhi Mat. Nauk, 68:4(412) (2013),  173–176
51. Nikolai Aleksandrovich Shanin (on his 80th birthday)
    
    Uspekhi Mat. Nauk, 56:3(339) (2001),  181–184