Arrow Research search

Author name cluster

Dima Grigoriev

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
2 author rows

Possible papers

22

FLAP Journal 2017 Journal Article

Secure Multiparty Computation without One-way Functions.

  • Dima Grigoriev
  • Vladimir Shpilrain

We describe protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. One of the new inputs that we offer here is that, in contrast with other proposals, we conceal intermediate results of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. We also give a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we describe a secret sharing scheme where an advantage over Shamir’s and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer. In memory of Grigori Mints Part of this research was presented by the first author at the conference “Philosophy, Mathematics, Linguistics: Aspects of Interaction 2012” (PhML-2012), held on May 22–25, 2012 at the Euler International Mathematical Institute. ∗ Research was supported by the RSF grant 16-11-10075. † Research was partially supported by the NSF grant CNS-1117675 and by the ONR (Office of Naval Research) grant N000141512164.

PDF Details

FOCS Conference 1998 Conference Paper

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields

  • Dima Grigoriev
  • Alexander A. Razborov

A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f: D/sup n//spl rarr/F for subsets D/spl sub/F. In particular, we prove an exponential lower bound on the complexity of a depth 3 arithmetic circuit which computes the determinant or the permanent of a matrix considered as functions f: (F*)n/sup 2//spl rarr/F.

Details

FOCS Conference 1998 Conference Paper

Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs

  • Dima Grigoriev

We use the known linear lower bound for Tseitin's tautologies for establishing linear lower bounds on the degree of Nullstellensatz proofs (in the usual boolean setting) for explicitly constructed systems of polynomials of a constant (in our construction 6) degree. It holds over any field of characteristic distinct from 2. Previously, a linear lower bound was proved for an explicitly constructed system of polynomials of a logarithmic degree.

Details

FOCS Conference 1995 Conference Paper

Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees

  • Dima Grigoriev
  • Marek Karpinski
  • Nicolai N. Vorobjov Jr.

We introduce a new method of proving lower bounds on the depth of algebraic decision trees of degree d and apply it to prove a lower bound /spl Omega/(log N) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N>(nd)/sup /spl Omega//(n). This weakens considerably the restriction on N previously imposed by the authors and opens a possibility to apply the bound to some naturally appearing polyhedra.

Details

FOCS Conference 1994 Conference Paper

Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates

  • Dima Grigoriev
  • Nicolai N. Vorobjov Jr.

We consider computation trees which admit as gate functions along with the usual arithmetic operations also algebraic or transcendental functions like exp, log, sin, square root (defined in the relevant domains) or much more general, Pfaffian functions. A new method for proving lower bounds on the depth of these trees is developed which allows to prove a lower bound /spl Omega/(/spl radic/(log N)) for testing membership to a convex polyhedron with N facets of all dimensions, provided that N is large enough. This method differs essentially from the previous approaches adopted for algebraic computation trees. >

Details

FOCS Conference 1991 Conference Paper

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]

  • Dima Grigoriev
  • Marek Karpinski

The authors design the first polynomial time (for an arbitrary and fixed field GF(q)) ( in, delta )-approximation algorithm for the number of zeros of arbitrary polynomial f(x/sub 1/. .. x/sub n/) over GF(q). It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF(2) (like GF(3)), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x/sub 1/. .. ,x/sub n/) over GF(q) in the function of the number m of its terms. The bounding ratio is proved to be m/sup (q-1)/log/sup q/. >

Details

FOCS Conference 1990 Conference Paper

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents

  • Dima Grigoriev
  • Marek Karpinski
  • Michael F. Singer

The authors present the first algorithm for the (black box) interpolation of t-sparse, n-variate, rational functions without knowing bounds on exponents of their sparse representation, with the number of queries independent of exponents. In fact, the algorithm uses O(nt/sup t/) queries to the black box, and it can be implemented for a fixed t in a polynomially bounded storage (or polynomial parallel time). >

Details

FOCS Conference 1987 Conference Paper

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)

  • Dima Grigoriev
  • Marek Karpinski

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = nO(1)) are in the deterministic classes NC2 and NC3, respectively. We further design an NC3 algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(nk). The basic step was the development of a new symmetric functions method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3 n) parallel time and O(n3k+5. 5 · log n) processors. In the case of arbitrary bipartite graphs it yields an 'optimal' (up to the log n- factor) parallel time algorithm for enumerating all the perfect matchings in a graph. It entails also among other things an efficient NC3-algorithm for computing small (polynomially bounded) arithmetic permanents, and a sublinear parallel time algorithm for enumerating all the perfect matchings in graphs with permanents up to 2nε.

Details

MFCS Conference 1984 Invited Paper

Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields

  • Alexander L. Chistov
  • Dima Grigoriev

Abstract An algorithm is described producing for each formula of the first order theory of algebraically closed fields an equivalent free of quantifiers one. Denote by N a number of polynomials occuring in the formula, by d an upper bound on the degrees of polynomials, by n a number of variables, by a a number of quantifier alternations (in the prefix form). Then the algorithm works within the polynomial in the formula's size and in (Nd) n (2a+2) time. Up to now a bound (Nd) n o(n) was known ([5], [7], [15]).

Details

MFCS Conference 1981 Conference Paper

Multiplicative Complexity of a Bilinear Form over a Commutative Ring

  • Dima Grigoriev

Abstract We characterize the class of Noetherian commutative rings K such that the multiplicative complexity of a bilinear form over K coincides with its rank. The asymptotic behaviour of the multiplicative complexity of bilinear forms from one special class over the polynomial rings is described, and in particular it is shown that there is no finite upper bound for the difference between the multiplicative complexity of a bilinear form from this class and the rank of this form. The relationship between the multiplicative complexity of a bilinear form over a ring K and homological properties of the ring is explained.

Details