Group:Lunch Meeting
Title: Groups and Computation,A remark on one-wayness versus pseudorandomness
Speaker: Youming Qiao, Guang Yang
Time: 2011-10-13 12:00-2011-10-13 14:00
Venue: FIT 1-222


Speaker: Youming Qiao
Title: Groups and Computation

Abstract: Since the times of Turing, the interaction of group theory and the theory of computation has been a topic intriguing to both mathematicians and complexity theorists. In this talk I will give a historical account of the important ideas and results in this aspect, exhibiting e.g. Adian's undecidability results of problems in groups, Luks's algorithm for isomorphism test of graphs with bounded degree, and Babai and Shlomo's invention of Arthur-Merlin games. I will conclude the talk with a survey of recent results on group isomorphism problem, when groups are given as Cayley tables.

Speaker: Guang Yang
Title: A remark on one-wayness versus pseudorandomness

Abstract: Every pseudorandom generator is in particular a one-way function. If we consider only part of the output of a pseudorandom generator is it still one-way? Somewhat surprisingly the answer is no in a general setting formalizing the question. In particular, assuming the existence of a pseudorandom generator of any stretch and hardness, we construct a pseudorandom generator of the same stretch and hardness, where an O(n/logn)-large random projection of the output is not one-way. More generally, the same holds if we sample a linear operator and apply it on the output of such a pseudorandom generator G. Specifically, let n be the seed length, l(n)>n the output length of G and let M_R in {0,1}^{m(n) x l(n)}, m(n)=O(n/log n), be a linear operator sampled in polynomial time using randomness R. Then, f(x,R) = (M_R G(x), R) is not even weakly one-way. This formulation in particular rules out the application of universal families of hash functions and randomness extractors.

Joint work with Periklis Papakonstantinou