Login with HarvardKey to view all events.

# Hardness of Bounded Distance Decoding on Lattice in l_p Norms

This is a past event.

Monday, October 19, 2020 1:45pm to 2:45pm

## Event Dates

Monday, October 19, 2020 1:45pm to 2:45pm

Virtual Event
Compared to prior work on the hardness of BDD_{p,\alpha} by Liu, Lyubashevsky, and Micciancio (APPROX-RANDOM 2008), our results improve the values of \alpha for which the problem is known to be NP-hard for all p > p_1 \approx 4.2773, and give the very first fine-grained hardness for BDD (in any norm). Our reductions rely on a special family of locally dense'' lattices in l_p norms, which we construct by modifying the integer-lattice sparsification technique of Aggarwal and Stephens-Davidowitz (STOC 2018).