All reports by Author Konstantin Pervyshev:

__
TR06-131
| 6th October 2006
__

Konstantin Pervyshev#### On Heuristic Time Hierarchies

__
TR06-046
| 1st April 2006
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### A Complete Public-Key Cryptosystem

Comments: 1

__
TR05-111
| 3rd October 2005
__

Dieter van Melkebeek, Konstantin Pervyshev#### A Generic Time Hierarchy for Semantic Models With One Bit of Advice

__
TR05-076
| 2nd July 2005
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### Time hierarchies for cryptographic function inversion with advice

__
TR05-054
| 19th May 2005
__

Konstantin Pervyshev#### Time Hierarchies for Computations with a Bit of Advice

Konstantin Pervyshev

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

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 >>>

Dieter van Melkebeek, Konstantin Pervyshev

We show that for any reasonable semantic model of computation and for

any positive integer $a$ and rationals $1 \leq c < d$, there exists a language

computable in time $n^d$ with $a$ bits of advice but not in time $n^c$

with $a$ bits of advice. A semantic ...
more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

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 >>>

Konstantin Pervyshev

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>