Publications

Found 10 results
Author Title Type [ Year(Asc)]
Filters: Author is Dima Yu. Grigoriev  [Clear All Filters]
1996
Grigoriev, D. Yu., & Karpinski M. (1996).  Randomized ?(n^2) Lower Bound for Knapsack.
1995
Grigoriev, D. Yu., Karpinski M., & Yao A. C. (1995).  An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX.
Grigoriev, D. Yu., Karpinski M., der Heide F. Meyer auf, & Smolensky R. (1995).  A Lower Bound for Randomized Algebraic Decision Trees.
1993
Grigoriev, D. Yu., & Karpinski M. (1993).  Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Decision Trees.
Grigoriev, D. Yu., Karpinski M., & Vorobjov N. (1993).  Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees.
1991
Grigoriev, D. Yu., & Karpinski M. (1991).  Algorithms for Sparse Rational Interpolation.
Grigoriev, D. Yu., & Karpinski M. (1991).  An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q].
Grigoriev, D. Yu., Karpinski M., & Singer M. F. (1991).  Computational Complexity of Sparse Rational Interpolation.
Grigoriev, D. Yu., Karpinski M., & Odlyzko A. M. (1991).  Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis.
1990
Grigoriev, D. Yu., Karpinski M., & Singer M. F. (1990).  Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents.