^May June – 2007 ^July

This talk addresses one of the most the most fundamental tasks in Cryptography, that of constructing pseudorandom generators from one-way functions. The seminal paper of Hastad et al. (known as HILL), proved that these notions are equivalent. However, the reduction is not nearly as security preserving as one may desire. In this context, we revisit a technique that we call the Randomized Iterate, introduced by Goldreich et al. In the talk I will introduce the randomized iterate and survey its recent applications. Our results simplify and strengthen the basic technique and achieve constructions with improved security of pseudorandom generators from regular one-way functions as well as general one-way functions. I will focus on another result: a new construction of a pseudorandom generator from any exponentially hard one-way function that gains substantial improvement in both security and efficiency.

Joint work with Iftach Haitner and Omer Reingold.

Metric embeddings has been a useful tool in designing approximation algorithms in the last decade. One of the basic paradigm in which it is employed is as follows: Given a hard optimization problem over metric data $X$, first embed $f:X \rightarrow H$, and then solve the problem over $f(X)$, assuming that H is a "nice" metric space to optimize over. One such a successful approach is "probabilistic embedding into trees" due to Alon, Karp, Peleg, West, and Bartal. This metric embedding technique is useful for minimization problems over distances in which the optimized function is linear, and (relatively) easy to solve on trees.

In this talk, I will describe a strengthening of the probabilistic embedding, that enable reducing a class of NONLINEAR problems (mainly nonlinear clustering problems) to trees.

Based on a joint work with Assaf Naor