Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication. - Dima Grigoriev (MFCS, 1978)

Multiplicative Complexity of a Bilinear Form over a Commutative Ring. - Dima Grigoriev (MFCS, 1981)

Additive Complexity in Directed Computations. - Dima Grigoriev (Theor. Comput. Sci., 1982)

Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. - Alexander L. Chistov; Dima Grigoriev (MFCS, 1984)

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) - Dima Grigoriev; Marek Karpinski (FOCS, 1987)

Complexity of Deciding Tarski Algebra. - Dima Grigoriev (J. Symb. Comput., 1988)

Solving Systems of Polynomial Inequalities in Subexponential Time. - Dima Grigoriev; Nicolai N. Vorobjov Jr. (J. Symb. Comput., 1988)

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents - Dima Grigoriev; Marek Karpinski; Michael F. Singer (FOCS, 1990)

How to Test in Subexponential Time Whether Two Points Can Be Connected by a Curve in a Semialgebraic Set. - Dima Grigoriev (ISSAC, 1990)

Complexity of Irreducibility Testing for a System of Linear Ordinary Differential Equations. - Dima Grigoriev (ISSAC, 1990)

Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators. - Dima Grigoriev (J. Symb. Comput., 1990)

Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. - Dima Grigoriev; Marek Karpinski; Michael F. Singer (SIAM J. Comput., 1990)

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] - Dima Grigoriev; Marek Karpinski (FOCS, 1991)

Algorithms for Sparse Rational Interpolation. - Dima Grigoriev; Marek Karpinski (ISSAC, 1991)

Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. - Dima Grigoriev; Marek Karpinski; Andrew M. Odlyzko (ISSAC, 1992)

A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. - Dima Grigoriev; Marek Karpinski (AAECC, 1993)

Lower bounds on testing membership to a polyhedron by algebraic decision trees. - Dima Grigoriev; Marek Karpinski; Nicolai N. Vorobjov Jr. (STOC, 1994)

Computational Complexity of Sparse Rational Interpolation. - Dima Grigoriev; Marek Karpinski; Michael F. Singer (SIAM J. Comput., 1994)

Deviation Theorems for Solutions of Differential Equations and Applications to Lower Bounds on Parallel Complexity of Sigmoids. - Dima Grigoriev (Theor. Comput. Sci., 1994)

Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Nicolai N. Vorobjov Jr. (FOCS, 1995)

On Computing Algebraic Functions Using Logarithms and Exponentials. - Dima Grigoriev; Michael F. Singer; Andrew Chi-Chih Yao (SIAM J. Comput., 1995)

Testing Shift-Equivalence of Polynomials Using Quantum Machines. - Dima Grigoriev (ISSAC, 1996)

Randomized Omega(n2) Lower Bound for Knapsack - Dima Grigoriev; Marek Karpinski (Electron. Colloquium Comput. Complex., 1996)

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. - Dima Grigoriev; Marek Karpinski; Andrew M. Odlyzko (Fundam. Informaticae, 1996)

NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. - Dima Grigoriev (Theor. Comput. Sci., 1996)

Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. - Dima Grigoriev; Marek Karpinski (Theor. Comput. Sci., 1996)

Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. - Dima Grigoriev; Nicolai N. Vorobjov Jr. (Theor. Comput. Sci., 1996)

Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. - Dima Grigoriev; Anatol Slissenko (AAECC, 1997)

A Lower Bound for Randomized Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Friedhelm Meyer auf der Heide; Roman Smolensky (Comput. Complex., 1997)

Randomization and the Computational Power of Analytic and Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Roman Smolensky (Comput. Complex., 1997)

Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. - Dima Grigoriev; Marek Karpinski; Nicolai N. Vorobjov Jr. (Discret. Comput. Geom., 1997)

Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations. - Dima Grigoriev (J. Complex., 1997)

On the Power of Real Turing Machines Over Binary Inputs. - Felipe Cucker; Dima Grigoriev (SIAM J. Comput., 1997)

Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. - Dima Grigoriev (Theor. Comput. Sci., 1997)

Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. - Dima Grigoriev (FOCS, 1998)

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. - Dima Grigoriev; Alexander A. Razborov (FOCS, 1998)

Polytime Algorithm for the Shortest Path in a Homotopy Class Amidst Semi-Algebraic Obstacles in the Plane. - Dima Grigoriev; Anatol Slissenko (ISSAC, 1998)

