UCSB CS Theory Colloquium Series

Spring 2022

Friday, March 11th, 2pm, Phelps 2510 Speaker: Qipeng Liu (Simons) Title: Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering Abstract: In this talk, I will show possible speed-ups for solving lattice-related problems using quantum computers, including the following: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. One interesting parameter regime is to find a binary solution x for an over-determined linear equation system Ax = 0 in field F_3, in polynomial time. (*) Learning with errors (LWE) problem given LWE-like *quantum* samples with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. No classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. |