The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Dima Grigoriev: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Dima Grigoriev, Nicolai Vorobjov
    Solving Systems of Polynomial Inequalities in Subexponential Time. [Citation Graph (1, 0)][DBLP]
    J. Symb. Comput., 1988, v:5, n:1/2, pp:37-64 [Journal]
  2. Dima Grigoriev, Marek Karpinski
    A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. [Citation Graph (0, 0)][DBLP]
    AAECC, 1993, pp:162-169 [Conf]
  3. Dima Grigoriev, Anatol Slissenko
    Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. [Citation Graph (0, 0)][DBLP]
    AAECC, 1997, pp:114-129 [Conf]
  4. Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
    Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1999, pp:5- [Conf]
  5. Dima Grigoriev
    Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. [Citation Graph (0, 0)][DBLP]
    FOCS, 1998, pp:648-652 [Conf]
  6. Dima Grigoriev, Marek Karpinski
    The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) [Citation Graph (0, 0)][DBLP]
    FOCS, 1987, pp:166-172 [Conf]
  7. Dima Grigoriev, Marek Karpinski
    An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] [Citation Graph (0, 0)][DBLP]
    FOCS, 1991, pp:662-669 [Conf]
  8. Dima Grigoriev, Marek Karpinski, Michael F. Singer
    Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents [Citation Graph (0, 0)][DBLP]
    FOCS, 1990, pp:840-846 [Conf]
  9. Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
    Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    FOCS, 1995, pp:258-265 [Conf]
  10. Dima Grigoriev, Alexander A. Razborov
    Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. [Citation Graph (0, 0)][DBLP]
    FOCS, 1998, pp:269-278 [Conf]
  11. Dima Grigoriev, Nicolai Vorobjov
    Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates [Citation Graph (0, 0)][DBLP]
    FOCS, 1994, pp:548-552 [Conf]
  12. Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik
    Exponential Lower Bound for Static Semi-algebraic Proofs. [Citation Graph (0, 0)][DBLP]
    ICALP, 2002, pp:257-268 [Conf]
  13. Dima Grigoriev
    How to Test in Subexponential Time Whether Two Points Can Be Connected by a Curve in a Semialgebraic Set. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1990, pp:104-105 [Conf]
  14. Dima Grigoriev
    Complexity of Irreducibility Testing for a System of Linear Ordinary Differential Equations. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1990, pp:225-230 [Conf]
  15. Dima Grigoriev
    Testing Shift-Equivalence of Polynomials Using Quantum Machines. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1996, pp:49-54 [Conf]
  16. Dima Grigoriev, Marek Karpinski
    Algorithms for Sparse Rational Interpolation. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1991, pp:7-13 [Conf]
  17. Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko
    Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1992, pp:117-122 [Conf]
  18. Dima Grigoriev, Yagati N. Lakshman
    Algorithms for Computing Sparse Shifts for Multivariate Polynomials. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1995, pp:96-103 [Conf]
  19. Dima Grigoriev, Fritz Schwarz
    Generalized Loewy-decomposition of d-modules. [Citation Graph (0, 0)][DBLP]
    ISSAC, 2005, pp:163-170 [Conf]
  20. Dima Grigoriev, Anatol Slissenko
    Polytime Algorithm for the Shortest Path in a Homotopy Class Amidst Semi-Algebraic Obstacles in the Plane. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1998, pp:17-24 [Conf]
  21. Dima Grigoriev, Nicolai Vorobjov
    Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. [Citation Graph (0, 0)][DBLP]
    ISSAC, 2000, pp:137-146 [Conf]
  22. Alexander L. Chistov, Dima Grigoriev
    Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. [Citation Graph (0, 0)][DBLP]
    MFCS, 1984, pp:17-31 [Conf]
  23. Felipe Cucker, Dima Grigoriev
    There Are No Sparse NPW-Hard Sets. [Citation Graph (0, 0)][DBLP]
    MFCS, 2001, pp:285-291 [Conf]
  24. Dima Grigoriev
    Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication. [Citation Graph (0, 0)][DBLP]
    MFCS, 1978, pp:250-256 [Conf]
  25. Dima Grigoriev
    Multiplicative Complexity of a Bilinear Form over a Commutative Ring. [Citation Graph (0, 0)][DBLP]
    MFCS, 1981, pp:281-286 [Conf]
  26. Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik
    Complexity of Semi-algebraic Proofs. [Citation Graph (0, 0)][DBLP]
    STACS, 2002, pp:419-430 [Conf]
  27. Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
    Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. [Citation Graph (0, 0)][DBLP]
    STOC, 1999, pp:547-556 [Conf]
  28. Dima Grigoriev
    Randomized Complexity Lower Bounds. [Citation Graph (0, 0)][DBLP]
    STOC, 1998, pp:219-223 [Conf]
  29. Dima Grigoriev, Marek Karpinski
    Randomized Omega(n2) Lower Bound for Knapsack. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:76-85 [Conf]
  30. Dima Grigoriev, Marek Karpinski
    An Exponential Lower Bound for Depth 3 Arithmetic Circuits. [Citation Graph (0, 0)][DBLP]
    STOC, 1998, pp:577-582 [Conf]
  31. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
    A Lower Bound for Randomized Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    STOC, 1996, pp:612-619 [Conf]
  32. Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
    Lower bounds on testing membership to a polyhedron by algebraic decision trees. [Citation Graph (0, 0)][DBLP]
    STOC, 1994, pp:635-644 [Conf]
  33. Dima Grigoriev, Yagati N. Lakshman
    Algorithms for Computing Sparse Shifts for Multivariate Polynomials. [Citation Graph (0, 0)][DBLP]
    Appl. Algebra Eng. Commun. Comput., 2000, v:11, n:1, pp:43-67 [Journal]
  34. Dima Grigoriev, Alexander A. Razborov
    Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. [Citation Graph (0, 0)][DBLP]
    Appl. Algebra Eng. Commun. Comput., 2000, v:10, n:6, pp:465-487 [Journal]
  35. Dima Grigoriev, Ilia V. Ponomarenko
    Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits. [Citation Graph (0, 0)][DBLP]
    Appl. Algebra Eng. Commun. Comput., 2006, v:17, n:3-4, pp:239-255 [Journal]
  36. Dima Grigoriev, Nicolai Vorobjov
    Complexity of Null-and Positivstellensatz proofs. [Citation Graph (0, 0)][DBLP]
    Ann. Pure Appl. Logic, 2001, v:113, n:1-3, pp:153-160 [Journal]
  37. Dima Grigoriev, S. Vakulenko
    Algorithms and complexity in biological pattern formation problems. [Citation Graph (0, 0)][DBLP]
    Ann. Pure Appl. Logic, 2006, v:141, n:3, pp:412-428 [Journal]
  38. Dima Grigoriev
    Complexity of Positivstellensatz proofs for the knapsack. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2001, v:10, n:2, pp:139-154 [Journal]
  39. Dima Grigoriev
    Complexity lower bounds for randomized computation trees over zero characteristic fields. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1999, v:8, n:4, pp:316-329 [Journal]
  40. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
    A Lower Bound for Randomized Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1997, v:6, n:4, pp:357-375 [Journal]
  41. Dima Grigoriev, Marek Karpinski, Roman Smolensky
    Randomization and the Computational Power of Analytic and Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1997, v:6, n:4, pp:376-388 [Journal]
  42. Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao
    An exponential lower bound on the size of algebraic decision trees for Max. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1998, v:7, n:3, pp:193-203 [Journal]
  43. Dima Grigoriev, Dmitrii V. Pasechnik
    Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2005, v:14, n:1, pp:20-52 [Journal]
  44. Dima Grigoriev, Fritz Schwarz
    Factoring and Solving Linear Partial Differential Equations. [Citation Graph (0, 0)][DBLP]
    Computing, 2004, v:73, n:2, pp:179-197 [Journal]
  45. Dima Grigoriev, Ilia V. Ponomarenko
    On non-abelian homomorphic public-key cryptosystems [Citation Graph (0, 0)][DBLP]
    CoRR, 2002, v:0, n:, pp:- [Journal]
  46. Dima Grigoriev
    Public-key cryptography and invariant theory [Citation Graph (0, 0)][DBLP]
    CoRR, 2002, v:0, n:, pp:- [Journal]
  47. Dima Grigoriev, Ilia V. Ponomarenko
    Homomorphic public-key cryptosystems and encrypting boolean circuits [Citation Graph (0, 0)][DBLP]
    CoRR, 2003, v:0, n:, pp:- [Journal]
  48. Dima Grigoriev, Ilia V. Ponomarenko
    Homomorphic public-key cryptosystems over groups and rings [Citation Graph (0, 0)][DBLP]
    CoRR, 2003, v:0, n:, pp:- [Journal]
  49. Dima Grigoriev
    Weak Bezout inequality for D-modules [Citation Graph (0, 0)][DBLP]
    CoRR, 2003, v:0, n:, pp:- [Journal]
  50. Dima Grigoriev, Dmitrii V. Pasechnik
    Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets [Citation Graph (0, 0)][DBLP]
    CoRR, 2004, v:0, n:, pp:- [Journal]
  51. Dima Grigoriev
    Randomized Complexity Lower Bound for Arrangements and Polyhedra. [Citation Graph (0, 0)][DBLP]
    Discrete & Computational Geometry, 1999, v:21, n:3, pp:329-344 [Journal]
  52. Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
    Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. [Citation Graph (0, 0)][DBLP]
    Discrete & Computational Geometry, 1997, v:17, n:2, pp:191-215 [Journal]
  53. Dima Grigoriev, Edward A. Hirsch
    Algebraic proof systems over formulas [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:11, pp:- [Journal]
  54. Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik
    Complexity of semi-algebraic proofs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:103, pp:- [Journal]
  55. Dima Grigoriev
    Public-key cryptography and invariant theory [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:042, pp:- [Journal]
  56. Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev
    Time hierarchies for cryptographic function inversion with advice [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:076, pp:- [Journal]
  57. Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao
    An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:57, pp:- [Journal]
  58. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
    A Lower Bound for Randomized Algebraic Decision Trees [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:63, pp:- [Journal]
  59. Dima Grigoriev
    Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval. [Citation Graph (0, 0)][DBLP]
    Foundations of Computational Mathematics, 2001, v:1, n:3, pp:289-295 [Journal]
  60. Dima Grigoriev
    Approximation and Complexity II: Iterated Integration. [Citation Graph (0, 0)][DBLP]
    Foundations of Computational Mathematics, 2002, v:2, n:3, pp:295-304 [Journal]
  61. Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko
    Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. [Citation Graph (0, 0)][DBLP]
    Fundam. Inform., 1996, v:28, n:3-4, pp:297-301 [Journal]
  62. Felipe Cucker, Dima Grigoriev
    Complexity Lower Bounds for Approximation Algebraic Computation Trees. [Citation Graph (0, 0)][DBLP]
    J. Complexity, 1999, v:15, n:4, pp:499-512 [Journal]
  63. Dima Grigoriev
    Topological Complexity of the Range Searching. [Citation Graph (0, 0)][DBLP]
    J. Complexity, 2000, v:16, n:1, pp:50-53 [Journal]
  64. Dima Grigoriev
    Weak Bézout inequality for D-modules. [Citation Graph (0, 0)][DBLP]
    J. Complexity, 2005, v:21, n:4, pp:532-542 [Journal]
  65. Dima Grigoriev
    Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations. [Citation Graph (0, 0)][DBLP]
    J. Complexity, 1997, v:13, n:1, pp:50-64 [Journal]
  66. Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
    Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2001, v:62, n:2, pp:267-289 [Journal]
  67. Dima Grigoriev
    Complexity of Deciding Tarski Algebra. [Citation Graph (0, 0)][DBLP]
    J. Symb. Comput., 1988, v:5, n:1/2, pp:65-108 [Journal]
  68. Dima Grigoriev
    Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators. [Citation Graph (0, 0)][DBLP]
    J. Symb. Comput., 1990, v:10, n:1, pp:7-38 [Journal]
  69. Felipe Cucker, Dima Grigoriev
    There are No Sparse NPw-Hard Sets. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2001, v:31, n:1, pp:193-198 [Journal]
  70. Felipe Cucker, Dima Grigoriev
    On the Power of Real Turing Machines Over Binary Inputs. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1997, v:26, n:1, pp:243-254 [Journal]
  71. Dima Grigoriev, Marek Karpinski
    Computing the Additive Complexity of Algebraic Circuits with Root Extracting. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1998, v:27, n:3, pp:694-701 [Journal]
  72. Dima Grigoriev, Marek Karpinski, Michael F. Singer
    Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1990, v:19, n:6, pp:1059-1063 [Journal]
  73. Dima Grigoriev, Marek Karpinski, Michael F. Singer
    Computational Complexity of Sparse Rational Interpolation. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1994, v:23, n:1, pp:1-11 [Journal]
  74. Dima Grigoriev, Michael F. Singer, Andrew Chi-Chih Yao
    On Computing Algebraic Functions Using Logarithms and Exponentials. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1995, v:24, n:2, pp:242-246 [Journal]
  75. Dima Burago, Dima Grigoriev, Anatol Slissenko
    Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2004, v:315, n:2-3, pp:371-404 [Journal]
  76. Dima Grigoriev
    Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2001, v:259, n:1-2, pp:613-622 [Journal]
  77. Dima Grigoriev
    Deviation Theorems for Solutions of Differential Equations and Applications to Lower Bounds on Parallel Complexity of Sigmoids. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1994, v:133, n:1, pp:23-33 [Journal]
  78. Dima Grigoriev
    NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:157, n:1, pp:79-90 [Journal]
  79. Dima Grigoriev
    Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1997, v:180, n:1-2, pp:217-228 [Journal]
  80. Dima Grigoriev, Edward A. Hirsch
    Algebraic proof systems over formulas. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2003, v:1, n:303, pp:83-102 [Journal]
  81. Dima Grigoriev, Marek Karpinski
    Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:157, n:1, pp:91-99 [Journal]
  82. Dima Grigoriev, Nicolai Vorobjov
    Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:157, n:2, pp:185-214 [Journal]
  83. Dima Grigoriev
    Additive Complexity in Directed Computations. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1982, v:19, n:, pp:39-67 [Journal]
  84. Dima Grigoriev
    Probabilistic communication complexity over the reals [Citation Graph (0, 0)][DBLP]
    CoRR, 2007, v:0, n:, pp:- [Journal]

  85. Loewy decomposition of third-order linear aPDE's in the plane. [Citation Graph (, )][DBLP]


  86. Probabilistic Communication Complexity Over The Reals. [Citation Graph (, )][DBLP]


  87. Zero-knowledge authentication schemes from actions on graphs, groups, or rings [Citation Graph (, )][DBLP]


  88. A Complete Public-Key Cryptosystem. [Citation Graph (, )][DBLP]


Search in 0.016secs, Finished in 0.019secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002