Randomized Complexity Lower Bounds. - Dima Grigoriev (STOC, 1998)

An Exponential Lower Bound for Depth 3 Arithmetic Circuits. - Dima Grigoriev; Marek Karpinski (STOC, 1998)

An exponential lower bound on the size of algebraic decision trees for Max. - Dima Grigoriev; Marek Karpinski; Andrew Chi-Chih Yao (Comput. Complex., 1998)

Computing the Additive Complexity of Algebraic Circuits with Root Extracting. - Dima Grigoriev; Marek Karpinski (SIAM J. Comput., 1998)

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). - Samuel R. Buss; Dima Grigoriev; Russell Impagliazzo; Toniann Pitassi (CCC, 1999)

Complexity lower bounds for randomized computation trees over zero characteristic fields. - Dima Grigoriev (Comput. Complex., 1999)

Randomized Complexity Lower Bound for Arrangements and Polyhedra. - Dima Grigoriev (Discret. Comput. Geom., 1999)

Complexity Lower Bounds for Approximation Algebraic Computation Trees. - Felipe Cucker; Dima Grigoriev (J. Complex., 1999)

Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. - Dima Grigoriev; Nicolai N. Vorobjov Jr. (ISSAC, 2000)

Algorithms for Computing Sparse Shifts for Multivariate Polynomials. - Dima Grigoriev; Yagati N. Lakshman (Appl. Algebra Eng. Commun. Comput., 2000)

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. - Dima Grigoriev; Alexander A. Razborov (Appl. Algebra Eng. Commun. Comput., 2000)

Topological Complexity of the Range Searching. - Dima Grigoriev (J. Complex., 2000)

Complexity of Null-and Positivstellensatz proofs. - Dima Grigoriev; Nicolai N. Vorobjov Jr. (Ann. Pure Appl. Log., 2001)

Complexity of Positivstellensatz proofs for the knapsack. - Dima Grigoriev (Comput. Complex., 2001)

Complexity of semi-algebraic proofs - Dima Grigoriev; Edward A. Hirsch; Dmitrii V. Pasechnik (Electron. Colloquium Comput. Complex., 2001)

Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval. - Dima Grigoriev (Found. Comput. Math., 2001)

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. - Samuel R. Buss; Dima Grigoriev; Russell Impagliazzo; Toniann Pitassi (J. Comput. Syst. Sci., 2001)

There are No Sparse NPw-Hard Sets. - Felipe Cucker; Dima Grigoriev (SIAM J. Comput., 2001)

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. - Dima Grigoriev (Theor. Comput. Sci., 2001)

Exponential Lower Bound for Static Semi-algebraic Proofs. - Dima Grigoriev; Edward A. Hirsch; Dmitrii V. Pasechnik (ICALP, 2002)

On non-abelian homomorphic public-key cryptosystems - Dima Grigoriev; Ilia N. Ponomarenko (CoRR, 2002)

Public-key cryptography and invariant theory - Dima Grigoriev (Electron. Colloquium Comput. Complex., 2002)

Approximation and Complexity II: Iterated Integration. - Dima Grigoriev (Found. Comput. Math., 2002)

Homomorphic public-key cryptosystems over groups and rings - Dima Grigoriev; Ilia N. Ponomarenko (CoRR, 2003)

Algebraic proof systems over formulas. - Dima Grigoriev; Edward A. Hirsch (Theor. Comput. Sci., 2003)

Factoring and Solving Linear Partial Differential Equations. - Dima Grigoriev; Fritz Schwarz (Computing, 2004)

Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. - Dima Burago; Dima Grigoriev; Anatol Slissenko (Theor. Comput. Sci., 2004)

Generalized Loewy-decomposition of d-modules. - Dima Grigoriev; Fritz Schwarz (ISSAC, 2005)

Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. - Dima Grigoriev; Dmitrii V. Pasechnik (Comput. Complex., 2005)

Time hierarchies for cryptographic function inversion with advice - Dima Grigoriev; Edward A. Hirsch; Konstantin Pervyshev (Electron. Colloquium Comput. Complex., 2005)

Weak Bézout inequality for D-modules. - Dima Grigoriev (J. Complex., 2005)

Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits. - Dima Grigoriev; Ilia N. Ponomarenko (Appl. Algebra Eng. Commun. Comput., 2006)

Algorithms and complexity in biological pattern formation problems. - Dima Grigoriev; Sergei Vakulenko (Ann. Pure Appl. Log., 2006)

