| 2008 |
|---|
| 90 | EE | Dima Grigoriev,
Fritz Schwarz:
Loewy decomposition of third-order linear aPDE's in the plane.
ISSAC 2008: 277-286 |
| 89 | EE | Dima Grigoriev,
Vladimir Shpilrain:
Zero-knowledge authentication schemes from actions on graphs, groups, or rings
CoRR abs/0802.1661: (2008) |
| 88 | EE | Sergei N. Artëmov,
Volker Diekert,
Dima Grigoriev:
Foreword.
Theory Comput. Syst. 43(2): 99 (2008) |
| 2007 |
|---|
| 87 | EE | Dima Grigoriev:
Probabilistic communication complexity over the reals
CoRR abs/0710.2732: (2007) |
| 2006 |
|---|
| 86 | | Dima Grigoriev,
John Harrison,
Edward A. Hirsch:
Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings
Springer 2006 |
| 85 | EE | Dima Grigoriev,
S. Vakulenko:
Algorithms and complexity in biological pattern formation problems.
Ann. Pure Appl. Logic 141(3): 412-428 (2006) |
| 84 | EE | Dima Grigoriev,
Ilia V. Ponomarenko:
Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits.
Appl. Algebra Eng. Commun. Comput. 17(3-4): 239-255 (2006) |
| 83 | EE | Dima Grigoriev,
Edward A. Hirsch,
Konstantin Pervyshev:
A Complete Public-Key Cryptosystem.
Electronic Colloquium on Computational Complexity (ECCC) 13: (2006) |
| 2005 |
|---|
| 82 | EE | Dima Grigoriev,
Fritz Schwarz:
Generalized Loewy-decomposition of d-modules.
ISSAC 2005: 163-170 |
| 81 | EE | Dima Grigoriev,
Dmitrii V. Pasechnik:
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets.
Computational Complexity 14(1): 20-52 (2005) |
| 80 | EE | Dima Grigoriev,
Edward A. Hirsch,
Konstantin Pervyshev:
Time hierarchies for cryptographic function inversion with advice
Electronic Colloquium on Computational Complexity (ECCC)(076): (2005) |
| 79 | EE | Dima Grigoriev:
Weak Bézout inequality for D-modules.
J. Complexity 21(4): 532-542 (2005) |
| 2004 |
|---|
| 78 | EE | Dima Grigoriev,
Dmitrii V. Pasechnik:
Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets
CoRR cs.SC/0403008: (2004) |
| 77 | EE | Dima Grigoriev,
Fritz Schwarz:
Factoring and Solving Linear Partial Differential Equations.
Computing 73(2): 179-197 (2004) |
| 76 | EE | 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) |
| 2003 |
|---|
| 75 | EE | Dima Grigoriev,
Ilia V. Ponomarenko:
Homomorphic public-key cryptosystems and encrypting boolean circuits
CoRR cs.CR/0301022: (2003) |
| 74 | EE | Dima Grigoriev,
Ilia V. Ponomarenko:
Homomorphic public-key cryptosystems over groups and rings
CoRR cs.CR/0309010: (2003) |
| 73 | EE | Dima Grigoriev:
Weak Bezout inequality for D-modules
CoRR cs.SC/0311053: (2003) |
| 72 | EE | Dima Grigoriev,
Edward A. Hirsch:
Algebraic proof systems over formulas.
Theor. Comput. Sci. 1(303): 83-102 (2003) |
| 2002 |
|---|
| 71 | EE | Dima Grigoriev,
Edward A. Hirsch,
Dmitrii V. Pasechnik:
Exponential Lower Bound for Static Semi-algebraic Proofs.
ICALP 2002: 257-268 |
| 70 | EE | Dima Grigoriev,
Edward A. Hirsch,
Dmitrii V. Pasechnik:
Complexity of Semi-algebraic Proofs.
STACS 2002: 419-430 |
| 69 | EE | Dima Grigoriev,
Ilia V. Ponomarenko:
On non-abelian homomorphic public-key cryptosystems
CoRR cs.CR/0207079: (2002) |
| 68 | EE | Dima Grigoriev:
Public-key cryptography and invariant theory
CoRR cs.CR/0207080: (2002) |
| 67 | EE | Dima Grigoriev:
Public-key cryptography and invariant theory
Electronic Colloquium on Computational Complexity (ECCC)(042): (2002) |
| 66 | EE | Dima Grigoriev:
Approximation and Complexity II: Iterated Integration.
Foundations of Computational Mathematics 2(3): 295-304 (2002) |
| 2001 |
|---|
| 65 | EE | Felipe Cucker,
Dima Grigoriev:
There Are No Sparse NPW-Hard Sets.
MFCS 2001: 285-291 |
| 64 | | Dima Grigoriev,
Nicolai Vorobjov:
Complexity of Null-and Positivstellensatz proofs.
Ann. Pure Appl. Logic 113(1-3): 153-160 (2001) |
| 63 | EE | Dima Grigoriev:
Complexity of Positivstellensatz proofs for the knapsack.
Computational Complexity 10(2): 139-154 (2001) |
| 62 | EE | Dima Grigoriev,
Edward A. Hirsch,
Dmitrii V. Pasechnik:
Complexity of semi-algebraic proofs
Electronic Colloquium on Computational Complexity (ECCC)(103): (2001) |
| 61 | EE | Dima Grigoriev,
Edward A. Hirsch:
Algebraic proof systems over formulas
Electronic Colloquium on Computational Complexity (ECCC) 8(11): (2001) |
| 60 | EE | Dima Grigoriev:
Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval.
Foundations of Computational Mathematics 1(3): 289-295 (2001) |
| 59 | | 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) |
| 58 | EE | Felipe Cucker,
Dima Grigoriev:
There are No Sparse NPw-Hard Sets.
SIAM J. Comput. 31(1): 193-198 (2001) |
| 57 | EE | Dima Grigoriev:
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity.
Theor. Comput. Sci. 259(1-2): 613-622 (2001) |
| 2000 |
|---|
| 56 | EE | Dima Grigoriev,
Nicolai Vorobjov:
Bounds on numers of vectors of multiplicities for polynomials which are easy to compute.
ISSAC 2000: 137-146 |
| 55 | EE | 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) |
| 54 | EE | Dima Grigoriev,
Yagati N. Lakshman:
Algorithms for Computing Sparse Shifts for Multivariate Polynomials.
Appl. Algebra Eng. Commun. Comput. 11(1): 43-67 (2000) |
| 53 | EE | Dima Grigoriev:
Topological Complexity of the Range Searching.
J. Complexity 16(1): 50-53 (2000) |
| 1999 |
|---|
| 52 | EE | 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 |
| 51 | EE | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes.
STOC 1999: 547-556 |
| 50 | EE | Dima Grigoriev:
Complexity lower bounds for randomized computation trees over zero characteristic fields.
Computational Complexity 8(4): 316-329 (1999) |
| 49 | EE | Dima Grigoriev:
Randomized Complexity Lower Bound for Arrangements and Polyhedra.
Discrete & Computational Geometry 21(3): 329-344 (1999) |
| 48 | EE | Felipe Cucker,
Dima Grigoriev:
Complexity Lower Bounds for Approximation Algebraic Computation Trees.
J. Complexity 15(4): 499-512 (1999) |
| 1998 |
|---|
| 47 | EE | 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 |
| 46 | EE | Dima Grigoriev:
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs.
FOCS 1998: 648-652 |
| 45 | EE | 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 |
| 44 | EE | Dima Grigoriev:
Randomized Complexity Lower Bounds.
STOC 1998: 219-223 |
| 43 | EE | Dima Grigoriev,
Marek Karpinski:
An Exponential Lower Bound for Depth 3 Arithmetic Circuits.
STOC 1998: 577-582 |
| 42 | EE | 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) |
| 41 | | Dima Grigoriev,
Marek Karpinski:
Computing the Additive Complexity of Algebraic Circuits with Root Extracting.
SIAM J. Comput. 27(3): 694-701 (1998) |
| 1997 |
|---|
| 40 | | Dima Grigoriev,
Anatol Slissenko:
Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane.
AAECC 1997: 114-129 |
| 39 | EE | Dima Grigoriev,
Marek Karpinski:
Randomized Omega(n2) Lower Bound for Knapsack.
STOC 1997: 76-85 |
| 38 | | 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) |
| 37 | | Dima Grigoriev,
Marek Karpinski,
Roman Smolensky:
Randomization and the Computational Power of Analytic and Algebraic Decision Trees.
Computational Complexity 6(4): 376-388 (1997) |
| 36 | EE | 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) |
| 35 | EE | Dima Grigoriev:
Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations.
J. Complexity 13(1): 50-64 (1997) |
| 34 | | Felipe Cucker,
Dima Grigoriev:
On the Power of Real Turing Machines Over Binary Inputs.
SIAM J. Comput. 26(1): 243-254 (1997) |
| 33 | EE | Dima Grigoriev:
Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines.
Theor. Comput. Sci. 180(1-2): 217-228 (1997) |
| 1996 |
|---|
| 32 | EE | Dima Grigoriev:
Testing Shift-Equivalence of Polynomials Using Quantum Machines.
ISSAC 1996: 49-54 |
| 31 | EE | Dima Grigoriev,
Marek Karpinski,
Friedhelm Meyer auf der Heide,
Roman Smolensky:
A Lower Bound for Randomized Algebraic Decision Trees.
STOC 1996: 612-619 |
| 30 | EE | Dima Grigoriev,
Marek Karpinski:
Randomized Omega(n2) Lower Bound for Knapsack
Electronic Colloquium on Computational Complexity (ECCC) 3(58): (1996) |
| 29 | | 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) |
| 28 | EE | Dima Grigoriev:
NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns.
Theor. Comput. Sci. 157(1): 79-90 (1996) |
| 27 | EE | Dima Grigoriev,
Marek Karpinski:
Computability of the Additive Complexity of Algebraic Circuits with Root Extracting.
Theor. Comput. Sci. 157(1): 91-99 (1996) |
| 26 | EE | Dima Grigoriev,
Nicolai Vorobjov:
Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates.
Theor. Comput. Sci. 157(2): 185-214 (1996) |
| 1995 |
|---|
| 25 | | Dima Grigoriev,
Marek Karpinski,
Nicolai Vorobjov:
Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees.
FOCS 1995: 258-265 |
| 24 | EE | Dima Grigoriev,
Yagati N. Lakshman:
Algorithms for Computing Sparse Shifts for Multivariate Polynomials.
ISSAC 1995: 96-103 |
| 23 | EE | 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) |
| 22 | EE | 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) |
| 21 | | 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) |
| 1994 |
|---|
| 20 | | Dima Grigoriev,
Nicolai Vorobjov:
Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates
FOCS 1994: 548-552 |
| 19 | EE | Dima Grigoriev,
Marek Karpinski,
Nicolai Vorobjov:
Lower bounds on testing membership to a polyhedron by algebraic decision trees.
STOC 1994: 635-644 |
| 18 | | Dima Grigoriev,
Marek Karpinski,
Michael F. Singer:
Computational Complexity of Sparse Rational Interpolation.
SIAM J. Comput. 23(1): 1-11 (1994) |
| 17 | | 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) |
| 1993 |
|---|
| 16 | | Dima Grigoriev,
Marek Karpinski:
A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals.
AAECC 1993: 162-169 |
| 1992 |
|---|
| 15 | EE | 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 |
|---|
| 14 | | Dima Grigoriev,
Marek Karpinski:
An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
FOCS 1991: 662-669 |
| 13 | EE | Dima Grigoriev,
Marek Karpinski:
Algorithms for Sparse Rational Interpolation.
ISSAC 1991: 7-13 |
| 1990 |
|---|
| 12 | | Dima Grigoriev,
Marek Karpinski,
Michael F. Singer:
Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents
FOCS 1990: 840-846 |
| 11 | EE | 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 |
| 10 | EE | Dima Grigoriev:
Complexity of Irreducibility Testing for a System of Linear Ordinary Differential Equations.
ISSAC 1990: 225-230 |
| 9 | | Dima Grigoriev:
Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators.
J. Symb. Comput. 10(1): 7-38 (1990) |
| 8 | | 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) |
| 1988 |
|---|
| 7 | | Dima Grigoriev,
Nicolai Vorobjov:
Solving Systems of Polynomial Inequalities in Subexponential Time.
J. Symb. Comput. 5(1/2): 37-64 (1988) |
| 6 | | Dima Grigoriev:
Complexity of Deciding Tarski Algebra.
J. Symb. Comput. 5(1/2): 65-108 (1988) |
| 1987 |
|---|
| 5 | | Dima Grigoriev,
Marek Karpinski:
The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)
FOCS 1987: 166-172 |
| 1984 |
|---|
| 4 | | Alexander L. Chistov,
Dima Grigoriev:
Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields.
MFCS 1984: 17-31 |
| 1982 |
|---|
| 3 | | Dima Grigoriev:
Additive Complexity in Directed Computations.
Theor. Comput. Sci. 19: 39-67 (1982) |
| 1981 |
|---|
| 2 | | Dima Grigoriev:
Multiplicative Complexity of a Bilinear Form over a Commutative Ring.
MFCS 1981: 281-286 |
| 1978 |
|---|
| 1 | | Dima Grigoriev:
Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication.
MFCS 1978: 250-256 |
