dblp.uni-trier.dewww.uni-trier.de

Dima Grigoriev Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2008
91EEDima Grigoriev, Fritz Schwarz: Loewy decomposition of third-order linear aPDE's in the plane. ISSAC 2008: 277-286
90EEDima Grigoriev, Vladimir Shpilrain: Zero-knowledge authentication schemes from actions on graphs, groups, or rings CoRR abs/0802.1661: (2008)
89EEDima Grigoriev: Probabilistic Communication Complexity Over The Reals. Computational Complexity 17(4): 536-548 (2008)
88EESergei N. Artëmov, Volker Diekert, Dima Grigoriev: Foreword. Theory Comput. Syst. 43(2): 99 (2008)
2007
87EEDima 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
85EEDima Grigoriev, S. Vakulenko: Algorithms and complexity in biological pattern formation problems. Ann. Pure Appl. Logic 141(3): 412-428 (2006)
84EEDima Grigoriev, Ilia V. Ponomarenko: Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits. Appl. Algebra Eng. Commun. Comput. 17(3-4): 239-255 (2006)
83EEDima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: A Complete Public-Key Cryptosystem. Electronic Colloquium on Computational Complexity (ECCC) 13: (2006)
2005
82EEDima Grigoriev, Fritz Schwarz: Generalized Loewy-decomposition of d-modules. ISSAC 2005: 163-170
81EEDima Grigoriev, Dmitrii V. Pasechnik: Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Computational Complexity 14(1): 20-52 (2005)
80EEDima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev: Time hierarchies for cryptographic function inversion with advice Electronic Colloquium on Computational Complexity (ECCC)(076): (2005)
79EEDima Grigoriev: Weak Bézout inequality for D-modules. J. Complexity 21(4): 532-542 (2005)
2004
78EEDima Grigoriev, Dmitrii V. Pasechnik: Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets CoRR cs.SC/0403008: (2004)
77EEDima Grigoriev, Fritz Schwarz: Factoring and Solving Linear Partial Differential Equations. Computing 73(2): 179-197 (2004)
76EEDima 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
75EEDima Grigoriev, Ilia V. Ponomarenko: Homomorphic public-key cryptosystems and encrypting boolean circuits CoRR cs.CR/0301022: (2003)
74EEDima Grigoriev, Ilia V. Ponomarenko: Homomorphic public-key cryptosystems over groups and rings CoRR cs.CR/0309010: (2003)
73EEDima Grigoriev: Weak Bezout inequality for D-modules CoRR cs.SC/0311053: (2003)
72EEDima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas. Theor. Comput. Sci. 1(303): 83-102 (2003)
2002
71EEDima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Exponential Lower Bound for Static Semi-algebraic Proofs. ICALP 2002: 257-268
70EEDima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of Semi-algebraic Proofs. STACS 2002: 419-430
69EEDima Grigoriev, Ilia V. Ponomarenko: On non-abelian homomorphic public-key cryptosystems CoRR cs.CR/0207079: (2002)
68EEDima Grigoriev: Public-key cryptography and invariant theory CoRR cs.CR/0207080: (2002)
67EEDima Grigoriev: Public-key cryptography and invariant theory Electronic Colloquium on Computational Complexity (ECCC)(042): (2002)
66EEDima Grigoriev: Approximation and Complexity II: Iterated Integration. Foundations of Computational Mathematics 2(3): 295-304 (2002)
2001
65EEFelipe 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)
63EEDima Grigoriev: Complexity of Positivstellensatz proofs for the knapsack. Computational Complexity 10(2): 139-154 (2001)
62EEDima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik: Complexity of semi-algebraic proofs Electronic Colloquium on Computational Complexity (ECCC)(103): (2001)
61EEDima Grigoriev, Edward A. Hirsch: Algebraic proof systems over formulas Electronic Colloquium on Computational Complexity (ECCC) 8(11): (2001)
60EEDima 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)
58EEFelipe Cucker, Dima Grigoriev: There are No Sparse NPw-Hard Sets. SIAM J. Comput. 31(1): 193-198 (2001)
57EEDima Grigoriev: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259(1-2): 613-622 (2001)
2000
56EEDima Grigoriev, Nicolai Vorobjov: Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. ISSAC 2000: 137-146
55EEDima 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)
54EEDima Grigoriev, Yagati N. Lakshman: Algorithms for Computing Sparse Shifts for Multivariate Polynomials. Appl. Algebra Eng. Commun. Comput. 11(1): 43-67 (2000)
53EEDima Grigoriev: Topological Complexity of the Range Searching. J. Complexity 16(1): 50-53 (2000)
1999
52EESamuel 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
51EESamuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556
50EEDima Grigoriev: Complexity lower bounds for randomized computation trees over zero characteristic fields. Computational Complexity 8(4): 316-329 (1999)
49EEDima Grigoriev: Randomized Complexity Lower Bound for Arrangements and Polyhedra. Discrete & Computational Geometry 21(3): 329-344 (1999)
48EEFelipe Cucker, Dima Grigoriev: Complexity Lower Bounds for Approximation Algebraic Computation Trees. J. Complexity 15(4): 499-512 (1999)
1998
47EEDima Grigoriev, Alexander A. Razborov: Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. FOCS 1998: 269-278
46EEDima Grigoriev: Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. FOCS 1998: 648-652
45EEDima Grigoriev, Anatol Slissenko: Polytime Algorithm for the Shortest Path in a Homotopy Class Amidst Semi-Algebraic Obstacles in the Plane. ISSAC 1998: 17-24
44EEDima Grigoriev: Randomized Complexity Lower Bounds. STOC 1998: 219-223
43EEDima Grigoriev, Marek Karpinski: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577-582
42EEDima 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
40EEDima Grigoriev, Anatol Slissenko: Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. AAECC 1997: 114-129
39EEDima 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)
36EEDima 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)
35EEDima 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)
33EEDima Grigoriev: Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. Theor. Comput. Sci. 180(1-2): 217-228 (1997)
1996
32EEDima Grigoriev: Testing Shift-Equivalence of Polynomials Using Quantum Machines. ISSAC 1996: 49-54
31EEDima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. STOC 1996: 612-619
30EEDima 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)
28EEDima Grigoriev: NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. Theor. Comput. Sci. 157(1): 79-90 (1996)
27EEDima Grigoriev, Marek Karpinski: Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. Theor. Comput. Sci. 157(1): 91-99 (1996)
26EEDima 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
24EEDima Grigoriev, Yagati N. Lakshman: Algorithms for Computing Sparse Shifts for Multivariate Polynomials. ISSAC 1995: 96-103
23EEDima 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)
22EEDima 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
19EEDima 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
16EEDima Grigoriev, Marek Karpinski: A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. AAECC 1993: 162-169
1992
15EEDima 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
13EEDima 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
11EEDima Grigoriev: How to Test in Subexponential Time Whether Two Points Can Be Connected by a Curve in a Semialgebraic Set. ISSAC 1990: 104-105
10EEDima 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
4EEAlexander 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
2EEDima Grigoriev: Multiplicative Complexity of a Bilinear Form over a Commutative Ring. MFCS 1981: 281-286
1978
1EEDima Grigoriev: Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication. MFCS 1978: 250-256

Coauthor Index

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)