research
∙
11/21/2022
Lattice Problems Beyond Polynomial Time
We study the complexity of lattice problems in a world where algorithms,...
share
research
∙
11/08/2022
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms, and of the Subset Sum Problem!
Recent work [BGS17,ABGS19] has shown SETH hardness of some constant fact...
research
∙
11/07/2021
Extractors: Low Entropy Requirements Colliding With Non-Malleability
The known constructions of negligible error (non-malleable) two-source e...
research
∙
06/05/2021
Quantum Measurement Adversary
Multi-source-extractors are functions that extract uniform randomness fr...
research
∙
04/14/2021
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms
We show a number of reductions between the Shortest Vector Problem and t...
research
∙
07/19/2020
A 2^n/2-Time Algorithm for √(n)-SVP and √(n)-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
We show a 2^n/2+o(n)-time algorithm that finds a (non-zero) vector in a ...
research
∙
05/24/2020
A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices
Blömer and Seifert showed that 𝖲𝖨𝖵𝖯_2 is NP-hard to approximate by givin...
research
∙
02/19/2020
Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
The most important computational problem on lattices is the Shortest Vec...
research
∙
11/06/2019
Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else)
We show that the Closest Vector Problem in the ℓ_p norm (CVP_p) cannot b...
research
∙
08/10/2019
Slide Reduction, Revisited---Filling the Gaps in SVP Approximation
We show how to generalize Gama and Nguyen's slide reduction algorithm [S...
research
∙
01/08/2018
Faster algorithms for SVP and CVP in the ℓ_∞ norm
Blomer and Naewe[BN09] modified the randomized sieving algorithm of Ajta...
research
∙
12/04/2017