Loewy and primary decompositions of D-modules. - Dima Grigoriev; Fritz Schwarz (Adv. Appl. Math., 2007)

Loewy decomposition of third-order linear aPDE's in the plane. - Dima Grigoriev; Fritz Schwarz (ISSAC, 2008)

Probabilistic Communication Complexity Over The Reals. - Dima Grigoriev (Comput. Complex., 2008)

Zero-knowledge authentication schemes from actions on graphs, groups, or rings - Dima Grigoriev; Vladimir Shpilrain (CoRR, 2008)

Foreword. - Sergei N. Artëmov; Volker Diekert; Dima Grigoriev (Theory Comput. Syst., 2008)

A Complete Public-Key Cryptosystem. - Dima Grigoriev; Edward A. Hirsch; Konstantin Pervyshev (Groups Complex. Cryptol., 2009)

Authentication from Matrix Conjugation. - Dima Grigoriev; Vladimir Shpilrain (Groups Complex. Cryptol., 2009)

Absolute factoring of non-holonomic ideals in the plane. - Dima Grigoriev; Fritz Schwarz (ISSAC, 2010)

Authentication schemes from actions on graphs, groups, or rings. - Dima Grigoriev; Vladimir Shpilrain (Ann. Pure Appl. Log., 2010)

A low complexity probabilistic test for integer multiplication. - Dima Grigoriev; Gerald Tenenbaum (J. Complex., 2010)

Preface. - Sergei N. Artëmov; Volker Diekert; Dima Grigoriev (Theory Comput. Syst., 2010)

Tropical Geometries and Dynamics of Biochemical Networks Application to Hybrid Cell Cycle Models. - Vincent Noel; Dima Grigoriev; Sergei Vakulenko; Ovidiu Radulescu (SASB, 2011)

Complexity of Solving Systems with Few Independent Monomials and Applications to Mass-Action Kinetics. - Dima Grigoriev; Andreas Weber 004 (CASC, 2012)

On a tropical dual Nullstellensatz. - Dima Grigoriev (Adv. Appl. Math., 2012)

Hybrid models of the cell cycle molecular machinery - Vincent Noel; Dima Grigoriev; Sergei Vakulenko; Ovidiu Radulescu (HSB, 2012)

Continuous hard-to-invert functions and biometric authentication. - Dima Grigoriev; Sergey I. Nikolenko (Groups Complex. Cryptol., 2012)

No-leak authentication by the Sherlock Holmes method. - Dima Grigoriev; Vladimir Shpilrain (Groups Complex. Cryptol., 2012)

Efficient Methods to Compute Hopf Bifurcations in Chemical Reaction Networks Using Reaction Coordinates. - Hassan Errami; Markus Eiswirth; Dima Grigoriev; Werner M. Seiler; Thomas Sturm 001; Andreas Weber 004 (CASC, 2013)

Polynomial Complexity of Solving Systems of Few Algebraic Equations with Small Degrees. - Dima Grigoriev (CASC, 2013)

Complexity in Tropical Algebra (Invited Talk). - Dima Grigoriev (CASC, 2013)

Computing Divisors and Common Multiples of Quasi-linear Ordinary Differential Equations. - Dima Grigoriev; Fritz Schwarz (CASC, 2013)

Complexity of Solving Tropical Linear Systems. - Dima Grigoriev (Comput. Complex., 2013)

Subtraction-free complexity and cluster transformations. - Sergey Fomin; Dima Grigoriev; Gleb A. Koshevoy (CoRR, 2013)

Secrecy without one-way functions. - Dima Grigoriev; Vladimir Shpilrain (Groups Complex. Cryptol., 2013)

Tropical cryptography. - Dima Grigoriev; Vladimir Shpilrain (IACR Cryptol. ePrint Arch., 2013)

Secure information transmission based on physical principles. - Dima Grigoriev; Vladimir Shpilrain (IACR Cryptol. ePrint Arch., 2013)

Punctuated evolution and robustness in morphogenesis. - Dima Grigoriev; John Reinitz; Sergei Vakulenko; Andreas Weber 004 (Biosyst., 2014)

Tensor Rank: Matching Polynomials and Schur Rings. - Dima Grigoriev; Mikhail E. Muzychuk; Ilia N. Ponomarenko (Found. Comput. Math., 2014)

