Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Dima Grigoriev
2010 – today
- 2013
[j52]Dima Grigoriev: Complexity of Solving Tropical Linear Systems. Computational Complexity 22(1): 71-88 (2013)- [j51]Dima Grigoriev, Vladimir Shpilrain: Secrecy without one-way functions. Groups Complexity Cryptology 5(1): 31-52 (2013)
- [c36]Dima Grigoriev, Vladimir Shpilrain: Secure Information Transmission Based on Physical Principles. UCNC 2013: 113-124
- [i25]
- [i24]
- [i23]Dima Grigoriev, Vladimir Shpilrain: Tropical cryptography. IACR Cryptology ePrint Archive 2013: 12 (2013)
- [i22]Dima Grigoriev, Vladimir Shpilrain: Secrecy without one-way functions. IACR Cryptology ePrint Archive 2013: 55 (2013)
- [i21]Dima Grigoriev, Vladimir Shpilrain: Secure information transmission based on physical principles. IACR Cryptology ePrint Archive 2013: 261 (2013)
- 2012
- [j50]Vincent Noel, Dima Grigoriev, Sergei Vakulenko, Ovidiu Radulescu: Tropical Geometries and Dynamics of Biochemical Networks Application to Hybrid Cell Cycle Models. Electr. Notes Theor. Comput. Sci. 284: 75-91 (2012)
- [j49]Dima Grigoriev, Sergey I. Nikolenko: Continuous hard-to-invert functions and biometric authentication. Groups Complexity Cryptology 4(1): 19-32 (2012)
- [j48]Dima Grigoriev, Vladimir Shpilrain: No-leak authentication by the Sherlock Holmes method. Groups Complexity Cryptology 4(1): 177-189 (2012)
- [c35]Dima Grigoriev, Andreas Weber: Complexity of Solving Systems with Few Independent Monomials and Applications to Mass-Action Kinetics. CASC 2012: 143-154
- [c34]Vincent Noel, Dima Grigoriev, Sergei Vakulenko, Ovidiu Radulescu: Hybrid models of the cell cycle molecular machinery. HSB 2012: 88-105
- [i20]Dima Grigoriev, Vladimir V. Podolskii: Complexity of tropical and min-plus linear prevarieties. CoRR abs/1204.4578 (2012)
- 2010
- [j47]Dima Grigoriev, Vladimir Shpilrain: Authentication schemes from actions on graphs, groups, or rings. Ann. Pure Appl. Logic 162(3): 194-200 (2010)
- [j46]Dima Grigoriev, Gerald Tenenbaum: A low complexity probabilistic test for integer multiplication. J. Complexity 26(3): 263-267 (2010)
- [j45]
- [c33]Dima Grigoriev, Fritz Schwarz: Absolute factoring of non-holonomic ideals in the plane. ISSAC 2010: 93-97
- [i19]Dima Grigoriev, Vladimir Shpilrain: Authentication from matrix conjugation. CoRR abs/1010.5034 (2010)
- [i18]Dima Grigoriev, Vladimir Shpilrain: Authentication schemes from actions on graphs, groups, or rings. IACR Cryptology ePrint Archive 2010: 24 (2010)
- [i17]Dima Grigoriev, Vladimir Shpilrain: No-leak authentication by the Sherlock Holmes method. IACR Cryptology ePrint Archive 2010: 624 (2010)
2000 – 2009
- 2009
- [j44]Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: A Complete Public-Key Cryptosystem. Groups Complexity Cryptology 1(1): 1-12 (2009)
- [j43]Dima Grigoriev, Vladimir Shpilrain: Authentication from Matrix Conjugation. Groups Complexity Cryptology 1(2): 199-205 (2009)
- 2008
- [j42]Dima Grigoriev: Probabilistic Communication Complexity Over The Reals. Computational Complexity 17(4): 536-548 (2008)
- [j41]
- [c32]Dima Grigoriev, Fritz Schwarz: Loewy decomposition of third-order linear aPDE's in the plane. ISSAC 2008: 277-286
- [i16]Dima Grigoriev, Vladimir Shpilrain: Zero-knowledge authentication schemes from actions on graphs, groups, or rings. CoRR abs/0802.1661 (2008)
- 2007
- [i15]
- 2006
- [j40]Dima Grigoriev, Ilia V. Ponomarenko: Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits. Appl. Algebra Eng. Commun. Comput. 17(3-4): 239-255 (2006)
- [j39]Dima Grigoriev, Sergei Vakulenko: Algorithms and complexity in biological pattern formation problems. Ann. Pure Appl. Logic 141(3): 412-428 (2006)
- [e1]Dima Grigoriev, John Harrison, Edward A. Hirsch (Eds.): Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings. Lecture Notes in Computer Science 3967, Springer 2006, ISBN 3-540-34166-8
- [i14]Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: A Complete Public-Key Cryptosystem. Electronic Colloquium on Computational Complexity (ECCC) 13 (2006)
- 2005
- [j38]Dima Grigoriev, Dmitrii V. Pasechnik: Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Computational Complexity 14(1): 20-52 (2005)
- [j37]
- [c31]
- [i13]Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: Time hierarchies for cryptographic function inversion with advice. Electronic Colloquium on Computational Complexity (ECCC)(076) (2005)
- 2004
- [j36]Dima Grigoriev, Fritz Schwarz: Factoring and Solving Linear Partial Differential Equations. Computing 73(2): 179-197 (2004)
- [j35]Dima Burago, Dima Grigoriev, Anatol Slissenko: Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. Theor. Comput. Sci. 315(2-3): 371-404 (2004)
- [i12]Dima Grigoriev, Dmitrii V. Pasechnik: Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets. CoRR cs.SC/0403008 (2004)
- 2003
- [j34]Dima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas. Theor. Comput. Sci. 1(303): 83-102 (2003)
- [i11]Dima Grigoriev, Ilia V. Ponomarenko: Homomorphic public-key cryptosystems and encrypting boolean circuits. CoRR cs.CR/0301022 (2003)
- [i10]Dima Grigoriev, Ilia V. Ponomarenko: Homomorphic public-key cryptosystems over groups and rings. CoRR cs.CR/0309010 (2003)
- [i9]
- 2002
- [j33]Dima Grigoriev: Approximation and Complexity II: Iterated Integration. Foundations of Computational Mathematics 2(3): 295-304 (2002)
- [c30]Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Exponential Lower Bound for Static Semi-algebraic Proofs. ICALP 2002: 257-268
- [c29]Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of Semi-algebraic Proofs. STACS 2002: 419-430
- [i8]Dima Grigoriev, Ilia V. Ponomarenko: On non-abelian homomorphic public-key cryptosystems. CoRR cs.CR/0207079 (2002)
- [i7]
- [i6]Dima Grigoriev: Public-key cryptography and invariant theory. Electronic Colloquium on Computational Complexity (ECCC)(042) (2002)
- 2001
- [j32]Dima Grigoriev, Nicolai Vorobjov: Complexity of Null-and Positivstellensatz proofs. Ann. Pure Appl. Logic 113(1-3): 153-160 (2001)
- [j31]Dima Grigoriev: Complexity of Positivstellensatz proofs for the knapsack. Computational Complexity 10(2): 139-154 (2001)
- [j30]Dima Grigoriev: Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval. Foundations of Computational Mathematics 1(3): 289-295 (2001)
- [j29]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62(2): 267-289 (2001)
- [j28]Felipe Cucker, Dima Grigoriev: There are No Sparse NPw-Hard Sets. SIAM J. Comput. 31(1): 193-198 (2001)
- [j27]Dima Grigoriev: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259(1-2): 613-622 (2001)
- [c28]
- [i5]Dima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas. Electronic Colloquium on Computational Complexity (ECCC) 8(11) (2001)
- [i4]Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of semi-algebraic proofs. Electronic Colloquium on Computational Complexity (ECCC)(103) (2001)
- 2000
- [j26]Dima Grigoriev, Alexander A. Razborov: Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Appl. Algebra Eng. Commun. Comput. 10(6): 465-487 (2000)
- [j25]Dima Grigoriev, Yagati N. Lakshman: Algorithms for Computing Sparse Shifts for Multivariate Polynomials. Appl. Algebra Eng. Commun. Comput. 11(1): 43-67 (2000)
- [j24]
- [c27]Dima Grigoriev, Nicolai Vorobjov: Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. ISSAC 2000: 137-146
1990 – 1999
- 1999
- [j23]Dima Grigoriev: Complexity lower bounds for randomized computation trees over zero characteristic fields. Computational Complexity 8(4): 316-329 (1999)
- [j22]Dima Grigoriev: Randomized Complexity Lower Bound for Arrangements and Polyhedra. Discrete & Computational Geometry 21(3): 329-344 (1999)
- [j21]Felipe Cucker, Dima Grigoriev: Complexity Lower Bounds for Approximation Algebraic Computation Trees. J. Complexity 15(4): 499-512 (1999)
- [c26]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). IEEE Conference on Computational Complexity 1999: 5
- [c25]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556
- 1998
- [j20]Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An exponential lower bound on the size of algebraic decision trees for Max. Computational Complexity 7(3): 193-203 (1998)
- [j19]Dima Grigoriev, Marek Karpinski: Computing the Additive Complexity of Algebraic Circuits with Root Extracting. SIAM J. Comput. 27(3): 694-701 (1998)
- [c24]Dima Grigoriev, Alexander A. Razborov: Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. FOCS 1998: 269-278
- [c23]Dima Grigoriev: Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. FOCS 1998: 648-652
- [c22]Dima Grigoriev, Anatol Slissenko: Polytime Algorithm for the Shortest Path in a Homotopy Class Amidst Semi-Algebraic Obstacles in the Plane. ISSAC 1998: 17-24
- [c21]
- [c20]Dima Grigoriev, Marek Karpinski: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577-582
- 1997
- [j18]Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. Computational Complexity 6(4): 357-375 (1997)
- [j17]Dima Grigoriev, Marek Karpinski, Roman Smolensky: Randomization and the Computational Power of Analytic and Algebraic Decision Trees. Computational Complexity 6(4): 376-388 (1997)
- [j16]Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. Discrete & Computational Geometry 17(2): 191-215 (1997)
- [j15]Dima Grigoriev: Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations. J. Complexity 13(1): 50-64 (1997)
- [j14]Felipe Cucker, Dima Grigoriev: On the Power of Real Turing Machines Over Binary Inputs. SIAM J. Comput. 26(1): 243-254 (1997)
- [j13]Dima Grigoriev: Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. Theor. Comput. Sci. 180(1-2): 217-228 (1997)
- [c19]Dima Grigoriev, Anatol Slissenko: Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. AAECC 1997: 114-129
- [c18]
- 1996
- [j12]Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko: Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. Fundam. Inform. 28(3-4): 297-301 (1996)
- [j11]Dima Grigoriev: NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. Theor. Comput. Sci. 157(1): 79-90 (1996)
- [j10]Dima Grigoriev, Marek Karpinski: Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. Theor. Comput. Sci. 157(1): 91-99 (1996)
- [j9]Dima Grigoriev, Nicolai Vorobjov: Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. Theor. Comput. Sci. 157(2): 185-214 (1996)
- [c17]
- [c16]Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. STOC 1996: 612-619
- [i3]Dima Grigoriev, Marek Karpinski: Randomized Omega(n2) Lower Bound for Knapsack. Electronic Colloquium on Computational Complexity (ECCC) 3(58) (1996)
- 1995
- [j8]Dima Grigoriev, Michael F. Singer, Andrew Chi-Chih Yao: On Computing Algebraic Functions Using Logarithms and Exponentials. SIAM J. Comput. 24(2): 242-246 (1995)
- [c15]Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. FOCS 1995: 258-265
- [c14]Dima Grigoriev, Yagati N. Lakshman: Algorithms for Computing Sparse Shifts for Multivariate Polynomials. ISSAC 1995: 96-103
- [i2]Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX. Electronic Colloquium on Computational Complexity (ECCC) 2(57) (1995)
- [i1]Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. Electronic Colloquium on Computational Complexity (ECCC) 2(63) (1995)
- 1994
- [j7]Dima Grigoriev, Marek Karpinski, Michael F. Singer: Computational Complexity of Sparse Rational Interpolation. SIAM J. Comput. 23(1): 1-11 (1994)
- [j6]Dima Grigoriev: Deviation Theorems for Solutions of Differential Equations and Applications to Lower Bounds on Parallel Complexity of Sigmoids. Theor. Comput. Sci. 133(1): 23-33 (1994)
- [c13]Dima Grigoriev, Nicolai Vorobjov: Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. FOCS 1994: 548-552
- [c12]Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Lower bounds on testing membership to a polyhedron by algebraic decision trees. STOC 1994: 635-644
- 1993
- [c11]Dima Grigoriev, Marek Karpinski: A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. AAECC 1993: 162-169
- 1992
- [c10]Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko: Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. ISSAC 1992: 117-122
- 1991
- [c9]Dima Grigoriev, Marek Karpinski: An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]. FOCS 1991: 662-669
- [c8]
- 1990
- [j5]Dima Grigoriev: Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators. J. Symb. Comput. 10(1): 7-38 (1990)
- [j4]Dima Grigoriev, Marek Karpinski, Michael F. Singer: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. SIAM J. Comput. 19(6): 1059-1063 (1990)
- [c7]Dima Grigoriev, Marek Karpinski, Michael F. Singer: Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents. FOCS 1990: 840-846
- [c6]Dima Grigoriev: How to Test in Subexponential Time Whether Two Points Can Be Connected by a Curve in a Semialgebraic Set. ISSAC 1990: 104-105
- [c5]Dima Grigoriev: Complexity of Irreducibility Testing for a System of Linear Ordinary Differential Equations. ISSAC 1990: 225-230
1980 – 1989
- 1988
- [j3]Dima Grigoriev, Nicolai Vorobjov: Solving Systems of Polynomial Inequalities in Subexponential Time. J. Symb. Comput. 5(1/2): 37-64 (1988)
- [j2]
- 1987
- [c4]Dima Grigoriev, Marek Karpinski: The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract). FOCS 1987: 166-172
- 1984
- [c3]Alexander L. Chistov, Dima Grigoriev: Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. MFCS 1984: 17-31
- 1982
- [j1]
- 1981
- [c2]Dima Grigoriev: Multiplicative Complexity of a Bilinear Form over a Commutative Ring. MFCS 1981: 281-286
1970 – 1979
- 1978
- [c1]Dima Grigoriev: Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication. MFCS 1978: 250-256
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-14 22:39 CEST by the dblp team