Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Dima Grigoriev:

TR06-046 | 1st April 2006
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

A Complete Public-Key Cryptosystem

Comments: 1

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

TR05-076 | 2nd July 2005
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

Time hierarchies for cryptographic function inversion with advice

We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
In particular, we prove that if there is a strongly
one-way function, then for any k and for any polynomial p,
there is a function f computable in linear time
with one ... more >>>

TR02-042 | 7th June 2002
Dima Grigoriev

Public-key cryptography and invariant theory

Public-key crypto
Contact: dima@maths.univ-rennes1.fr
Author: Dima Grigoriev
Title: Public-key cryptography and invariant theory
Abstract: Public-key cryptosystems are suggested based on invariants of group

more >>>

TR01-103 | 14th December 2001
Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

Complexity of semi-algebraic proofs

Revisions: 3

It is a known approach to translate propositional formulas into
systems of polynomial inequalities and to consider proof systems
for the latter ones. The well-studied proof systems of this kind
are the Cutting Planes proof system (CP) utilizing linear
inequalities and the Lovasz-Schrijver calculi (LS) utilizing
quadratic ... more >>>

TR01-011 | 21st January 2001
Dima Grigoriev, Edward Hirsch

Algebraic proof systems over formulas

We introduce two algebraic propositional proof systems F-NS
and F-PC. The main difference of our systems from (customary)
Nullstellensatz and Polynomial Calculus is that the polynomials
are represented as arbitrary formulas (rather than sums of
monomials). Short proofs of Tseitin's tautologies in the
constant-depth version of F-NS provide ... more >>>

TR96-058 | 25th November 1996
Dima Grigoriev, Marek Karpinski

Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the
general model of \emph{randomized computation trees} solving
the \emph{Knapsack Problem}, and more generally \emph{Restricted
Integer Programming}. This is the \emph{first nontrivial} lower
bound proven for this model of computation. The method of the ... more >>>

TR95-063 | 19th December 1995
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

A Lower Bound for Randomized Algebraic Decision Trees

We extend the lower bounds on the depth of algebraic decision trees
to the case of {\em randomized} algebraic decision trees (with
two-sided error) for languages being finite unions of hyperplanes
and the intersections of halfspaces, solving a long standing open
problem. As an application, among ... more >>>

TR95-057 | 24th November 1995
Dima Grigoriev, Marek Karpinski, A. C. Yao

An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

We prove an exponential lower bound on the size of any
fixed-degree algebraic decision tree for solving MAX, the
problem of finding the maximum of $n$ real numbers. This
complements the $n-1$ lower bound of Rabin \cite{R72} on
the depth of ... more >>>

ISSN 1433-8092 | Imprint