Yao's Millionaires' Problem and Decoy-Based Public Key Encryption by Classical Physics. - Dima Grigoriev; Vladimir Shpilrain (Int. J. Found. Comput. Sci., 2014)

Polynomial Complexity Recognizing a Tropical Linear Variety. - Dima Grigoriev (CASC, 2015)

Computing Highest-Order Divisors for a Class of Quasi-Linear Partial Differential Equations. - Dima Grigoriev; Fritz Schwarz (CASC, 2015)

Analysis of Reaction Network Systems Using Tropical Geometry. - Satya Swarup Samal; Dima Grigoriev; Holger Fröhlich; Ovidiu Radulescu (CASC, 2015)

Symbolic Dynamics of Biochemical Pathways as Finite States Machines. - Ovidiu Radulescu; Satya Swarup Samal; Aurélien Naldi; Dima Grigoriev; Andreas Weber 004 (CMSB, 2015)

Tropical Effective Primary and Dual Nullstellens"atze. - Dima Grigoriev; Vladimir V. Podolskii (STACS, 2015)

Complexity of Tropical and Min-plus Linear Prevarieties. - Dima Grigoriev; Vladimir V. Podolskii (Comput. Complex., 2015)

Detection of Hopf bifurcations in chemical reaction networks using convex coordinates. - Hassan Errami; Markus Eiswirth; Dima Grigoriev; Werner M. Seiler; Thomas Sturm 001; Andreas Weber 004 (J. Comput. Phys., 2015)

Geometric analysis of pathways dynamics: Application to versatility of TGF-β receptors. - Satya Swarup Samal; Aurélien Naldi; Dima Grigoriev; Andreas Weber 004; Nathalie Théret; Ovidiu Radulescu (Biosyst., 2016)

Algorithms and Effectivity in Tropical Mathematics and Beyond (Dagstuhl Seminar 16482). - Stéphane Gaubert; Dima Grigoriev; Michael Joswig; Thorsten Theobald (Dagstuhl Reports, 2016)

Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees. - Sergey Fomin; Dima Grigoriev; Gleb A. Koshevoy (Found. Comput. Math., 2016)

Complexity of tropical Schur polynomials. - Dima Grigoriev; Gleb A. Koshevoy (J. Symb. Comput., 2016)

Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks. - Matthew England 001; Hassan Errami; Dima Grigoriev; Ovidiu Radulescu; Thomas Sturm 001; Andreas Weber 004 (CASC, 2017)

Tropical Combinatorial Nullstellensatz and Fewnomials Testing. - Dima Grigoriev; Vladimir V. Podolskii (FCT, 2017)

A Case Study on the Parametric Occurrence of Multiple Steady States. - Russell J. Bradford; James H. Davenport; Matthew England 001; Hassan Errami; Vladimir P. Gerdt; Dima Grigoriev; Charles Tapley Hoyt; Marek Kosta; Ovidiu Radulescu; Thomas Sturm 001; Andreas Weber 004 (ISSAC, 2017)

Tropical differential equations. - Dima Grigoriev (Adv. Appl. Math., 2017)

Bounds on the Number of Connected Components for Tropical Prevarieties. - Alex Davydow; Dima Grigoriev (Discret. Comput. Geom., 2017)

Secure Multiparty Computation without One-way Functions. - Dima Grigoriev; Vladimir Shpilrain (FLAP, 2017)

Probabilistic solution of Yao's millionaires' problem. - Mariya Bessonov; Dima Grigoriev; Vladimir Shpilrain (IACR Cryptol. ePrint Arch., 2017)

Yao's Millionaires' Problem and Public-Key Encryption Without Computational Assumptions. - Dima Grigoriev; Laszlo B. Kish; Vladimir Shpilrain (Int. J. Found. Comput. Sci., 2017)

Tropical Newton-Puiseux Polynomials. - Dima Grigoriev (CASC, 2018)

Orthogonal Tropical Linear Prevarieties. - Dima Grigoriev; Nicolai N. Vorobjov Jr. (CASC, 2018)

A Framework for Unconditionally Secure Public-Key Encryption (with Possible Decryption Errors). - Mariya Bessonov; Dima Grigoriev; Vladimir Shpilrain (ICMS, 2018)

On semiring complexity of Schur polynomials. - Sergey Fomin; Dima Grigoriev; Dorian Nogneng; Éric Schost (Comput. Complex., 2018)

Tropical Effective Primary and Dual Nullstellensätze. - Dima Grigoriev; Vladimir V. Podolskii (Discret. Comput. Geom., 2018)

