摘要：Hitting set generator and pseudorandom generator have found wide application in derandomized algorithms and complexity theory. We present a construction of optimal hitting set generators through algebraic curves and bilinear map. There are two consequences of this result: (i) we obtain optimal punctured Reed-Muller codes; (ii) we provide a good class of pseudorandom generator.

报告人简介：邢朝平教授现任新加坡南洋理工大学数学系终身教授，2013荷兰Kloosterman讲席教授。现为权威期刊IEEE信息论会刊等5家国际期刊编委。曾在第五届亚洲数学家大会上做1小时报告，第三届华人数学家大会上做45分钟报告，第三届欧洲数学家大会上做45分钟报告。近年来在编码，密码，理论计算机顶级会议上发表多篇论文。