| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Dima Grigoriev, Vladimir V. Podolskii |
Complexity of tropical and min-plus linear prevarieties  |
CoRR  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Gerald Tenenbaum |
A low complexity probabilistic test for integer multiplication. |
J. Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Vladimir Shpilrain |
No-leak authentication by the Sherlock Holmes method. |
IACR Cryptology ePrint Archive |
2010 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Vladimir Shpilrain |
Authentication schemes from actions on graphs, groups, or rings. |
IACR Cryptology ePrint Archive |
2010 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Vladimir Shpilrain |
Authentication schemes from actions on graphs, groups, or rings. |
Ann. Pure Appl. Logic |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Vladimir Shpilrain |
Authentication from matrix conjugation |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Sergei N. Artëmov, Volker Diekert, Dima Grigoriev |
Preface. |
Theory Comput. Syst. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Fritz Schwarz |
Absolute factoring of non-holonomic ideals in the plane. |
ISSAC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Probabilistic Communication Complexity Over The Reals. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification, 68W40 |
| 1 | Dima Grigoriev, Vladimir Shpilrain |
Zero-knowledge authentication schemes from actions on graphs, groups, or rings |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Sergei N. Artëmov, Volker Diekert, Dima Grigoriev |
Foreword. |
Theory Comput. Syst. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Fritz Schwarz |
Loewy decomposition of third-order linear aPDE's in the plane. |
ISSAC |
2008 |
DBLP DOI BibTeX RDF |
linear partial differential equations, loewy decomposition, factorization |
| 1 | Dima Grigoriev |
Probabilistic communication complexity over the reals |
CoRR |
2007 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev |
A Complete Public-Key Cryptosystem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, S. Vakulenko |
Algorithms and complexity in biological pattern formation problems. |
Ann. Pure Appl. Logic |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Ilia V. Ponomarenko |
Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits. |
Appl. Algebra Eng. Commun. Comput. |
2006 |
DBLP DOI BibTeX RDF |
Homomorphic cryptosystem, Free product of groups, Encrypting boolean circuits |
| 1 | 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 |
CSR |
2006 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev |
Time hierarchies for cryptographic function inversion with advice |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev |
Weak Bézout inequality for D-modules. |
J. Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Dmitrii V. Pasechnik |
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. |
Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
Subject classification. 68W30, 14Q20, 14Pxx, 13P10 |
| 1 | Dima Grigoriev, Fritz Schwarz |
Generalized Loewy-decomposition of d-modules. |
ISSAC |
2005 |
DBLP DOI BibTeX RDF |
Janet basis, Loewy decomposition, d-module |
| 1 | Dima Burago, Dima Grigoriev, Anatol Slissenko |
Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. |
Theor. Comput. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Fritz Schwarz |
Factoring and Solving Linear Partial Differential Equations. |
Computing |
2004 |
DBLP DOI BibTeX RDF |
Partial differential equations, factorization |
| 1 | Dima Grigoriev, Dmitrii V. Pasechnik |
Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets |
CoRR |
2004 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch |
Algebraic proof systems over formulas. |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Ilia V. Ponomarenko |
Homomorphic public-key cryptosystems over groups and rings |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Ilia V. Ponomarenko |
Homomorphic public-key cryptosystems and encrypting boolean circuits |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev |
Weak Bezout inequality for D-modules |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev |
Approximation and Complexity II: Iterated Integration. |
Foundations of Computational Mathematics |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Public-key cryptography and invariant theory |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Ilia V. Ponomarenko |
On non-abelian homomorphic public-key cryptosystems |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev |
Public-key cryptography and invariant theory |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik |
Exponential Lower Bound for Static Semi-algebraic Proofs. |
ICALP |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik |
Complexity of Semi-algebraic Proofs. |
STACS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval. |
Foundations of Computational Mathematics |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik |
Complexity of semi-algebraic proofs |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Edward A. Hirsch |
Algebraic proof systems over formulas |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev |
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. |
Theor. Comput. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Nicolai Vorobjov |
Complexity of Null-and Positivstellensatz proofs. |
Ann. Pure Appl. Logic |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Complexity of Positivstellensatz proofs for the knapsack. |
Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
Polynomial calculus, Positivstellensatz proofs, complexity of the knapsack |
| 1 | Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Felipe Cucker, Dima Grigoriev |
There are No Sparse NPw-Hard Sets. |
SIAM J. Comput. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Felipe Cucker, Dima Grigoriev |
There Are No Sparse NPW-Hard Sets. |
MFCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Topological Complexity of the Range Searching. |
J. Complexity |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Yagati N. Lakshman |
Algorithms for Computing Sparse Shifts for Multivariate Polynomials. |
Appl. Algebra Eng. Commun. Comput. |
2000 |
DBLP DOI BibTeX RDF |
Shifted sparse polynomial, Gröbner bases, Complexity. > |
| 1 | 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. |
2000 |
DBLP DOI BibTeX RDF |
Exponential lower bounds, Depth 3 arithmetic circuits, Finite fields |
| 1 | Dima Grigoriev, Nicolai Vorobjov |
Bounds on numers of vectors of multiplicities for polynomials which are easy to compute. |
ISSAC |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Felipe Cucker, Dima Grigoriev |
Complexity Lower Bounds for Approximation Algebraic Computation Trees. |
J. Complexity |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Randomized Complexity Lower Bound for Arrangements and Polyhedra. |
Discrete & Computational Geometry |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Complexity lower bounds for randomized computation trees over zero characteristic fields. |
Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
Randomized computation trees, multiplicative complexity, distinctness problem, knapsack problem |
| 1 | Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). (PDF / PS) |
IEEE Conference on Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
counting principles, graph tautologies, algebraic proof systems, binomial proofs, Nullstellensatz proofs, polynomial calculus proofs, propositional logic, Proof complexity |
| 1 | Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. |
STOC |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao |
An exponential lower bound on the size of algebraic decision trees for Max. |
Computational Complexity |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
Computing the Additive Complexity of Algebraic Circuits with Root Extracting. |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. |
FOCS |
1998 |
DBLP DOI BibTeX RDF |
Nullstellensatz proofs, Tseitin's tautologies, lower bounds, expander |
| 1 | Dima Grigoriev, Alexander A. Razborov |
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. |
FOCS |
1998 |
DBLP DOI BibTeX RDF |
depth 3 arithmetic circuits, exponential lower bounds, approximating by sparse polynomials |
| 1 | Dima Grigoriev, Anatol Slissenko |
Polytime Algorithm for the Shortest Path in a Homotopy Class Amidst Semi-Algebraic Obstacles in the Plane. |
ISSAC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Randomized Complexity Lower Bounds. |
STOC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
An Exponential Lower Bound for Depth 3 Arithmetic Circuits. |
STOC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. |
Theor. Comput. Sci. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations. |
J. Complexity |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov |
Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. |
Discrete & Computational Geometry |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky |
A Lower Bound for Randomized Algebraic Decision Trees. |
Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Roman Smolensky |
Randomization and the Computational Power of Analytic and Algebraic Decision Trees. |
Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Felipe Cucker, Dima Grigoriev |
On the Power of Real Turing Machines Over Binary Inputs. |
SIAM J. Comput. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Anatol Slissenko |
Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane. |
AAECC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
Randomized Omega(n2) Lower Bound for Knapsack. |
STOC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
Randomized Omega(n2) Lower Bound for Knapsack |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Nicolai Vorobjov |
Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. |
Theor. Comput. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. |
Theor. Comput. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. |
Theor. Comput. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko |
Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. |
Fundam. Inform. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Testing Shift-Equivalence of Polynomials Using Quantum Machines. |
ISSAC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky |
A Lower Bound for Randomized Algebraic Decision Trees. |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | 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) |
1995 |
DBLP BibTeX RDF |
|
| 1 | 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) |
1995 |
DBLP BibTeX RDF |
|
| 1 | Dima Grigoriev, Michael F. Singer, Andrew Chi-Chih Yao |
On Computing Algebraic Functions Using Logarithms and Exponentials. |
SIAM J. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov |
Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. |
FOCS |
1995 |
DBLP DOI BibTeX RDF |
algebraic decision trees, n-dimensional convex polyhedron, naturally appearing polyhedra, computational geometry, lower bound, lower bounds, decision theory, polyhedron, membership testing |
| 1 | Dima Grigoriev, Yagati N. Lakshman |
Algorithms for Computing Sparse Shifts for Multivariate Polynomials. |
ISSAC |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Deviation Theorems for Solutions of Differential Equations and Applications to Lower Bounds on Parallel Complexity of Sigmoids. |
Theor. Comput. Sci. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Michael F. Singer |
Computational Complexity of Sparse Rational Interpolation. |
SIAM J. Comput. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Nicolai Vorobjov |
Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates |
FOCS |
1994 |
DBLP DOI BibTeX RDF |
complexity lower bounds, computation trees, elementary transcendental function gates, membership, arithmetic operations, algebraic functions, transcendental functions, convex polyhedron |
| 1 | Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov |
Lower bounds on testing membership to a polyhedron by algebraic decision trees. |
STOC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. |
AAECC |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko |
Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. |
ISSAC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] |
FOCS |
1991 |
DBLP DOI BibTeX RDF |
bounding ratio, arbitrary polynomials, approximation algorithm, finite fields, polynomial time algorithm, multivariate polynomials, zeros |
| 1 | Dima Grigoriev, Marek Karpinski |
Algorithms for Sparse Rational Interpolation. |
ISSAC |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators. |
J. Symb. Comput. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Michael F. Singer |
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. |
SIAM J. Comput. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski, Michael F. Singer |
Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents |
FOCS |
1990 |
DBLP DOI BibTeX RDF |
polynomial parallel time, sparse rational functions, polynomially bounded storage, interpolation, queries, sparse representation, black box |
| 1 | Dima Grigoriev |
Complexity of Irreducibility Testing for a System of Linear Ordinary Differential Equations. |
ISSAC |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
How to Test in Subexponential Time Whether Two Points Can Be Connected by a Curve in a Semialgebraic Set. |
ISSAC |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Nicolai Vorobjov |
Solving Systems of Polynomial Inequalities in Subexponential Time. |
J. Symb. Comput. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Complexity of Deciding Tarski Algebra. |
J. Symb. Comput. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev, Marek Karpinski |
The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) |
FOCS |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander L. Chistov, Dima Grigoriev |
Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. |
MFCS |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Additive Complexity in Directed Computations. |
Theor. Comput. Sci. |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Multiplicative Complexity of a Bilinear Form over a Commutative Ring. |
MFCS |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | Dima Grigoriev |
Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication. |
MFCS |
1978 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")