Noah Stephens-Davidowitz
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 4 in the filters
on a stage with
never shared a talk
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Some Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms | Quantum and Lattices Joint Reunion Workshop | 2022-06-13 |
Shows that for large constant approximation factors lattice problems in any Lp norm run in essentially the same time as in L2, giving a 2^{0.8n} algorithm for… | ||
| A Reverse Minkowski Theorem | Lattices: Geometry, Algorithms and Hardness 2020 | 2020-02-18 |
Proves a precise reverse Minkowski: local → sublattice density statement: if every sublattice has det ≥1 then any ball has at most 2^{O(n)} Gaussian mass (and… | ||
| Algorithms for Lattice Problems | Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020 | 2020-01-21 |
Survey of concrete SVP algorithms and their costs: classic sieving is implemented and practical but lacks proofs; a provable 2^{n} provable sieving method via… | ||
| Complexity of Lattice Problems | Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020 | 2020-01-21 |
Defines precise reductions and runtimes: SVP reduces to CVP by doubling one basis coordinate, and CVP is NP‑hard via a subset‑sum basis construction that makes… | ||
| Solving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-Davidowitz | The Mathematics of Modern Cryptography | 2015-07-06 |
Randomized exact-SVP algorithm runs in 2^n time by starting with ~2^n samples from the discrete Gaussian (via GPV), repeatedly pairing vectors grouped by… | ||
| nothing matches | ||