Tropical cryptography II: extensions by homomorphisms. - Dima Grigoriev; Vladimir Shpilrain (IACR Cryptol. ePrint Arch., 2018)

Semi-Algebraic Proofs, IPS Lower Bounds and the $ tau$-Conjecture: Can a Natural Number be Negative? - Yaroslav Alekseev; Dima Grigoriev; Edward A. Hirsch; Iddo Tzameret (Electron. Colloquium Comput. Complex., 2019)

Key agreement based on automaton groups. - Rostislav I. Grigorchuk; Dima Grigoriev (Groups Complex. Cryptol., 2019)

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? - Yaroslav Alekseev; Dima Grigoriev; Edward A. Hirsch; Iddo Tzameret (STOC, 2020)

Tropical recurrent sequences. - Dima Grigoriev (Adv. Appl. Math., 2020)

Tropical Combinatorial Nullstellensatz and Sparse Polynomials. - Dima Grigoriev; Vladimir V. Podolskii (Found. Comput. Math., 2020)

Identifying the parametric occurrence of multiple steady states for some biological networks. - Russell J. Bradford; James H. Davenport; Matthew England 001; Hassan Errami; Vladimir P. Gerdt; Dima Grigoriev; Charles Tapley Hoyt; Marek Kosta; Ovidiu Radulescu; Thomas Sturm 001; Andreas Weber 004 (J. Symb. Comput., 2020)

Decomposing tropical rational functions. - Dima Grigoriev (J. Symb. Comput., 2020)

Complexity of deciding whether a tropical linear prevariety is a tropical variety. - Dima Grigoriev; Nicolai N. Vorobjov Jr. (Appl. Algebra Eng. Commun. Comput., 2021)

Probability theory and public-key cryptography. - Mariya Bessonov; Dima Grigoriev; Vladimir Shpilrain (Int. J. Comput. Math. Comput. Syst. Theory, 2021)

RSA and redactable blockchains. - Dima Grigoriev; Vladimir Shpilrain (Int. J. Comput. Math. Comput. Syst. Theory, 2021)

Efficiently and Effectively Recognizing Toricity of Steady State Varieties. - Dima Grigoriev; Alexandru Iosif; Hamid Rahkooy; Thomas Sturm 001; Andreas Weber 004 (Math. Comput. Sci., 2021)

Entropy of tropical holonomic sequences. - Dima Grigoriev (J. Symb. Comput., 2022)

On a tropical version of the Jacobian conjecture. - Dima Grigoriev; Danylo V. Radchenko (J. Symb. Comput., 2022)

Excitable media store and transfer complicated information via topological defect motion. - Ivan Sudakow; Sergey Vakulenko; Dima Grigoriev (Commun. Nonlinear Sci. Numer. Simul., 2023)

BASS: Boolean Automorphisms Signature Scheme. - Dima Grigoriev; Ilia Ilmer; Alexey Ovchinnikov; Vladimir Shpilrain (IACR Cryptol. ePrint Arch., 2023)

Tropical Newton-Puiseux polynomials II. - Dima Grigoriev (J. Symb. Comput., 2023)

Tropical proof systems. - Yaroslav Alekseev; Dima Grigoriev; Edward A. Hirsch (Electron. Colloquium Comput. Complex., 2024)

Digital signature schemes using non-square matrices or scrap automorphisms. - Jiale Chen; Dima Grigoriev; Vladimir Shpilrain (Int. J. Comput. Math. Comput. Syst. Theory, 2024)

Semialgebraic Proofs, IPS Lower Bounds, and the ( boldsymbol{ tau} )-Conjecture: Can a Natural Number be Negative? - Yaroslav Alekseev; Dima Grigoriev; Edward A. Hirsch; Iddo Tzameret (SIAM J. Comput., 2024)

The entropy of the radical ideal of a tropical curve. - Dima Grigoriev (Adv. Appl. Math., 2024)

Tropical cryptography III: Digital signatures. - Jiale Chen; Dima Grigoriev; Vladimir Shpilrain (J. Math. Cryptol., 2024)

Tropical Proof Systems: Between R(CP) and Resolution. - Yaroslav Alekseev; Dima Grigoriev; Edward A. Hirsch (STACS, 2025)

Testing containment of tropical hypersurfaces within polynomial complexity. - Dima Grigoriev (J. Symb. Comput., 2026)