Persons
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
 
Grigor'ev, Dmitrii Yur'evich
Head Scientist Researcher
Doctor of physico-mathematical sciences (1985)
Speciality: 01.01.06 (Mathematical logic, algebra, and number theory)
E-mail:
Website: https://en.wikipedia.org/wiki/Dima_Grigoriev
Keywords: Algebraic Complexity.

Subject:

Algebra, Complexity

Biography

1979 PhD (Candidate of Sciences) in Physics and Mathematics
1985 Doctor of Science (higher doctorate)
1992 Head of Laboratory of algorithmic methods Leningrad Department of the Steklov Mathematical Institute
1992–1998 Full Professor at Penn State University
1998 Research Director at CNRS, University of Rennes 1
2008 Research Director at CNRS, Laboratory Paul Painleve University Lille 1, France
   
Main publications:
  1. Dima Grigoriev, Vladimir V. Podolskii, “Complexity of tropical and min-plus linear prevarieties”, Computational Complexity, 24:1 (2015), 31–64  mathnet  crossref  mathscinet
  2. D. Grigoriev, V. V. Podolskii, “Tropical effective primary and dual Nullstellensatz”, Leibniz International Proc. in Inform., 30 (2015), 379–391  mathscinet
  3. Dima Grigoriev, “Analogue of Newton.Puiseux series for non-holonomic D-modules and factoring”, Mosc. Math.Journal, 9:4 (2009), 775–800  mathscinet
  4. D. Yu. Grigorev, A. L. Chistov, “Slozhnost standartnogo bazisa D-modulya”, Algebra i analiz, 20:5 (2008), 41–82  mathnet  mathscinet
  5. D. Grigoriev, S. Fomin, G. Koshevoy, “Subtraction-free complexity, cluster transformations, and spanning trees”, Found. Comput. Math., 16 (2016), 1–31  crossref  mathscinet

https://www.mathnet.ru/eng/person11043
List of publications on Google Scholar
https://mathscinet.ams.org/mathscinet/MRAuthorID/208676

