# zbMATH — the first resource for mathematics

## Grigor’ev, Dmitriĭ Yur’evich

Compute Distance To:
 Author ID: grigorev.dimitri-yu Published as: Grigoriev, Dima; Grigor’ev, D. Yu.; Grigoriev, D.; Grigor’ev, D. Ju.; Grigoriev, D. Yu.; Grigoriev, Dima Yu.; Grigor’ev, Dima Yurevitch; Grigor’ev, Dimitri Yu.; Grigoriev, Dimitri; Grigoriev, Dmitry; Grigor’ev, D. Homepage: https://logic.pdmi.ras.ru/~grigorev/ External Links: MGP · Math-Net.Ru · Wikidata · dblp
 Documents Indexed: 218 Publications since 1974, including 10 Books
all top 5

#### Co-Authors

 86 single-authored 19 Karpinski, Marek 19 Vorob’ëv, Nikolaĭ N. jun. 12 Shpilrain, Vladimir 10 Weber, Andreas Günter 9 Hirsch, Edward A. 8 Radulescu, Ovidiu 6 Schwarz, Fritz 6 Singer, Michael F. 5 Errami, Hassan 5 Podol’skiĭ, Vladimir Vladimirovich 5 Ponomarenko, Ilya Nikolaevich 5 Slisenko, A. O. 4 Chistov, Alexandre L. 4 Cucker, Felipe 4 Pasechnik, Dmitrii V. 3 England, Matthew 3 Matiyasevich, Yuriĭ Vladimirovich 3 Milman, Pierre D. 3 Orevkov, V. P. 3 Samal, Satya Swarup 3 Slissenko, Anatol 3 Smolensky, Roman 2 Artemov, Sergei 2 Bessonov, Mariya 2 Bradford, Russell J. 2 Buss, Sam 2 Dantsin, E. Ya. 2 Davenport, James Harold 2 Davydov, G. V. 2 Diekert, Volker 2 Eiswirth, Markus 2 Fomin, Sergey Vladimirovich 2 Fröhlich, Holger 2 Gerdt, Vladimir P. 2 Hoyt, Charles 2 Impagliazzo, Russell 2 Konev, B. Yu. 2 Koshevoy, Gleb A. 2 Košta, Marek 2 Lakshman, Y. N. 2 Lifschitz, Vladimir 2 Meyer auf der Heide, Friedhelm 2 Mints, Grigoriĭ Efroimovich 2 Noel, Vincent 2 Odlyzko, Andrew M. 2 Pitassi, Toniann 2 Seiler, Werner M. 2 Vakulenko, Sergei A. 2 Vsemirnov, M. A. 2 Yao, Andrew Chi-Chih 1 Alekseev, Yaroslav 1 Beauquier, Danièle 1 Bierstone, Edward 1 Burago, Dmitri 1 Canny, John F. 1 Chernov, V. P. 1 Davydow, Alex 1 Girsh, È. A. 1 Grigorchuk, Rostislav Ivanovich 1 Grigorieva, Alla 1 Heintz, Joos 1 Iosif, Alexandru 1 Ivanov, Aleksandr Aleksandrovich 1 Ivanov, Nikolai V. 1 Karavaev, Eh. F. 1 Kish, Laszlo B. 1 Kossovsky, N. K. 1 Margenstern, Maurice 1 Muzychuk, Mikhail E. 1 Nikolenko, S. J. 1 Nikolenko, Sergey I. 1 Nogneng, Dorian 1 Pervyshev, K. V. 1 Pervyshev, Konstantin 1 Pliuškevičius, Regimantas 1 Rahkooy, Hamid 1 Razborov, Aleksandr Aleksandrovich 1 Roy, Marie-Françoise 1 Schost, Éric 1 Solernó, Pablo 1 Solov’ëv, Sergeĭ Vladimirovich 1 Sutcliffe, Paul M. 1 Tchrakian, D. H. 1 Tenenbaum, Gérald 1 Tzameret, Iddo 1 Vakulenko, Sergey A. 1 Włodarczyk, Jarosław 1 Zaslavskii, Igor Dmitrievich
all top 5

#### Serials

 16 Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni V. A. Steklova 15 Journal of Soviet Mathematics 11 Computational Complexity 10 Theoretical Computer Science 9 Journal of Mathematical Sciences (New York) 8 Soviet Mathematics. Doklady 6 SIAM Journal on Computing 6 Journal of Symbolic Computation 6 Groups, Complexity, Cryptology 5 Advances in Applied Mathematics 5 Journal of Complexity 5 Applicable Algebra in Engineering, Communication and Computing 5 St. Petersburg Mathematical Journal 5 Foundations of Computational Mathematics 4 Discrete & Computational Geometry 3 Russian Mathematical Surveys 3 Annals of Pure and Applied Logic 2 Communications in Algebra 2 Advances in Mathematics 2 International Journal of Foundations of Computer Science 2 Theory of Computing Systems 2 Moscow Mathematical Journal 2 Mathematical Modelling of Natural Phenomena 1 Journal of Computational Physics 1 Mathematical Notes 1 Physics Letters. B 1 Uspekhi Matematicheskikh Nauk [N. S.] 1 Zhurnal Vychislitel’noĭ Matematiki i Matematicheskoĭ Fiziki 1 Bulletin of Mathematical Biology 1 Computing 1 Journal of Computer and System Sciences 1 Mathematics of the USSR. Izvestiya 1 Studies in Applied Mathematics 1 Transactions of the American Mathematical Society 1 Annales Societatis Mathematicae Polonae. Series IV 1 Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya 1 U.S.S.R. Computational Mathematics and Mathematical Physics 1 Comptes Rendus de l’Académie des Sciences. Série I 1 Zapiski Nauchnykh Seminarov POMI 1 The Asian Journal of Mathematics 1 Comptes Rendus. Mathématique. Académie des Sciences, Paris 1 International Journal of Pure and Applied Mathematics 1 Lecture Notes in Computer Science 1 Mathematics in Computer Science 1 Arnold Mathematical Journal
