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].

Time

2023-06-05  14:00 - 15:00   

Speaker

Zeyong Li,  National University of Singapore

Room

Room 602, SIME, SUFE