Publications in Math-Net.Ru Citations
2020
1. Dima Grigoriev, Vladimir V. Podolskii, “Tropical Combinatorial Nullstellensatz and sparse polynomials”, Found. Comput. Math., 20 (2020),  753–781  mathnet  mathscinet  isi  scopus 4
2018
2. Dima Grigoriev, Vladimir V. Podolskii, “Tropical effective primary and dual nullstellensätze”, Discrete Comput. Geom., 59:3 (2018),  507–552  mathnet  mathscinet  isi  scopus 8
2017
3. D. Yu. Grigor'ev, V. V. Podolskii, “Tropical Combinatorial Nullstellensatz and Fewnomials Testing”, Lecture Notes in Comput. Sci., 10472 (2017),  284–297  mathnet  mathscinet  isi  scopus 1
2015
4. Dima Grigoriev, Vladimir V. Podolskii, “Complexity of tropical and min-plus linear prevarieties”, Comput. Complexity, 24:1 (2015),  31–64  mathnet  mathscinet  zmath  isi  scopus 16
5. D. Grigoriev, V. V. Podolskii, “Tropical effective primary and dual Nullstellensátz”, Leibniz Internat. Proc. in Inform., 30 (2015),  379–391  mathnet  mathscinet  scopus
2009
6. Dima Grigoriev, “Analogue of Newton–Puiseux series for non-holonomic $D$-modules and factoring”, Mosc. Math. J., 9:4 (2009),  775–800  mathnet  mathscinet  isi 4
2008
7. D. Grigoriev, A. Kojevnikov, S. J. Nikolenko, “Algebraic cryptography: new constructions and their security against provable break”, Algebra i Analiz, 20:6 (2008),  119–147  mathnet  mathscinet  zmath; St. Petersburg Math. J., 20:6 (2009), 937–953  isi 4
8. D. Yu. Grigoriev, A. L. Chistov, “Complexity of the Standard Basis of a $D$-Module”, Algebra i Analiz, 20:5 (2008),  41–82  mathnet  mathscinet  zmath; St. Petersburg Math. J., 20:5 (2009), 709–736  isi 8
9. S. Vakulenko, D. Grigoriev, “Instability, complexity, and evolution”, Zap. Nauchn. Sem. POMI, 360 (2008),  31–69  mathnet  elib; J. Math. Sci. (N. Y.), 158:6 (2009), 787–808  scopus 1
10. E. A. Hirsch, D. Yu. Grigor'ev, K. V. Pervyshev, “Time hierarchies for cryptographic function inversion with advice”, Zap. Nauchn. Sem. POMI, 358 (2008),  54–76  mathnet; J. Math. Sci. (N. Y.), 158:5 (2009), 633–644  scopus 1
2005
11. S. A. Vakulenko, D. Yu. Grigor'ev, “Evolution in random environment and structural instability”, Zap. Nauchn. Sem. POMI, 325 (2005),  28–60  mathnet  mathscinet; J. Math. Sci. (N. Y.), 138:3 (2006), 5644–5662  scopus 2
2002
12. D. Yu. Grigor'ev, E. A. Hirsch, D. V. Pasechnik, “Complexity of semialgebraic proofs”, Mosc. Math. J., 2:4 (2002),  647–679  mathnet  mathscinet  zmath  isi 35
13. D. Yu. Grigor'ev, I. N. Ponomarenko, “On non-abelian homomorphic public-key cryptosystems”, Zap. Nauchn. Sem. POMI, 293 (2002),  39–58  mathnet  mathscinet  zmath; J. Math. Sci. (N. Y.), 126:3 (2005), 1158–1166 3
14. D. Yu. Grigor'ev, “Public-key cryptography and invariant theory”, Zap. Nauchn. Sem. POMI, 293 (2002),  26–38  mathnet  mathscinet  zmath; J. Math. Sci. (N. Y.), 126:3 (2005), 1152–1157 4
2001
15. D. Yu. Grigor'ev, “Testing the shift-equivalence of polynomials using quantum machines”, Itogi Nauki i Tekhniki. Sovrem. Mat. Pril. Temat. Obz., 34 (2001),  98–116  mathnet  mathscinet  zmath; J. Math. Sci., 82:1 (1996), 3184–3193 2
16. D. Yu. Grigor'ev, “Double-exponential growth of the number of vectors of solutions of polynomial systems”, Zap. Nauchn. Sem. POMI, 277 (2001),  47–52  mathnet  mathscinet  zmath; J. Math. Sci. (N. Y.), 118:2 (2003), 4963–4965
1998
17. D. Yu. Grigor'ev, A. O. Slisenko, “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  mathnet  mathscinet  zmath; St. Petersburg Math. J., 10:2 (1999), 315–332 2
1994
18. D. Yu. Grigoriev, “Deviation theorems for pfaffian sigmoids”, Algebra i Analiz, 6:1 (1994),  127–131  mathnet  mathscinet  zmath; St. Petersburg Math. J., 6:1 (1995), 107–111 5
19. D. Yu. Grigoriev, “Deviation theorems for solutions of linear ordinary differential equations and applications to parallel complexity of sigmoids”, Algebra i Analiz, 6:1 (1994),  110–126  mathnet  mathscinet  zmath; St. Petersburg Math. J., 6:1 (1995), 89–106 5
1991
20. D. Yu. Grigor'ev, “Complexity of irreducibility testing for a system of linear ordinary differential equations”, Zap. Nauchn. Sem. LOMI, 192 (1991),  60–68  mathnet  mathscinet  zmath; J. Math. Sci., 70:4 (1994), 1881–1886
21. D. Yu. Grigor'ev, “Complexity of solving linears systems in the rings of differential operators”, Zap. Nauchn. Sem. LOMI, 192 (1991),  47–60  mathnet  mathscinet  zmath; J. Math. Sci., 70:4 (1994), 1873–1880 2
22. N. N. Vorobjov (jr.), D. Yu. Grigor'ev, “Finding connected components of a semialgebraic set in subexponential time”, Zap. Nauchn. Sem. LOMI, 192 (1991),  3–46  mathnet  mathscinet  zmath; J. Math. Sci., 70:4 (1994), 1847–1872 1
1990
23. N. N. Vorobjov (Jr.), D. Yu. Grigor'ev, “Determination of the number of connected components of a semi-algebraic set in subexponential time”, Dokl. Akad. Nauk SSSR, 314:5 (1990),  1040–1043  mathnet  mathscinet  zmath; Dokl. Math., 42:2 (1991), 563–566
1989
24. D. Yu. Grigor'ev, “The complexity of computing the genus of a system of exterior differential equations”, Dokl. Akad. Nauk SSSR, 306:1 (1989),  26–30  mathnet  mathscinet  zmath; Dokl. Math., 39:3 (1989), 432–436 1
25. D. Yu. Grigor'ev, “Complexity of computations in commutative division of the USSR Academy of Sciences”, Mat. Zametki, 46:1 (1989),  96–104  mathnet  mathscinet  zmath; Math. Notes, 46:1 (1989), 563–568  isi
26. D. Yu. Grigor'ev, “Complexity of factoring and GCD calculating for linear ordinary differential operators”, Zap. Nauchn. Sem. LOMI, 176 (1989),  68–103  mathnet  mathscinet  zmath; J. Soviet Math., 59:3 (1992), 823–841
27. D. Yu. Grigor'ev, “Complexity of quantifier elimination in the theory of ordinary differentially closed fields”, Zap. Nauchn. Sem. LOMI, 176 (1989),  53–67  mathnet  mathscinet  zmath; J. Soviet Math., 59:3 (1992), 814–822 1
1988
28. D. Yu. Grigor'ev, “Complexity of the factorization of a linear ordinary differential operator”, Dokl. Akad. Nauk SSSR, 303:1 (1988),  16–20  mathnet  mathscinet  zmath; Dokl. Math., 38:3 (1989), 452–457
29. D. Yu. Grigor'ev, “Complexity of deciding the first-order theory of real closed fields”, Zap. Nauchn. Sem. LOMI, 174 (1988),  53–100  mathnet  mathscinet  zmath; J. Soviet Math., 55:2 (1991), 1553–1587
30. N. N. Vorobjov (Jr.), D. Yu. Grigor'ev, “Solving systems of polynomial inequalities over real closed fields in subexponential time”, Zap. Nauchn. Sem. LOMI, 174 (1988),  3–36  mathnet  mathscinet  zmath; J. Soviet Math., 55:2 (1991), 1519–1540 1
1986
31. D. Yu. Grigor'ev, “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  mathnet  mathscinet  zmath; Math. USSR-Izv., 29:2 (1987), 459–475 9
1985
32. N. N. Vorobjov (Jr.), D. Yu. Grigor'ev, “Finding real solutions of systems of algebraic inequalities in subexponential time”, Dokl. Akad. Nauk SSSR, 283:6 (1985),  1294–1299  mathnet  mathscinet  zmath
1984
33. D. Yu. Grigor'ev, A. L. Chistov, “Fast factorization of polynomials into irreducible ones and the solution of systems of algebraic equations”, Dokl. Akad. Nauk SSSR, 275:6 (1984),  1302–1306  mathnet  mathscinet  zmath
34. D. Yu. Grigor'ev, “Factoring polynomials over a finite field and solving systems of algebraic equations”, Zap. Nauchn. Sem. LOMI, 137 (1984),  20–79  mathnet  mathscinet  zmath 3
1982
35. D. Yu. Grigor'ev, “Lower hounds in the algebraic computational complexity”, Zap. Nauchn. Sem. LOMI, 118 (1982),  25–82  mathnet  mathscinet  zmath 5
1981
36. D. Yu. Grigor'ev, “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  mathnet  mathscinet  zmath
37. D. Yu. Grigor'ev, “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  mathnet  mathscinet  zmath; J. Soviet Math., 22:3 (1983), 1285–1289 3
1980
38. D. Yu. Grigor'ev, N. V. Ivanov, “On the Eisenbud–Levine formula over a perfect field”, Dokl. Akad. Nauk SSSR, 252:1 (1980),  24–27  mathnet  mathscinet  zmath
1979
39. D. Yu. Grigor'ev, “The rank of a pair of matrices and convolution”, Uspekhi Mat. Nauk, 34:2(206) (1979),  193–194  mathnet  mathscinet  zmath; Russian Math. Surveys, 34:2 (1979), 231–232 2
40. D. Yu. Grigor'ev, “Two reductions of graph isomorphism to problems for polynomials”, Zap. Nauchn. Sem. LOMI, 88 (1979),  56–61  mathnet  mathscinet  zmath; J. Soviet Math., 20:4 (1982), 2296–2298 5
41. D. Yu. Grigor'ev, “Time bounds of multidimensional Turing machines”, Zap. Nauchn. Sem. LOMI, 88 (1979),  47–55  mathnet  mathscinet  zmath; J. Soviet Math., 20:4 (1982), 2290–2295 2
42. D. Yu. Grigor'ev, “Relation between rank and multiplicative complexity of a bilinear form over a commutative Noetherian ring”, Zap. Nauchn. Sem. LOMI, 86 (1979),  66–81  mathnet  mathscinet  zmath; J. Soviet Math., 17:4 (1981), 1987–1998 3
43. D. Yu. Grigor'ev, “The algebraic complexity of computing a family of bilinear forms”, Zh. Vychisl. Mat. Mat. Fiz., 19:3 (1979),  563–580  mathnet  mathscinet  zmath; U.S.S.R. Comput. Math. Math. Phys., 19:3 (1979), 1–20 2
1977
44. D. Yu. Grigor'ev, “Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms”, Dokl. Akad. Nauk SSSR, 234:1 (1977),  15–18  mathnet  mathscinet  zmath 1
45. D. Yu. Grigor'ev, “Problem of path connections in graphs”, Zap. Nauchn. Sem. LOMI, 68 (1977),  26–29  mathnet  mathscinet  zmath; J. Soviet Math., 15:1 (1981), 14–16
46. D. Yu. Grigor'ev, “A lower bound for the computational complexity of a set of disjunctives in a monotone basis”, Zap. Nauchn. Sem. LOMI, 68 (1977),  19–25  mathnet  mathscinet  zmath; J. Soviet Math., 15:1 (1981), 11–14 4
1976
47. D. Yu. Grigor'ev, “Application of separability and independence notions for proving lower bounds of circuit complexity”, Zap. Nauchn. Sem. LOMI, 60 (1976),  38–48  mathnet  mathscinet  zmath; J. Soviet Math., 14:5 (1980), 1450–1457 11
48. D. Yu. Grigor'ev, “Kolmogoroff algorithms are stronger than turing machines”, Zap. Nauchn. Sem. LOMI, 60 (1976),  29–37  mathnet  mathscinet  zmath; J. Soviet Math., 14:5 (1980), 1445–1450 8
1974
49. D. Yu. Grigor'ev, “On the algebraic complexity of a pair of bilinear forms”, Zap. Nauchn. Sem. LOMI, 47 (1974),  159–163  mathnet  mathscinet  zmath 1
2013
50. M. A. Vsemirnov, È. A. Hirsch, D. Yu. Grigor'ev, G. V. Davydov, E. Ya. Dantsin, I. D. Zaslavskii, È. F. Karavaev, B. Yu. Konev, N. K. Kossovskii, V. A. Lifschitz, M. Margenstern, Yu. V. Matiyasevich, G. E. Mints, V. P. Orevkov, R. Pliuškevičius, A. O. Slisenko, S. V. Solov'ev, V. P. Chernov, “Nikolai Aleksandrovich Shanin (obituary)”, Uspekhi Mat. Nauk, 68:4(412) (2013),  173–176  mathnet  mathscinet  elib; Russian Math. Surveys, 68:4 (2013), 763–767  isi  elib  scopus
2001
51. M. A. Vsemirnov, E. A. Hirsch, D. Yu. Grigor'ev, G. V. Davydov, E. Ya. Dantsin, A. A. Ivanov, B. Yu. Konev, V. A. Lifshits, Yu. V. Matiyasevich, G. E. Mints, V. P. Orevkov, A. O. Slisenko, “Nikolai Aleksandrovich Shanin (on his 80th birthday)”, Uspekhi Mat. Nauk, 56:3(339) (2001),  181–184  mathnet  mathscinet  zmath; Russian Math. Surveys, 56:3 (2001), 601–605  isi 1

Presentations in Math-Net.Ru
1. On a tropical version of the Jacobian conjecture
D. Yu. Grigor'ev
Adian 90: Conference on Mathematical Logic, Algebra, and Computation
July 7, 2021 17:00   
2. Проблема P-NP и сложность задач компьютерной алгебры
D. Yu. Grigor'ev
Meetings of the St. Petersburg Mathematical Society
May 7, 2013 17:30
3. Nash conjecture for binomial varieties and multidimensional Euclidean algorithm
D. Grigoriev
Mathematics - XXI century. PDMI 70th anniversary
September 15, 2010 13:30   
4. Сложностная криптография: полные криптосистемы с открытым ключом
E. A. Hirsch, D. Yu. Grigor'ev, K. V. Pervyshev
Meetings of the Moscow Mathematical Society
April 11, 2006
5. Algebraic methods in cryptography
D. Yu. Grigoriev
General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences
December 23, 2004

Organisations
 
  Contact us:
  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024