all top 5

#### Fields

 144 Computer science (68-XX) 44 Algebraic geometry (14-XX) 32 Field theory and polynomials (12-XX) 29 Mathematical logic and foundations (03-XX) 27 Information and communication theory, circuits (94-XX) 22 Linear and multilinear algebra; matrix theory (15-XX) 22 Numerical analysis (65-XX) 18 Commutative algebra (13-XX) 18 Ordinary differential equations (34-XX) 18 Biology and other natural sciences (92-XX) 13 Combinatorics (05-XX) 11 Associative rings and algebras (16-XX) 9 General and overarching topics; collections (00-XX) 9 Number theory (11-XX) 7 Partial differential equations (35-XX) 6 Real functions (26-XX) 5 Several complex variables and analytic spaces (32-XX) 4 Group theory and generalizations (20-XX) 4 Operator theory (47-XX) 3 History and biography (01-XX) 3 Convex and discrete geometry (52-XX) 3 Probability theory and stochastic processes (60-XX) 3 Quantum theory (81-XX) 3 Operations research, mathematical programming (90-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Approximations and expansions (41-XX) 2 Global analysis, analysis on manifolds (58-XX) 1 Topological groups, Lie groups (22-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Systems theory; control (93-XX)

#### Citations contained in zbMATH Open

140 Publications have been cited 828 times in 532 Documents Cited by Year
Solving systems of polynomial inequalities in subexponential time. Zbl 0662.12001
Grigor’ev, D. Yu.; Vorobjov, N. N. jun.
1988
Complexity of deciding Tarski algebra. Zbl 0689.03021
Grigor’ev, D. Yu.
1988
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. Zbl 0711.68059
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F.
1990
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Zbl 0974.68192
Grigoriev, D.
2001
Complexity of factoring and calculating the GCD of linear ordinary differential operators. Zbl 0728.68067
Grigor’ev, D. Yu.
1990
Counting connected components of a semialgebraic set in subexponential time. Zbl 0900.68253
Grigor’ev, D. Yu.; Vorobjov, N. N. jun.
1992
Complexity of Positivstellensatz proofs for the knapsack. Zbl 0992.68077
Grigoriev, D.
2001
Solving ordinary differential equations in terms of series with real exponents. Zbl 0758.12004
Grigor’ev, D. Yu.; Singer, M. F.
1991
Polynomial-time factoring of the multivariable polynomials over a global field. Zbl 0509.68029
Chistov, A. L.; Grigor’ev, D. Yu.
1982
An exponential lower bound for depth 3 arithmetic circuits. Zbl 1028.68069
Grigoriev, Dima; Karpinski, Marek
1998
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1007.03052
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
2001
Complexity of Null- and Positivstellensatz proofs. Zbl 0992.03073
Grigoriev, Dima; Vorobjov, Nicolai
2002
Factoring and solving linear partial differential equations. Zbl 1052.35008
Grigoriev, D.; Schwarz, F.
2004
Detection of Hopf bifurcations in chemical reaction networks using convex coordinates. Zbl 1349.92168
Errami, Hassan; Eiswirth, Markus; Grigoriev, Dima; Seiler, Werner M.; Sturm, Thomas; Weber, Andreas
2015
Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Zbl 1040.68045
Grigoriev, D.; Razborov, A.
2000
On the power of real Turing machines over binary inputs. Zbl 0874.68110
Cucker, Felipe; Grigoriev, Dima
1997
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Zbl 1082.14065
Grigoriev, Dima; Pasechnik, Dmitrii V.
2005
Factorization of polynomials over a finite field and the solution of systems of algebraic equations. Zbl 0596.12023
Grigor’ev, D. Yu.
1986
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
2013
A complete public-key cryptosystem. Zbl 1158.94384
Grigoriev, Dima; Hirsch, Edward A.; Pervyshev, Konstantin
2009
Complexity of quantifier elimination in the theory of algebraically closed fields. Zbl 0562.03015
Chistov, A. L.; Grigor’ev, D. Yu.
1984
Additive complexity in directed computations. Zbl 0486.68028
Grigor’ev, D. Yu.
1982
A zero-test and an interpolation algorithm for the shifted sparse polynomials. Zbl 0809.68072
Grigoriev, Dima; Karpinski, Marek
1993
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
2015
Fast decomposition of polynomials into irreducible ones and the solution of systems of algebraic equations. Zbl 0596.12021
Grigor’ev, D. Yu.; Chistov, A. L.
1984
Computational complexity of sparse rational interpolation. Zbl 0802.68060
Grigoriev, Dima; Karpinski, Marek; Singer, Michael F.
1994
Complexity of semialgebraic proofs. Zbl 1027.03044
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrij V.
2002
Complexity of quantifier elimination in the theory of ordinary differential equations. Zbl 1209.68679
Grigor’ev, D. Yu.
1989
Tropical cryptography. Zbl 1301.94114
2014
Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. Zbl 1326.68354
Grigoriev, Dima; Vorobjov, Nicolai
2000
Factorization of polynomials over a finite field and solution of a system of algebraic equations. Zbl 0561.12011
Grigor’ev, D. Yu.
1984
Effective Hironaka resolution and its complexity. Zbl 1315.14022
Bierstone, Edward; Grigoriev, Dima; Milman, Pierre; Włodarczyk, Jarosław
2011
Authentication from matrix conjugation. Zbl 1191.94104
2009
Generalized Loewy-decomposition of $$D$$-modules. Zbl 1360.13061
Grigoriev, Dima; Schwarz, Fritz
2005
Complexity lower bounds for computation trees with elementary transcendental function gates. Zbl 0877.68086
Grigoriev, D.; Vorobjov, N.
1996
Loewy and primary decompositions of $$\mathcal D$$-modules. Zbl 1126.35008
Grigoriev, D.; Schwarz, F.
2007
Complexity of semi-algebraic proofs. Zbl 1054.03035
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
2002
Authentication schemes from actions on graphs, groups, or rings. Zbl 1236.94076
2010
An application of separability and independence notions for obtaining lower bounds of circuit complexity. Zbl 0341.94020
Grigor’ev, D. Ju.
1976
Tropicalization and tropical equilibration of chemical reactions. Zbl 1320.92091
Noel, Vincent; Grigoriev, Dima; Vakulenko, Sergei; Radulescu, Ovidiu
2014
The interpolation problem for $$k$$-sparse sums of eigenfunctions of operators. Zbl 0785.12004
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F.
1991
Weak Bézout inequality for D-modules. Zbl 1080.32010
Grigoriev, Dima
2005
An analogue of the Bruhat decomposition for the closure of the cone of a Chevalley group of the classical series. Zbl 0479.22003
Grigor’ev, D. Yu.
1981
Lower bounds in algebraic computational complexity. Zbl 0563.68040
Grigor’ev, D. Yu.
1985
Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Zbl 1044.68946
Grigoriev, D.
1997
Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane. Zbl 0961.14039
Grigoriev, D.; Slissenko, A.
1998
Tropical geometries and dynamics of biochemical networks application to hybrid cell cycle models. Zbl 1283.92043
Noel, Vincent; Grigoriev, Dima; Vakulenko, Sergei; Radulescu, Ovidiu
2012
Nash resolution for binomial varieties as Euclidean division. A priori termination bound, polynomial complexity in essential dimension 2. Zbl 1287.14004
Grigoriev, Dima; Milman, Pierre D.
2012
Finding connected components of a semialgebraic set in subexponential time. Zbl 0783.14036
Canny, J.; Grigor’ev, D. Yu.; Vorob’ev, N. N. jun.
1992
Homomorphic public-key cryptosystems over groups and rings. Zbl 1149.94318
Grigoriev, Dima; Ponomarenko, Ilia
2004
Lower bounds on testing membership to a polyhedron by algebraic decision trees. Zbl 1345.68158
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
1994
Model reduction of biochemical reactions networks by tropical analysis methods. Zbl 1369.92047
Radulescu, O.; Vakulenko, S.; Grigoriev, D.
2015
Tropical effective primary and dual Nullstellensätze. Zbl 1356.14058
2015
Lower bounds in the algebraic computational complexity. Zbl 0504.68024
Grigor’ev, D. Yu.
1982
Complexity of a standard basis of a $$D$$-module. Zbl 1206.16050
Grigoriev, D. Yu.; Chistov, A. L.
2009
Bounds on the number of connected components for tropical prevarieties. Zbl 1401.14235
Davydow, Alex; Grigoriev, Dima
2017
Topological complexity of the range searching. Zbl 0951.68024
Grigoriev, Dima
2000
Symbolic versus numerical computation and visualization of parameter regions for multistationarity of biological networks. Zbl 1455.92058
England, Matthew; Errami, Hassan; Grigoriev, Dima; Radulescu, Ovidiu; Sturm, Thomas; Weber, Andreas
2017
Algorithms for computing sparse shifts for multivariate polynomials. Zbl 0924.68105
Grigoriev, Dima Yu.; Lakshman, Y. N.
1995
A lower bound for randomized algebraic decision trees. Zbl 0922.68090
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman
1996
Algorithms for sparse rational interpolation. Zbl 0920.65004
Grigoriev, Dima Yu.; Karpinski, Marek
1991
Computational complexity of sparse real algebraic function interpolation. Zbl 0801.68087
Grigoriev, D.; Karpinski, M.; Singer, M. F.
1993
Complexity of gene circuits, Pfaffian functions and the morphogenesis problem. Zbl 1050.92003
Vakulenko, Sergey; Grigoriev, Dmitry
2003
Public-key cryptography and invariant theory. Zbl 1081.94026
Grigoriev, D.
2002
Efficient methods to compute Hopf bifurcations in chemical reaction networks using reaction coordinates. Zbl 1412.34132
Errami, Hassan; Eiswirth, Markus; Grigoriev, Dima; Seiler, Werner M.; Sturm, Thomas; Weber, Andreas
2013
On a tropical dual Nullstellensatz. Zbl 1247.14067
Grigoriev, Dima
2012
Subtraction-free complexity, cluster transformations, and spanning trees. Zbl 1352.68104
Fomin, Sergey; Grigoriev, Dima; Koshevoy, Gleb
2016
Algorithms for computing sparse shifts for multivariate polynomials. Zbl 0968.68199
Grigoriev, Dima Yu.; Lakshman, Y. N.
2000
Imbedding theorems for Turing machines of different dimensions and Kolmogorov’s algorithms. Zbl 0386.03019
Grigor’ev, D. Ju.
1977
Application of separability and independence notions for proving lower bounds of circuit complexity. Zbl 0449.94030
Grigor’ev, D. Yu.
1980
Homomorphic public-key cryptosystems and encrypting Boolean circuits. Zbl 1104.94022
Grigoriev, Dima; Ponomarenko, Ilia
2006
Constructions in public-key cryptography over matrix groups. Zbl 1207.94053
Grigoriev, Dima; Ponomarenko, Ilia
2006
Reduction methods and chaos for quadratic systems of differential equations. Zbl 1359.92036
Vakulenko, S.; Grigoriev, D.; Weber, A.
2015
The complexity of the decision problem for the first order theory of algebraically closed fields. Zbl 0631.03006
Grigor’ev, D. Yu.
1987
Computational complexity in polynomial algebra. Zbl 0667.68054
Grigor’ev, D. Yu.
1987
Skyrmed monopoles. Zbl 0996.81059
Grigoriev, D. Yu.; Sutcliffe, P. M.; Tchrakian, D. H.
2002
Algebraic proof systems over formulas. Zbl 1044.68146
Grigoriev, Dima; Hirsch, Edward A.
2003
Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. Zbl 1075.68090
Burago, D.; Grigoriev, D.; Slissenko, A.
2004
Algebraic cryptography: new constructions and their security against provable break. Zbl 1206.94069
Grigoriev, D.; Kojevnikov, A.; Nikolenko, S. J.
2009
Approximation and complexity: Liouvillean-type theorems for linear differential equations on an interval. Zbl 1001.12007
Grigoriev, Dima
2001
Complexity of solving systems with few independent monomials and applications to mass-action kinetics. Zbl 1373.68461
Grigoriev, Dima; Weber, Andreas
2012
Deviation theorems for Pfaffian sigmoids. Zbl 0844.05090
Grigoriev, D. Yu.
1994
Approximation and complexity. II: Iterated integration. Zbl 1020.68041
Grigoriev, Dima
2002
Identifying the parametric occurrence of multiple steady states for some biological networks. Zbl 1442.92056
Bradford, Russell; Davenport, James H.; England, Matthew; Errami, Hassan; Gerdt, Vladimir; Grigoriev, Dima; Hoyt, Charles; Košta, Marek; Radulescu, Ovidiu; Sturm, Thomas; Weber, Andreas
2020
Counting connected components of a semi-algebraic set in single exponential time. (Comptage des composantes connexes d’un ensemble semi-algébrique en temps simplement exponentiel.) Zbl 0752.14043
Grigor’ev, Dima Yurevitch; Heintz, Joos; Roy, Marie-Françoise; Solernó, Pablo; Vorobjov, Nicolai Nicolaievitch jun.
1990
The rank of a pair of matrices and convolution. Zbl 0432.15019
Grigor’ev, D. Yu.
1979
Tropical effective primary and dual Nullstellensätze. Zbl 1420.14140
2018
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1345.03105
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
1999
Complexity of tropical Schur polynomials. Zbl 1329.65060
Grigoriev, Dima; Koshevoy, Gleb
2016
A geometric method for model reduction of biochemical networks with polynomial rate functions. Zbl 1342.92079
Samal, Satya Swarup; Grigoriev, Dima; Fröhlich, Holger; Weber, Andreas; Radulescu, Ovidiu
2015
On computing algebraic functions using logarithms and exponentials. Zbl 0834.68054
Grigoriev, Dima; Singer, Michael; Yao, Andrew
1995
Finding real solutions of systems of algebraic inequalities in subexponential time. Zbl 0607.65027
Vorob’ev, N. N. jun.; Grigor’ev, D. Yu.
1985
Complexity of decidability for the first order theory of algebraically closed fields. Zbl 0625.03004
Grigor’ev, D. Yu.
1986
Testing shift-equivalence of polynomials using quantum machines. Zbl 0928.68045
Grigoriev, D.
1996
An exponential lower bound on the size of algebraic decision trees for MAX. Zbl 0918.68032
Grigoriev, Dima; Karpinski, Marek; Yao, Andrew C.
1998
Improved lower bound on testing membership to a polyhedron by algebraic decision trees. Zbl 0938.68868
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
1995
Two reductions of graph isomorphism to problems on polynomials. Zbl 0493.03016
Grigor’ev, D. Yu.
1982
There are no sparse NP$$_{w}$$-hard sets. Zbl 0992.68061
Cucker, Felipe; Grigoriev, Dima
2001
Randomized complexity lower bounds. Zbl 1027.68608
Grigoriev, D.
1998
Exponential lower bound for static semi-algebraic proofs. Zbl 1056.03037
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
2002
Identifying the parametric occurrence of multiple steady states for some biological networks. Zbl 1442.92056
Bradford, Russell; Davenport, James H.; England, Matthew; Errami, Hassan; Gerdt, Vladimir; Grigoriev, Dima; Hoyt, Charles; Košta, Marek; Radulescu, Ovidiu; Sturm, Thomas; Weber, Andreas
2020
Tropical cryptography. II: Extensions by homomorphisms. Zbl 1451.14179
2019
Tropical effective primary and dual Nullstellensätze. Zbl 1420.14140
2018
Tropical Newton-Puiseux polynomials. Zbl 1453.14148
Grigoriev, Dima
2018
Orthogonal tropical linear prevarieties. Zbl 1453.14147
Grigoriev, Dima; Vorobjov, Nicolai
2018
Upper bounds on Betti numbers of tropical prevarieties. Zbl 1420.14141
Grigoriev, Dima; Vorobjov, Nicolai
2018
Bounds on the number of connected components for tropical prevarieties. Zbl 1401.14235
Davydow, Alex; Grigoriev, Dima
2017
Symbolic versus numerical computation and visualization of parameter regions for multistationarity of biological networks. Zbl 1455.92058
England, Matthew; Errami, Hassan; Grigoriev, Dima; Radulescu, Ovidiu; Sturm, Thomas; Weber, Andreas
2017
A case study on the parametric occurrence of multiple steady states. Zbl 1444.92034
Bradford, Russell; Davenport, James H.; England, Matthew; Errami, Hassan; Gerdt, Vladimir; Grigoriev, Dima; Hoyt, Charles; Košta, Marek; Radulescu, Ovidiu; Sturm, Thomas; Weber, Andreas
2017
Tropical differential equations. Zbl 1348.14140
Grigoriev, Dima
2017
Subtraction-free complexity, cluster transformations, and spanning trees. Zbl 1352.68104
Fomin, Sergey; Grigoriev, Dima; Koshevoy, Gleb
2016
Complexity of tropical Schur polynomials. Zbl 1329.65060
Grigoriev, Dima; Koshevoy, Gleb
2016
Detection of Hopf bifurcations in chemical reaction networks using convex coordinates. Zbl 1349.92168
Errami, Hassan; Eiswirth, Markus; Grigoriev, Dima; Seiler, Werner M.; Sturm, Thomas; Weber, Andreas
2015
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
2015
Model reduction of biochemical reactions networks by tropical analysis methods. Zbl 1369.92047
Radulescu, O.; Vakulenko, S.; Grigoriev, D.
2015
Tropical effective primary and dual Nullstellensätze. Zbl 1356.14058
2015
Reduction methods and chaos for quadratic systems of differential equations. Zbl 1359.92036
Vakulenko, S.; Grigoriev, D.; Weber, A.
2015
A geometric method for model reduction of biochemical networks with polynomial rate functions. Zbl 1342.92079
Samal, Satya Swarup; Grigoriev, Dima; Fröhlich, Holger; Weber, Andreas; Radulescu, Ovidiu
2015
Polynomial complexity recognizing a tropical linear variety. Zbl 1439.14175
Grigoriev, Dima
2015
Analysis of reaction network systems using tropical geometry. Zbl 1400.92201
Samal, Satya Swarup; Grigoriev, Dima; Fröhlich, Holger; Radulescu, Ovidiu
2015
Algorithms to study large metabolic network dynamics. Zbl 1331.34087
Grigoriev, D.; Samal, S. S.; Vakulenko, S.; Weber, A.
2015
Tropical cryptography. Zbl 1301.94114
2014
Tropicalization and tropical equilibration of chemical reactions. Zbl 1320.92091
Noel, Vincent; Grigoriev, Dima; Vakulenko, Sergei; Radulescu, Ovidiu
2014
Yao’s millionaires’ problem and decoy-based public key encryption by classical physics. Zbl 1302.94049
2014
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
2013
Efficient methods to compute Hopf bifurcations in chemical reaction networks using reaction coordinates. Zbl 1412.34132
Errami, Hassan; Eiswirth, Markus; Grigoriev, Dima; Seiler, Werner M.; Sturm, Thomas; Weber, Andreas
2013
Secrecy without one-way functions. Zbl 1290.94080
2013
Tropical geometries and dynamics of biochemical networks application to hybrid cell cycle models. Zbl 1283.92043
Noel, Vincent; Grigoriev, Dima; Vakulenko, Sergei; Radulescu, Ovidiu
2012
Nash resolution for binomial varieties as Euclidean division. A priori termination bound, polynomial complexity in essential dimension 2. Zbl 1287.14004
Grigoriev, Dima; Milman, Pierre D.
2012
On a tropical dual Nullstellensatz. Zbl 1247.14067
Grigoriev, Dima
2012
Complexity of solving systems with few independent monomials and applications to mass-action kinetics. Zbl 1373.68461
Grigoriev, Dima; Weber, Andreas
2012
No-leak authentication by the Sherlock Holmes method. Zbl 1272.94081
2012
Effective Hironaka resolution and its complexity. Zbl 1315.14022
Bierstone, Edward; Grigoriev, Dima; Milman, Pierre; Włodarczyk, Jarosław
2011
Authentication schemes from actions on graphs, groups, or rings. Zbl 1236.94076
2010
A low complexity probabilistic test for integer multiplication. Zbl 1196.68104
Grigoriev, Dima; Tenenbaum, Gérald
2010
A complete public-key cryptosystem. Zbl 1158.94384
Grigoriev, Dima; Hirsch, Edward A.; Pervyshev, Konstantin
2009
Authentication from matrix conjugation. Zbl 1191.94104
2009
Complexity of a standard basis of a $$D$$-module. Zbl 1206.16050
Grigoriev, D. Yu.; Chistov, A. L.
2009
Algebraic cryptography: new constructions and their security against provable break. Zbl 1206.94069
Grigoriev, D.; Kojevnikov, A.; Nikolenko, S. J.
2009
Loewy and primary decompositions of $$\mathcal D$$-modules. Zbl 1126.35008
Grigoriev, D.; Schwarz, F.
2007
Homomorphic public-key cryptosystems and encrypting Boolean circuits. Zbl 1104.94022
Grigoriev, Dima; Ponomarenko, Ilia
2006
Constructions in public-key cryptography over matrix groups. Zbl 1207.94053
Grigoriev, Dima; Ponomarenko, Ilia
2006
Algorithms and complexity in biological pattern formation problems. Zbl 1094.92008
Grigoriev, D.; Vakulenko, S.
2006
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Zbl 1082.14065
Grigoriev, Dima; Pasechnik, Dmitrii V.
2005
Generalized Loewy-decomposition of $$D$$-modules. Zbl 1360.13061
Grigoriev, Dima; Schwarz, Fritz
2005
Weak Bézout inequality for D-modules. Zbl 1080.32010
Grigoriev, Dima
2005
Factoring and solving linear partial differential equations. Zbl 1052.35008
Grigoriev, D.; Schwarz, F.
2004
Homomorphic public-key cryptosystems over groups and rings. Zbl 1149.94318
Grigoriev, Dima; Ponomarenko, Ilia
2004
Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. Zbl 1075.68090
Burago, D.; Grigoriev, D.; Slissenko, A.
2004
Complexity of gene circuits, Pfaffian functions and the morphogenesis problem. Zbl 1050.92003
Vakulenko, Sergey; Grigoriev, Dmitry
2003
Algebraic proof systems over formulas. Zbl 1044.68146
Grigoriev, Dima; Hirsch, Edward A.
2003
Complexity of Null- and Positivstellensatz proofs. Zbl 0992.03073
Grigoriev, Dima; Vorobjov, Nicolai
2002
Complexity of semialgebraic proofs. Zbl 1027.03044
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrij V.
2002
Complexity of semi-algebraic proofs. Zbl 1054.03035
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
2002
Public-key cryptography and invariant theory. Zbl 1081.94026
Grigoriev, D.
2002
Skyrmed monopoles. Zbl 0996.81059
Grigoriev, D. Yu.; Sutcliffe, P. M.; Tchrakian, D. H.
2002
Approximation and complexity. II: Iterated integration. Zbl 1020.68041
Grigoriev, Dima
2002
Exponential lower bound for static semi-algebraic proofs. Zbl 1056.03037
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
2002
On non-Abelian homomorphic public-key cryptosystems. Zbl 1081.94027
Grigoriev, D.; Ponomarenko, I.
2002
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Zbl 0974.68192
Grigoriev, D.
2001
Complexity of Positivstellensatz proofs for the knapsack. Zbl 0992.68077
Grigoriev, D.
2001
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1007.03052
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
2001
Approximation and complexity: Liouvillean-type theorems for linear differential equations on an interval. Zbl 1001.12007
Grigoriev, Dima
2001
There are no sparse NP$$_{w}$$-hard sets. Zbl 0992.68061
Cucker, Felipe; Grigoriev, Dima
2001
Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems. Zbl 1050.68048
Grigoriev, Dima
2001
Nikolai Aleksandrovich Shanin (on his 80th birthday). Zbl 1017.01517
Vsemirnov, M. A.; Girsh, È. A.; Grigor&rsquo;ev, D. Yu.; Davydov, G. V.; Dantsin, E. Ya.; Ivanov, A. A.; Konev, B. Yu.; Lifshits, V. A.; Matiyasevich, Yu. V.; Mints, G. E.; Orevkov, V. P.; Slisenko, A. O.
2001
Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Zbl 1040.68045
Grigoriev, D.; Razborov, A.
2000
Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. Zbl 1326.68354
Grigoriev, Dima; Vorobjov, Nicolai
2000
Topological complexity of the range searching. Zbl 0951.68024
Grigoriev, Dima
2000
Algorithms for computing sparse shifts for multivariate polynomials. Zbl 0968.68199
Grigoriev, Dima Yu.; Lakshman, Y. N.
2000
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1345.03105
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
1999
Complexity lower bounds for approximation algebraic computation trees. Zbl 0959.68143
Cucker, Felipe; Grigoriev, Dima
1999
Randomized complexity lower bound for arrangements and polyhedra. Zbl 0936.68047
Grigoriev, D.
1999
An exponential lower bound for depth 3 arithmetic circuits. Zbl 1028.68069
Grigoriev, Dima; Karpinski, Marek
1998
Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane. Zbl 0961.14039
Grigoriev, D.; Slissenko, A.
1998
An exponential lower bound on the size of algebraic decision trees for MAX. Zbl 0918.68032
Grigoriev, Dima; Karpinski, Marek; Yao, Andrew C.
1998
Randomized complexity lower bounds. Zbl 1027.68608
Grigoriev, D.
1998
On the power of real Turing machines over binary inputs. Zbl 0874.68110
Cucker, Felipe; Grigoriev, Dima
1997
Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Zbl 1044.68946
Grigoriev, D.
1997
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees. Zbl 0871.68176
Grigoriev, D.; Karpinski, M.; Vorobjov, N.
1997
Nearly sharp complexity bounds for multiprocessor algebraic computations. Zbl 0872.68053
Grigoriev, Dima
1997
A lower bound for randomized algebraic decision trees. Zbl 0895.68049
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman
1997
Randomization and the computational power of analytic and algebraic decision trees. Zbl 0895.68050
Grigoriev, Dima; Karpinski, Marek; Smolensky, Roman
1997
Complexity lower bounds for computation trees with elementary transcendental function gates. Zbl 0877.68086
Grigoriev, D.; Vorobjov, N.
1996
A lower bound for randomized algebraic decision trees. Zbl 0922.68090
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman
1996
Testing shift-equivalence of polynomials using quantum machines. Zbl 0928.68045
Grigoriev, D.
1996
NC solving of a system of linear ordinary differential equations in several unknowns. Zbl 0871.68096
Grigoriev, D.
1996
Algorithms for computing sparse shifts for multivariate polynomials. Zbl 0924.68105
Grigoriev, Dima Yu.; Lakshman, Y. N.
1995
On computing algebraic functions using logarithms and exponentials. Zbl 0834.68054
Grigoriev, Dima; Singer, Michael; Yao, Andrew
1995
Improved lower bound on testing membership to a polyhedron by algebraic decision trees. Zbl 0938.68868
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
1995
Computational complexity of sparse rational interpolation. Zbl 0802.68060
Grigoriev, Dima; Karpinski, Marek; Singer, Michael F.
1994
Lower bounds on testing membership to a polyhedron by algebraic decision trees. Zbl 1345.68158
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
1994
Deviation theorems for Pfaffian sigmoids. Zbl 0844.05090
Grigoriev, D. Yu.
1994
Deviation theorems for solutions of differential equations and applications to lower bounds on parallel complexity of sigmoids. Zbl 0844.05091
Grigoriev, D. Yu.
1994
A zero-test and an interpolation algorithm for the shifted sparse polynomials. Zbl 0809.68072
Grigoriev, Dima; Karpinski, Marek
1993
Computational complexity of sparse real algebraic function interpolation. Zbl 0801.68087
Grigoriev, D.; Karpinski, M.; Singer, M. F.
1993
Counting connected components of a semialgebraic set in subexponential time. Zbl 0900.68253
Grigor&rsquo;ev, D. Yu.; Vorobjov, N. N. jun.
1992
Finding connected components of a semialgebraic set in subexponential time. Zbl 0783.14036
Canny, J.; Grigor&rsquo;ev, D. Yu.; Vorob&rsquo;ev, N. N. jun.
1992
Existence of short proofs for nondivisibility of sparse polynomials under the Extended Riemann Hypothesis. Zbl 0963.68508
Grigoriev, Dima Yu.; Karpinski, Marek; Odlyzko, Andrew M.
1992
Solving ordinary differential equations in terms of series with real exponents. Zbl 0758.12004
Grigor&rsquo;ev, D. Yu.; Singer, M. F.
1991
...and 40 more Documents
all top 5

all top 5

#### Cited in 137 Serials

 56 Journal of Symbolic Computation 34 Theoretical Computer Science 19 Applicable Algebra in Engineering, Communication and Computing 17 Journal of Complexity 16 Computational Complexity 15 Discrete & Computational Geometry 14 SIAM Journal on Computing 14 Journal of Mathematical Sciences (New York) 12 Foundations of Computational Mathematics 11 Information Processing Letters 11 Journal of Computer and System Sciences 11 Advances in Applied Mathematics 10 Journal of Pure and Applied Algebra 10 Annals of Pure and Applied Logic 9 Mathematical Programming. Series A. Series B 9 Groups, Complexity, Cryptology 8 Journal of Algebra 8 Information and Computation 8 Mathematics in Computer Science 7 SIAM Journal on Optimization 6 Discrete Applied Mathematics 6 Theory of Computing Systems 5 Mathematical Notes 5 Annales de l’Institut Fourier 5 Algorithmica 5 Computational Geometry 5 Linear Algebra and its Applications 4 Mathematics of Computation 4 Advances in Mathematics 4 Journal of Soviet Mathematics 4 Programming and Computer Software 4 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI 4 Annals of Mathematics and Artificial Intelligence 3 Journal of Mathematical Physics 3 Linear and Multilinear Algebra 3 Bulletin of Mathematical Biology 3 Journal of Computational and Applied Mathematics 3 St. Petersburg Mathematical Journal 3 Journal of Systems Science and Complexity 3 Comptes Rendus. Mathématique. Académie des Sciences, Paris 3 Journal of Mathematical Cryptology 3 Prikladnaya Diskretnaya Matematika 2 Artificial Intelligence 2 Communications in Algebra 2 Applied Mathematics and Computation 2 Computing 2 Mathematische Zeitschrift 2 Results in Mathematics 2 Journal of Dynamics and Differential Equations 2 Cybernetics and Systems Analysis 2 Journal of Algebraic Combinatorics 2 Formal Methods in System Design 2 Russian Journal of Mathematical Physics 2 Journal of Combinatorial Optimization 2 Journal of the ACM 2 Lobachevskii Journal of Mathematics 2 SIAM Journal on Applied Dynamical Systems 2 Discrete and Continuous Dynamical Systems. Series S 1 Acta Informatica 1 Archive for History of Exact Sciences 1 Computers & Mathematics with Applications 1 Communications in Mathematical Physics 1 Journal of Computational Physics 1 Journal of Mathematical Analysis and Applications 1 Mathematical Methods in the Applied Sciences 1 Moscow University Mathematics Bulletin 1 Problems of Information Transmission 1 Russian Mathematical Surveys 1 Annali di Matematica Pura ed Applicata. Serie Quarta 1 Bulletin de la Société Mathématique de France 1 Kybernetika 1 Manuscripta Mathematica 1 Mathematische Annalen 1 Mathematics and Computers in Simulation 1 Mathematics of Operations Research 1 Memoirs of the American Mathematical Society 1 Michigan Mathematical Journal 1 Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods 1 Proceedings of the American Mathematical Society 1 Proceedings of the London Mathematical Society. Third Series 1 Rendiconti del Circolo Matemàtico di Palermo. Serie II 1 Transactions of the American Mathematical Society 1 Operations Research Letters 1 Combinatorica 1 Chinese Annals of Mathematics. Series B 1 Acta Applicandae Mathematicae 1 Computer Aided Geometric Design 1 Physica D 1 Applied Mathematics Letters 1 Journal of the American Mathematical Society 1 SIAM Journal on Discrete Mathematics 1 Multidimensional Systems and Signal Processing 1 Japan Journal of Industrial and Applied Mathematics 1 International Journal of Algebra and Computation 1 Differential Geometry and its Applications 1 International Journal of Foundations of Computer Science 1 Discrete Event Dynamic Systems 1 Geometric and Functional Analysis. GAFA 1 Computational Mathematics and Mathematical Physics 1 L’Enseignement Mathématique. 2e Série ...and 37 more Serials
all top 5

#### Cited in 54 Fields

 306 Computer science (68-XX) 110 Algebraic geometry (14-XX) 69 Field theory and polynomials (12-XX) 65 Mathematical logic and foundations (03-XX) 54 Numerical analysis (65-XX) 49 Operations research, mathematical programming (90-XX) 45 Commutative algebra (13-XX) 42 Ordinary differential equations (34-XX) 39 Information and communication theory, circuits (94-XX) 31 Linear and multilinear algebra; matrix theory (15-XX) 30 Number theory (11-XX) 28 Combinatorics (05-XX) 28 Biology and other natural sciences (92-XX) 21 Group theory and generalizations (20-XX) 18 Dynamical systems and ergodic theory (37-XX) 17 Associative rings and algebras (16-XX) 17 Partial differential equations (35-XX) 14 Convex and discrete geometry (52-XX) 10 Real functions (26-XX) 10 Several complex variables and analytic spaces (32-XX) 10 Quantum theory (81-XX) 8 Approximations and expansions (41-XX) 7 Differential geometry (53-XX) 7 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 6 Systems theory; control (93-XX) 5 Special functions (33-XX) 5 Algebraic topology (55-XX) 4 Operator theory (47-XX) 4 Probability theory and stochastic processes (60-XX) 3 General and overarching topics; collections (00-XX) 3 History and biography (01-XX) 3 Global analysis, analysis on manifolds (58-XX) 3 Classical thermodynamics, heat transfer (80-XX) 2 Order, lattices, ordered algebraic structures (06-XX) 2 General algebraic systems (08-XX) 2 Nonassociative rings and algebras (17-XX) 2 Category theory; homological algebra (18-XX) 2 Functions of a complex variable (30-XX) 2 Abstract harmonic analysis (43-XX) 2 Calculus of variations and optimal control; optimization (49-XX) 2 Geometry (51-XX) 2 Statistics (62-XX) 1 Potential theory (31-XX) 1 Difference and functional equations (39-XX) 1 Integral transforms, operational calculus (44-XX) 1 Functional analysis (46-XX) 1 General topology (54-XX) 1 Manifolds and cell complexes (57-XX) 1 Mechanics of deformable solids (74-XX) 1 Fluid mechanics (76-XX) 1 Optics, electromagnetic theory (78-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Relativity and gravitational theory (83-XX) 1 Mathematics education (97-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.