CSE 254 Handout Nearest Neighbor Preserving Embeddings 1 Nearest Neighbor Search (2008)
Paper Piotr Indyk, Assaf Naor, Konstantin Pervyshev
Problem 1 (The nearest neighbor problem). Given a set X ⊂ R n, build a data structure which given any query x ∈ R n, quickly reports the point x ′ in X that is (approximately) closest to x....
Mathematics and Mechanics Department, (2008)
Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev
Abstract. 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...
Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev, Danny Harnik, Joe Kilian, Moni Naor, ...
After we published our ECCC report, we were made aware about a recent work of Harnik et al. [1] that predates ours. Although the construction in our report is very similar to the construction...
A Generic Time Hierarchy for Semantic Models With One Bit of Advice (2006)
Van Melkebeek, Dieter, Pervyshev, Konstantin
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...
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 � ZPTime[n b]/1. The technique introduced in this...
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 � ZPTime[n b]/1. The technique introduced in this...
A Generic Time Hierarchy for Semantic Models With One Bit of Advice (2005)
Dieter Melkebeek, Konstantin Pervyshev
We show that for any reasonable semantic model of computation and for any positive integer a and rationals 1 ≤ c < d, there exists a language computable in time n d with a bits of advice but not...
A Generic Time Hierarchy for Semantic Models With One Bit of Advice (2005)
Dieter Melkebeek, Konstantin Pervyshev
We show that for any reasonable semantic model of computation and for any positive integer a and rationals 1 ≤ c < d, there exists a language computable in time n d with a bits of advice but not...