Dima Grigoriev
#40,284
Most Influential Person Now
Russian mathematician
Dima Grigoriev's AcademicInfluence.com Rankings
Dima Grigorievmathematics Degrees
Mathematics
#2548
World Rank
#3911
Historical Rank
Algebra
#106
World Rank
#172
Historical Rank
Geometry
#118
World Rank
#183
Historical Rank
Measure Theory
#2762
World Rank
#3298
Historical Rank
Download Badge
Mathematics
Why Is Dima Grigoriev Influential?
(Suggest an Edit or Addition)According to Wikipedia, Dima Grigoriev is a mathematician. His research interests include algebraic geometry, symbolic computation and computational complexity theory in computer algebra, with over 130 published articles.
Dima Grigoriev's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Solving Systems of Polynomial Inequalities in Subexponential Time (1988) (370)
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity (2001) (209)
- Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields (1984) (160)
- Complexity of Deciding Tarski Algebra (1988) (152)
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields (1988) (136)
- The matching problem for bipartite graphs with polynomially bounded permanents is in NC (1987) (134)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes (1999) (117)
- Complexity of Positivstellensatz proofs for the knapsack (2002) (111)
- An exponential lower bound for depth 3 arithmetic circuits (1998) (110)
- Complexity of Null-and Positivstellensatz proofs (2001) (85)
- Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane (1998) (67)
- Complexity of Semi-algebraic Proofs (2002) (67)
- Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields (2000) (67)
- Polynomial-time computing over quadratic maps i: sampling in real algebraic sets (2004) (64)
- Factoring and Solving Linear Partial Differential Equations (2004) (57)
- Detection of Hopf bifurcations in chemical reaction networks using convex coordinates (2015) (51)
- Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators (1990) (46)
- On the Power of Real Turing Machines Over Binary Inputs (1997) (42)
- Homomorphic public-key cryptosystems over groups and rings (2003) (41)
- Tropical Geometries and Dynamics of Biochemical Networks Application to Hybrid Cell Cycle Models (2011) (41)
- A lower bound for randomized algebraic decision trees (1996) (40)
- Computational Complexity of Sparse Rational Interpolation (1994) (40)
- Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields (1998) (37)
- Tropical Cryptography (2013) (37)
- Tseitin's tautologies and lower bounds for Nullstellensatz proofs (1998) (34)
- A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals (1993) (33)
- Complexity of Solving Tropical Linear Systems (2013) (33)
- Algebraic proof systems over formulas (2003) (33)
- Authentication from Matrix Conjugation (2010) (32)
- A Case Study on the Parametric Occurrence of Multiple Steady States (2017) (32)
- Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines (1997) (31)
- Generalized Loewy-decomposition of d-modules (2005) (30)
- Algorithms for Computing Sparse Shifts for Multivariate Polynomials (1995) (30)
- Model reduction of biochemical reactions networks by tropical analysis methods (2015) (30)
- Complexity of Tropical and Min-plus Linear Prevarieties (2012) (29)
- Tropicalization and tropical equilibration of chemical reactions (2012) (29)
- The Interpolation Problem for k-sparse Sums of Eigenfunctions of Operators (1991) (28)
- Nash resolution for binomial varieties as Euclidean division. A priori termination bound, polynomial complexity in essential dimension 2 (2012) (27)
- Interpolation of sparse rational functions without knowing bounds on exponents (1990) (24)
- Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks (2019) (23)
- Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks (2017) (22)
- Complexity of irreducibility testing for a system of linear ordinary differential equations (1990) (22)
- Effective Hironaka resolution and its complexity (2011) (21)
- Tropical cryptography II: Extensions by homomorphisms (2018) (20)
- Weak Bézout inequality for D-modules (2003) (19)
- Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees (2013) (19)
- An approximation algorithm for the number of zeros or arbitrary polynomials over GF(q) (1991) (19)
- Tropical Effective Primary and Dual Nullstellensätze (2014) (19)
- Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits (2003) (19)
- Bounds on numers of vectors of multiplicities for polynomials which are easy to compute (2000) (19)
- Optimal Jet Finder (2003) (18)
- Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication (1978) (17)
- Complexity of Solving Systems with Few Independent Monomials and Applications to Mass-Action Kinetics (2012) (17)
- Authentication schemes from actions on graphs, groups, or rings (2008) (17)
- A Geometric Method for Model Reduction of Biochemical Networks with Polynomial Rate Functions (2015) (17)
- Improved lower bound on testing membership to a polyhedron by algebraic decision trees (1995) (16)
- Towards a standard jet definition. (2003) (16)
- Algorithms for sparse rational interpolation (1991) (16)
- Exponential Lower Bound for Static Semi-algebraic Proofs (2002) (16)
- Complexity lower bounds for computation trees with elementary transcendental function gates (1994) (16)
- A Complete Public-Key Cryptosystem (2006) (16)
- Randomized complexity lower bounds (1998) (15)
- Testing shift-equivalence of polynomials using quantum machines (1996) (14)
- Tropical differential equations (2015) (14)
- Loewy decomposition of third-order linear aPDE's in the plane (2008) (14)
- Loewy and primary decompositions of D-modules (2007) (13)
- Yao's Millionaires' Problem and Decoy-Based Public Key Encryption by Classical Physics (2013) (13)
- An exponential lower bound on the size of algebraic decision trees for Max (1998) (13)
- Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees (1993) (12)
- Symbolic Dynamics of Biochemical Pathways as Finite States Machines (2015) (12)
- Computational Complexity of Sparse Real Algebraic Function Interpolation (1992) (12)
- Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis (1992) (11)
- Topological Complexity of the Range Searching (2000) (11)
- RSA and redactable blockchains (2020) (11)
- Efficient Methods to Compute Hopf Bifurcations in Chemical Reaction Networks Using Reaction Coordinates (2013) (11)
- Geometric analysis of pathways dynamics: Application to versatility of TGF-β receptors (2015) (11)
- On non-Abelian homomorphic public-key cryptosystems (2002) (11)
- Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane (1997) (10)
- Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? (2019) (10)
- Lower bound on testing membership to a polyhedron by algebraic decision and computation trees (1997) (10)
- Analysis of Reaction Network Systems Using Tropical Geometry (2015) (10)
- Absolute factoring of non-holonomic ideals in the plane (2010) (10)
- Lower bounds on testing membership to a polyhedron by algebraic decision trees (1994) (9)
- Randomized Ω(n2) lower bound for knapsack (1997) (9)
- Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon (2004) (9)
- Efficiently and Effectively Recognizing Toricity of Steady State Varieties (2019) (8)
- Multiplicative Complexity of a Bilinear Form over a Commutative Ring (1981) (8)
- Hybrid models of the cell cycle molecular machinery (2012) (8)
- On a tropical dual Nullstellensatz (2011) (8)
- Yao's Millionaires' Problem and Public-Key Encryption Without Computational Assumptions (2017) (8)
- Complexity Lower Bounds for Approximation Algebraic Computation Trees (1999) (8)
- Bounds on the Number of Connected Components for Tropical Prevarieties (2015) (8)
- Lower Bound for Randomized Linear Decision Trees Recognising a Union of Hyperplanes in a Generic Position (1994) (8)
- Public-key cryptography and invariant theory (2002) (7)
- Time hierarchies for cryptographic function inversion with advice (2009) (7)
- Algorithms to Study Large Metabolic Network Dynamics (2015) (6)
- On Computing Algebraic Functions Using Logarithms and Exponentials (1995) (6)
- Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations (1997) (6)
- Complexity of tropical Schur polynomials (2016) (6)
- Testing the shift-equivalence of polynomials using quantum machines (1996) (5)
- Algorithms and complexity in biological pattern formation problems (2006) (5)
- Evolution in random environment and structural instability (2006) (5)
- Analogue of Newton-Puiseux series for non-holonomic D-modules and factoring (2008) (5)
- Tropical Newton-Puiseux Polynomials (2017) (5)
- Secrecy without one-way functions (2013) (5)
- Deviation Theorems for Pfaffian Sigmoids (1994) (5)
- Secure Information Transmission Based on Physical Principles (2013) (5)
- A Simple 3-Parameter Model for Cancer Incidences (2018) (5)
- Complexity lower bounds for randomized computation trees over zero characteristic fields (1999) (5)
- Complexity of a standard basis of a D-module (2009) (5)
- Tropical recurrent sequences (2018) (4)
- Randomization and the computational power of analytic and algebraic decision trees (1996) (4)
- Punctuated evolution and robustness in morphogenesis (2014) (4)
- NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns (1996) (4)
- Effective Hironaka resolution and its Complexity (with appendix on applications in positive characteristic) (2012) (4)
- Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann (1996) (4)
- Polynomial Complexity Recognizing a Tropical Linear Variety (2015) (4)
- Randomized Complexity Lower Bound for Arrangements and Polyhedra (1999) (4)
- Computability of the Additive Complexity of Algebraic Circuits with Root Extracting (1996) (4)
- An efficient implementation of the optimal jet definition (1999) (4)
- A low complexity probabilistic test for integer multiplication (2010) (3)
- Loewy Decomposition of Linear Third-Order PDE ’ s in the Plane (2008) (3)
- There are No Sparse NPw-Hard Sets (2001) (3)
- Upper Bounds on Betti Numbers of Tropical Prevarieties (2017) (3)
- On semiring complexity of Schur polynomials (2016) (3)
- Probabilistic Communication Complexity Over The Reals (2007) (3)
- Algebraic cryptography: New constructions and their security against provable break (2009) (3)
- DEVIATION THEOREMS FOR SOLUTIONS OF LINEAR ORDINARY DIFFERENTIAL EQUATIONS AND APPLICATIONS TO PARALLEL COMPLEXITY OF SIGMOIDS (2007) (3)
- On a tropical version of the Jacobian conjecture (2019) (3)
- Tropical Combinatorial Nullstellensatz and Fewnomials Testing (2017) (3)
- Additive Complexity in Directed Computations (1982) (3)
- Orthogonal Tropical Linear Prevarieties (2018) (3)
- A Framework for Unconditionally Secure Public-Key Encryption (with Possible Decryption Errors) (2018) (3)
- A Tropical Method based on Newton Polygon Approach for Algebraic Analysis of Biochemical Reaction Networks (2014) (3)
- No-leak authentication by the Sherlock Holmes method (2012) (3)
- Non-holonomic Ideals in the Plane and Absolute Factoring (2008) (2)
- Key agreement based on automaton groups (2019) (2)
- Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval (2001) (2)
- Complexity of Janet basis of a D-module (2007) (2)
- Invariant-based Cryptosystems and Their Security Against Provable Worst-Case Break (2007) (2)
- Lower Bounds for the Number of Zeros of Multivariate Polynomials over GF[$q$] (1991) (2)
- Tensor Rank: Matching Polynomials and Schur Rings (2014) (2)
- Approximation and Complexity II: Iterated Integration (2002) (2)
- Subtraction-free complexity and cluster transformations (2013) (2)
- Deviation Theorems for Solutions of Differential Equations and Applications to Lower Bounds on Parallel Complexity of Sigmoids (1994) (1)
- Computing the Additive Complexity of Algebraic Circuits with Root Extracting (1998) (1)
- Instability, complexity, and evolution (2009) (1)
- Computing Divisors and Common Multiples of Quasi-linear Ordinary Differential Equations (2013) (1)
- Construction of universal Thom-Whitney-a stratifications, their functoriality and Sard-type Theorem for singular varieties (2008) (1)
- Complexity of Tropical and Min-plus Linear Prevarieties (2013) (1)
- Optical device accelerating dynamic programming (2007) (1)
- Tropical Effective Primary and Dual Nullstellensätze (2018) (1)
- Complexity of deciding whether a tropical linear prevariety is a tropical variety (2018) (1)
- Cryptography without one-way functions (2011) (1)
- A tropical version of Hilbert polynomial (in dimension one) (2021) (1)
- Entropy of tropical holonomic sequences (2020) (1)
- Tropical Combinatorial Nullstellensatz and Sparse Polynomials (2017) (1)
- A Geometric Method for Model Reduction of Biochemical Networks with Polynomial Rate Functions (2015) (1)
- Non-holonomic overideals of differential ideals in two variables and absolute factoring (2008) (1)
- Continuous hard-to-invert functions and biometric authentication (2012) (1)
- Quantum optical device accelerating dynamic programming (2005) (0)
- Complexity in Tropical Algebra (Invited Talk) (2013) (0)
- A N EFFICIENT IMPLEMENTATION OF THE OPTIMAL JET DEFINITION Contribution to the XIII Int. Workshop on Quantum Field Theory and High Energy Physics (1999) (0)
- Complexity and stable evolution of circuits (2010) (0)
- A G ] 2 5 A pr 2 01 9 Tropical Combinatorial Nullstellensatz and Sparse Polynomials ∗ (2019) (0)
- Instability, Evolution and Morphogenesis (2013) (0)
- A Monte Carlo Test of the Optimal Jet Definition (2003) (0)
- Apriori termination bound , polynomial complexity in dim 2 (0)
- Probability theory and public-key cryptography (2020) (0)
- Complexity of deciding whether a tropical linear prevariety is a tropical variety (2019) (0)
- Tensor Rank: Matching Polynomials and Schur Rings (2014) (0)
- Randomized Omega(n2) Lower Bound for Knapsack (1996) (0)
- Decomposing tropical rational functions (2019) (0)
- A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem (1995) (0)
- Quadratic Randomized Lower Boundfor the Knapsack Problem (2007) (0)
- Proceedings of the First international computer science conference on Theory and Applications (2006) (0)
- On semiring complexity of Schur polynomials (2018) (0)
- Tropicalization of systems biology models (2012) (0)
- A Deterministic Algorithm for Rational Function Interpolations (1988) (0)
- Entropy of radical ideal of a tropical prevariety. (2020) (0)
- Time hierarchies for cryptographic function inversion with nonuniform advice (2009) (0)
- Probabilistic solution of Yao's millionaires' problem (2017) (0)
- Iterated pushdown automata and sequences of rational numbers (2006) (0)
- How to test in subexponential time whether two points can be connected by a curve in a semialgebraic set (1990) (0)
- Complexity of Solving Tropical Linear Systems (2013) (0)
- Upper Bounds on Betti Numbers of Tropical Prevarieties (2018) (0)
- Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees (2014) (0)
- 1 5 O ct 2 00 7 Probabilistic communication complexity over the reals (2007) (0)
- Doubly-Exponential Growth of the Number of Vectors of Multipilicities for Solutions of Systems of Polynomial (2003) (0)
- Workshop Dynamical Systems and Applications in the Framework of the Project Fp7-people-2012-irses-316338 within the 7th European Community Framework Programme (2013) (0)
- Polynomial Complexity of Solving Systems of Few Algebraic Equations with Small Degrees (2013) (0)
- Universal stratifications and a Bertini-type theorem (2012) (0)
- Computer Science -- Theory and Applications: First International Symposium on Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, ... (Lecture Notes in Computer Science) (2006) (0)
- BIT COMMITMENT , OBLIVIOUS TRANSFER , AND MENTAL POKER WITHOUT ONE-WAY FUNCTIONS (2011) (0)
- MULTIPARTY COMPUTATION AND SECRET SHARING (2011) (0)
- Bounds on the Number of Connected Components for Tropical Prevarieties (2016) (0)
- A G ] 4 J un 2 01 5 Tropical Effective Primary and Dual Nullstellensätze ∗ (2018) (0)
- Computing Highest-Order Divisors for a Class of Quasi-Linear Partial Differential Equations (2015) (0)
- Key-agreement based on automaton groups Rostislav Grigorchuk (2019) (0)
- Entropy of radical ideal of a tropical curve (2020) (0)
- Computer science -- theory and applications : First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006 : proceedings (2006) (0)
- Algorithms and Effectivity in Tropical Mathematics and Beyond (Dagstuhl Seminar 16482) (2016) (0)
- ALGORITHMIC ASPECTS OF GENETIC SEQUENCES AND RELATIVE KOLMOGOROV COMPLEXITY (2013) (0)
- Excitablemedia store and transfer complicated information via topological defectmotion (2023) (0)
- Tropical Newton-Puiseux polynomials II (2021) (0)
- A Simple 3-Parameter Model for Cancer Incidences (2018) (0)
- Secure Multiparty Computation without One-way Functions (2017) (0)
- A C ] 2 A ug 2 01 1 On a tropical dual Nullstellensatz (2012) (0)
This paper list is powered by the following services:
Other Resources About Dima Grigoriev
What Schools Are Affiliated With Dima Grigoriev?
Dima Grigoriev is affiliated with the following schools:
