Dima Grigoriev

	2008
91		Dima Grigoriev, Fritz Schwarz: Loewy decomposition of third-order linear aPDE's in the plane. ISSAC 2008: 277-286
90		Dima Grigoriev, Vladimir Shpilrain: Zero-knowledge authentication schemes from actions on graphs, groups, or rings CoRR abs/0802.1661: (2008)
89		Dima Grigoriev: Probabilistic Communication Complexity Over The Reals. Computational Complexity 17(4): 536-548 (2008)
88		Sergei N. Artëmov, Volker Diekert, Dima Grigoriev: Foreword. Theory Comput. Syst. 43(2): 99 (2008)
	2007
87		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		Dima Grigoriev, S. Vakulenko: Algorithms and complexity in biological pattern formation problems. Ann. Pure Appl. Logic 141(3): 412-428 (2006)
84		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		Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: A Complete Public-Key Cryptosystem. Electronic Colloquium on Computational Complexity (ECCC) 13: (2006)
	2005
82		Dima Grigoriev, Fritz Schwarz: Generalized Loewy-decomposition of d-modules. ISSAC 2005: 163-170
81		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		Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: Time hierarchies for cryptographic function inversion with advice Electronic Colloquium on Computational Complexity (ECCC)(076): (2005)
79		Dima Grigoriev: Weak Bézout inequality for D-modules. J. Complexity 21(4): 532-542 (2005)
	2004
78		Dima Grigoriev, Dmitrii V. Pasechnik: Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets CoRR cs.SC/0403008: (2004)
77		Dima Grigoriev, Fritz Schwarz: Factoring and Solving Linear Partial Differential Equations. Computing 73(2): 179-197 (2004)
76		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		Dima Grigoriev, Ilia V. Ponomarenko: Homomorphic public-key cryptosystems and encrypting boolean circuits CoRR cs.CR/0301022: (2003)
74		Dima Grigoriev, Ilia V. Ponomarenko: Homomorphic public-key cryptosystems over groups and rings CoRR cs.CR/0309010: (2003)
73		Dima Grigoriev: Weak Bezout inequality for D-modules CoRR cs.SC/0311053: (2003)
72		Dima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas. Theor. Comput. Sci. 1(303): 83-102 (2003)
	2002
71		Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Exponential Lower Bound for Static Semi-algebraic Proofs. ICALP 2002: 257-268
70		Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of Semi-algebraic Proofs. STACS 2002: 419-430
69		Dima Grigoriev, Ilia V. Ponomarenko: On non-abelian homomorphic public-key cryptosystems CoRR cs.CR/0207079: (2002)
68		Dima Grigoriev: Public-key cryptography and invariant theory CoRR cs.CR/0207080: (2002)
67		Dima Grigoriev: Public-key cryptography and invariant theory Electronic Colloquium on Computational Complexity (ECCC)(042): (2002)
66		Dima Grigoriev: Approximation and Complexity II: Iterated Integration. Foundations of Computational Mathematics 2(3): 295-304 (2002)
	2001
65		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		Dima Grigoriev: Complexity of Positivstellensatz proofs for the knapsack. Computational Complexity 10(2): 139-154 (2001)
62		Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of semi-algebraic proofs Electronic Colloquium on Computational Complexity (ECCC)(103): (2001)
61		Dima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas Electronic Colloquium on Computational Complexity (ECCC) 8(11): (2001)
60		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		Felipe Cucker, Dima Grigoriev: There are No Sparse NPw-Hard Sets. SIAM J. Comput. 31(1): 193-198 (2001)
57		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		Dima Grigoriev, Nicolai Vorobjov: Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. ISSAC 2000: 137-146
55		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		Dima Grigoriev, Yagati N. Lakshman: Algorithms for Computing Sparse Shifts for Multivariate Polynomials. Appl. Algebra Eng. Commun. Comput. 11(1): 43-67 (2000)
53		Dima Grigoriev: Topological Complexity of the Range Searching. J. Complexity 16(1): 50-53 (2000)
	1999
52		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		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		Dima Grigoriev: Complexity lower bounds for randomized computation trees over zero characteristic fields. Computational Complexity 8(4): 316-329 (1999)
49		Dima Grigoriev: Randomized Complexity Lower Bound for Arrangements and Polyhedra. Discrete & Computational Geometry 21(3): 329-344 (1999)
48		Felipe Cucker, Dima Grigoriev: Complexity Lower Bounds for Approximation Algebraic Computation Trees. J. Complexity 15(4): 499-512 (1999)
	1998
47		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		Dima Grigoriev: Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. FOCS 1998: 648-652
45		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		Dima Grigoriev: Randomized Complexity Lower Bounds. STOC 1998: 219-223
43		Dima Grigoriev, Marek Karpinski: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577-582
42		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		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		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		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		Dima Grigoriev: Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. Theor. Comput. Sci. 180(1-2): 217-228 (1997)
	1996
32		Dima Grigoriev: Testing Shift-Equivalence of Polynomials Using Quantum Machines. ISSAC 1996: 49-54
31		Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. STOC 1996: 612-619
30		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		Dima Grigoriev: NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. Theor. Comput. Sci. 157(1): 79-90 (1996)
27		Dima Grigoriev, Marek Karpinski: Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. Theor. Comput. Sci. 157(1): 91-99 (1996)
26		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		Dima Grigoriev, Yagati N. Lakshman: Algorithms for Computing Sparse Shifts for Multivariate Polynomials. ISSAC 1995: 96-103
23		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		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		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		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		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		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		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

Coauthor Index

1	Sergei N. Artëmov	[88]
2	Dima Burago	[76]
3	Samuel R. Buss	[51] [52] [59]
4	Alexander L. Chistov	[4]
5	Felipe Cucker	[34] [48] [58] [65]
6	Volker Diekert	[88]
7	John Harrison	[86]
8	Friedhelm Meyer auf der Heide	[22] [31] [38]
9	Edward A. Hirsch	[61] [62] [70] [71] [72] [80] [83] [86]
10	Russell Impagliazzo	[51] [52] [59]
11	Marek Karpinski	[5] [8] [12] [13] [14] [15] [16] [18] [19] [22] [23] [25] [27] [29] [30] [31] [36] [37] [38] [39] [41] [42] [43]
12	Yagati N. Lakshman	[24] [54]
13	Andrew M. Odlyzko	[15] [29]
14	Dmitrii V. Pasechnik	[62] [70] [71] [78] [81]
15	Konstantin Pervyshev	[80] [83]
16	Toniann Pitassi	[51] [52] [59]
17	Ilia V. Ponomarenko	[69] [74] [75] [84]
18	Alexander A. Razborov	[47] [55]
19	Fritz Schwarz	[77] [82] [91]
20	Vladimir Shpilrain	[90]
21	Michael F. Singer	[8] [12] [18] [21]
22	Anatol Slissenko	[40] [45] [76]
23	Roman Smolensky	[22] [31] [37] [38]
24	S. Vakulenko	[85]
25	Nicolai Vorobjov	[7] [19] [20] [25] [26] [36] [56] [64]
26	Andrew Chi-Chih Yao	[21] [23] [42]

Colors in the list of coauthors