Time：Monday, June 5, 14:00--15:00
Venue: Room 602, ITCS, SIME
1. 主讲人介绍 Speaker
Zeyong Li is a third-year PhD student from Centre for Quantum Technologies, National University of Singapore, advised by Prof. Divesh Aggarwal.
His research interest lies in, broadly speaking, theoretical computer science, slightly biased towards complexity /hardness related stuff. Currently he works mostly on hardness of Lattice problems (lower bounds and algorithms, etc).
2. 讲座介绍 Introduction
Title: Lattice Problems beyond Polynomial Time
Abstract: Consider a world where algorithms, reductions, and protocols run in superpolynomial time, how would the complexity landscape for lattice problems look like? We revisit four foundational results and show that when the running time for the reductions/protocols is 2^{eps n}, the approximation factor improves by a factor of roughtly sqrt(n/log n).
In this talk, we will see a simple and arguably elegant coMA protocol that decides O(1)-CVP when given 2^{eps n} verification time and message size. This can be seen as a combination of the coAM protocol from [GG00] and the coNP protocol from [AR05].
