演讲人： Luca Trevisan Stanford University
时间： 2010-03-25 14:00-2010-03-25 15:00
地点：FIT楼1-222
内容：

We study time-space trade-offs in attacks against one-way functions and pseudorandom generators. Fiat and Naor show that for every function f:[N]- > [N] there is an algorithm that inverts f everywhere using (ignoring lower order factors) time, space and advice at most N^{3/4}.
We show that an algorithm using time, space and advice at most max { (epsilon*N)^{1/2} , epsilon^{5/4} * N^{3/4} } exists that inverts f on at least an epsilon fraction of inputs. A lower bound of (epsilon*N)^{1/2} also holds, making our result tight in the ``low end'' of small epsilon.
We also show that for every length-increasing generator G:[N]->[2N] there is a algorithm that achieves distinguishing probability epsilon between the output of G and the uniform distribution and that can be implemented in polynomial (in logN) time and with advice and space O(epsilon^2 * NlogN). Alternatively, it can be implemented as a circuit of size O(epsilon^2 * N). We prove a lower bound of ST > epsilon^2 * N where T is the time used by the algorithm and S is the amount of advice. We prove stronger lower bounds in the common random string model, for families of one-way permutations and of pseudorandom generators.
(Joint work with Anindya De and Madhur Tulsiani.)
 
 

个人简介:

Luca Trevisan is a professor of electrical engineering and computer science at U.C. Berkeley and a professor of computer science at Stanford. Luca received his PhD in 1997 from the University of Rome La Sapienza. Before moving to California in 2000, Luca was a post-doc at MIT and at DIMACS, and an assistant professor at Columbia University.
Luca's research is in theoretical computer science, and most of his work has been in two areas: (i) the study of randomness and pseudorandomness in computation and in combinatorics; and (ii) the theory of probabilistically checkable proofs and its relation to the approximability of combinatorial optimization problems.
Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians in Madrid.