About

I am an assistant professor in Cornell's computer science department, and a member of the applied math field and the mathematics field. My research to date has focused primarily on the study of lattices. I am also interested more broadly in theoretical computer science, cryptography, and geometry.

I received my PhD from NYU, advised by Professors Oded Regev and Yevgeniy Dodis. Before coming to Cornell, I was a fellow at the Simons Institute in Berkeley, as part of the program Lattices: Algorithms, Complexity, and Cryptography, a postdoctoral researcher at MIT's computer science department, supervised by Vinod Vaikunthanathan, and a postdoc at Princeton’s computer science department and visiting researcher at the Institute for Advanced Study’s math department---both as part of the Simons Collaboration on Algorithms and Geometry.

My email is noahsd@gmail.com. My office is Gates 321.

Papers


BibBase stephens-davidowitz, n
generated by bibbase.org
  2025 (1)
Recursive lattice reduction—A framework for finding short lattice vectors . Divesh Aggarwal; Thomas Espitau; Spencer Peters; and Noah Stephens-Davidowitz. In SOSA, 2025.
Recursive lattice reduction—A framework for finding short lattice vectors  [link]Paper   link   bibtex   9 downloads  
  2024 (3)
More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more. Surendra Ghentiyala; and Noah Stephens-Davidowitz. In APPROX, 2024.
More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more [link]Paper   link   bibtex   27 downloads  
The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions. Huck Bennett; Surendra Ghentiyala; and Noah Stephens-Davidowitz. 2024.
The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions [link]Paper   link   bibtex   2 downloads  
A reverse Minkowski theorem. Oded Regev; and Noah Stephens-Davidowitz. Annals of Mathematics. 2024. A preliminary version appeared in STOC 2017.
A reverse Minkowski theorem [link]Paper   A reverse Minkowski theorem [link] tcs+ talk   A reverse Minkowski theorem [link] ias talk   A reverse Minkowski theorem [link] bourbaki seminar   link   bibtex   107 downloads  
  2023 (6)
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity. Eldon Chung; Alexander Golovnev; Zeyong Li; Maciej Obremski; Sidhant Saraogi; and Noah Stephens-Davidowitz. 2023.
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity [link]Paper   link   bibtex   21 downloads  
A simple proof of a reverse Minkowski theorem for integral lattices. Oded Regev; and Noah Stephens-Davidowitz. 2023.
A simple proof of a reverse Minkowski theorem for integral lattices [link]Paper   link   bibtex   64 downloads  
Lattice problems beyond polynomial time. Divesh Aggarwal; Huck Bennett; Zvika Brakerski; Alexander Golovnev; Rajendra Kumar; Zeyong Li; Spencer Peters; Noah Stephens-Davidowitz; and Vinod Vaikuntanathan. In STOC, 2023.
Lattice problems beyond polynomial time [link]Paper   link   bibtex   60 downloads  
Revisiting time-space tradeoffs for function inversion. Alexander Golovnev; Siyao Guo; Spencer Peters; and Noah Stephens-Davidowitz. In CRYPTO, 2023.
Revisiting time-space tradeoffs for function inversion [link]Paper   link   bibtex   6 downloads  
Just how hard are rotations of $ℤ^n$? Algorithms and cryptography with the simplest lattice. Huck Bennett; Atul Ganju; Pura Peetathawatchai; and Noah Stephens-Davidowitz. In Eurocrypt, 2023.
Just how hard are rotations of $ℤ^n$? Algorithms and cryptography with the simplest lattice [link]Paper   link   bibtex   20 downloads  
On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization. Alexander Golovnev; Siyao Guo; Spencer Peters; and Noah Stephens-Davidowitz. In APPROX, 2023.
On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization [link]Paper   link   bibtex   6 downloads  
  2022 (2)
A tight reverse Minkowski inequality for the Epstein zeta function. Yael Eisenberg; Oded Regev; and Noah Stephens-Davidowitz. Proceedings of the AMS. 2022.
A tight reverse Minkowski inequality for the Epstein zeta function [link]Paper   link   bibtex   8 downloads  
On seedless PRNGs and premature next. Sandro Coretti; Yevgeniy Dodis; Harish Karthikeyan; Noah Stephens-Davidowitz; and Stefano Tessaro. In ITC, 2022.
On seedless PRNGs and premature next [link]Paper   link   bibtex   5 downloads  
  2021 (6)
No time to hash: On super efficient entropy accumulation. Yevgeniy Dodis; Siyao Guo; Noah Stephens-Davidowitz; and Zhiye Xie. In CRYPTO, 2021.
No time to hash: On super efficient entropy accumulation [link]Paper   link   bibtex   4 downloads  
Online linear extractors for independent sources. Yevgeniy Dodis; Siyao Guo; Noah Stephens-Davidowitz; and Zhiye Xie. In ITC, 2021.
Online linear extractors for independent sources [link]Paper   link   bibtex  
On the hardness of average-case $k$-SUM. Zvika Brakerski; Noah Stephens-Davidowitz; and Vinod Vaikuntanathan. In RANDOM, 2021.
On the hardness of average-case $k$-SUM [link]Paper   link   bibtex   3 downloads  
Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else). Divesh Aggarwal; Huck Bennett; Alexander Golovnev; and Noah Stephens-Davidowitz. In SODA, 2021.
Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else) [link]Paper   Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else) [link] simons blog post   link   bibtex   20 downloads  
Dimension-preserving reductions between SVP and CVP in different $p$-norms. Divesh Aggarwal; Yanlin Chen; Rajendra Kumar; Zeyong Li; and Noah Stephens-Davidowitz. In SODA, 2021.
Dimension-preserving reductions between SVP and CVP in different $p$-norms [link]Paper   link   bibtex   9 downloads  
A $2^{n/2}$-time algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP. Divesh Aggarwal; Zeyong Li; and Noah Stephens-Davidowitz. In Eurocrypt, 2021.
A $2^{n/2}$-time algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP [link]Paper   link   bibtex   7 downloads  
  2020 (3)
Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP. Tamalika Mukherjee; and Noah Stephens-Davidowitz. In CRYPTO, 2020.
Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP [link]Paper   link   bibtex   11 downloads  
Extractor lower bounds, revisited. Divesh Aggarwal; Siyao Guo; Maciej Obremski; João Ribeiro; and Noah Stephens-Davidowitz. In RANDOM, 2020.
Extractor lower bounds, revisited [link]Paper   link   bibtex   3 downloads  
Slide reduction, revisited—Filling the gaps in SVP approximation. Divesh Aggarwal; Jianwei Li; Phong Q. Nguyen; and Noah Stephens-Davidowitz. In CRYPTO, 2020.
Slide reduction, revisited—Filling the gaps in SVP approximation [link]Paper   link   bibtex   7 downloads  
  2019 (4)
An improved constant in Banaszczyk's transference theorem. Divesh Aggarwal; and Noah Stephens-Davidowitz. 2019.
An improved constant in Banaszczyk's transference theorem [link]Paper   link   bibtex   43 downloads  
Kissing numbers and transference theorems from generalized tail bounds. Stephen D. Miller; and Noah Stephens-Davidowitz. SIDMA, 33(3). 2019.
Kissing numbers and transference theorems from generalized tail bounds [link]Paper   link   bibtex   55 downloads  
SETH-hardness of coding problems. Noah Stephens-Davidowitz; and Vinod Vaikuntanathan. In FOCS, 2019.
SETH-hardness of coding problems [link]Paper   link   bibtex   110 downloads  
A time-distance trade-off for GDD with preprocessing—Instantiating the DLW heuristic. Noah Stephens-Davidowitz. In CCC, 2019.
A time-distance trade-off for GDD with preprocessing—Instantiating the DLW heuristic [link]Paper   link   bibtex   24 downloads  
  2018 (3)
(Gap/S)ETH Hardness of SVP. Divesh Aggarwal; and Noah Stephens-Davidowitz. In STOC, 2018.
(Gap/S)ETH Hardness of SVP [link]Paper   link   bibtex   84 downloads  
Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP). Divesh Aggarwal; and Noah Stephens-Davidowitz. In SOSA, 2018.
Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP) [link]Paper   link   bibtex   72 downloads  
New (and old) proof systems for lattice problems. Navid Alamati; Chris Peikert; and Noah Stephens-Davidowitz. In PKC, 2018.
New (and old) proof systems for lattice problems [link]Paper   link   bibtex   19 downloads  
  2017 (5)
An inequality for Gaussians on lattices. Oded Regev; and Noah Stephens-Davidowitz. SIDMA, 31(2). 2017.
An inequality for Gaussians on lattices [link]Paper   link   bibtex   50 downloads  
On the quantitative hardness of CVP. Huck Bennett; Alexander Golovnev; and Noah Stephens-Davidowitz. In FOCS, 2017.
On the quantitative hardness of CVP [link]Paper   On the quantitative hardness of CVP [link] princeton talk   link   bibtex   71 downloads  
Pseudorandomness of Ring-LWE for any ring and modulus. Chris Peikert; Oded Regev; and Noah Stephens-Davidowitz. In STOC, 2017.
Pseudorandomness of Ring-LWE for any ring and modulus [link]Paper   link   bibtex   68 downloads  
On the Gaussian measure over lattices. Noah Stephens-Davidowitz. Ph.D. Thesis, New York University, 2017.
link   bibtex  
Implementing BP-obfuscation using graph-induced encoding. Shai Halevi; Tzipora Halevi; Victor Shoup; and Noah Stephens-Davidowitz. In CCS, 2017.
Implementing BP-obfuscation using graph-induced encoding [link]Paper   link   bibtex   8 downloads  
  2016 (4)
Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. Noah Stephens-Davidowitz. In APPROX, 2016.
Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one [link]Paper   link   bibtex   47 downloads  
On the Lattice Distortion Problem. Huck Bennett; Daniel Dadush; and Noah Stephens-Davidowitz. In ESA, 2016.
On the Lattice Distortion Problem [link]Paper   link   bibtex   16 downloads  
Discrete Gaussian sampling reduces to CVP and SVP. Noah Stephens-Davidowitz. In SODA, 2016.
Discrete Gaussian sampling reduces to CVP and SVP [link]Paper   link   bibtex   110 downloads  
Message transmission with Reverse Firewalls–secure communication on corrupted machines. Yevgeniy Dodis; Ilya Mironov; and Noah Stephens-Davidowitz. In CRYPTO, 2016.
Message transmission with Reverse Firewalls–secure communication on corrupted machines [link]Paper   Message transmission with Reverse Firewalls–secure communication on corrupted machines [link] crypto talk   link   bibtex   16 downloads  
  2015 (4)
Solving the Closest Vector Problem in $2^n$ time–The discrete Gaussian strikes again!. Divesh Aggarwal; Daniel Dadush; and Noah Stephens-Davidowitz. In FOCS, 2015.
Solving the Closest Vector Problem in $2^n$ time–The discrete Gaussian strikes again! [link]Paper   link   bibtex   19 downloads  
Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling. Divesh Aggarwal; Daniel Dadush; Oded Regev; and Noah Stephens-Davidowitz. In STOC, 2015.
Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling [link]Paper   Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling [link] simons talk   link   bibtex   50 downloads  
Dimension-preserving reductions between lattice problems. Noah Stephens-Davidowitz. 2015.
Dimension-preserving reductions between lattice problems [pdf]Paper   link   bibtex   119 downloads  
Cryptographic Reverse Firewalls. Ilya Mironov; and Noah Stephens-Davidowitz. In Eurocrypt, 2015.
Cryptographic Reverse Firewalls [link]Paper   Cryptographic Reverse Firewalls [pdf] slides   link   bibtex   37 downloads  
  2014 (2)
On the Closest Vector Problem with a distance guarantee. Daniel Dadush; Oded Regev; and Noah Stephens-Davidowitz. In CCC, 2014.
On the Closest Vector Problem with a distance guarantee [link]Paper   link   bibtex   60 downloads  
How to eat your entropy and have it too – optimal recovery strategies for compromised RNGs. Yevgeniy Dodis; Adi Shamir; Noah Stephens-Davidowitz; and Daniel Wichs. In CRYPTO, 2014.
How to eat your entropy and have it too – optimal recovery strategies for compromised RNGs [link]Paper   How to eat your entropy and have it too – optimal recovery strategies for compromised RNGs [link] crypto talk   link   bibtex   18 downloads  
  2007 (2)
The Cyclic Sieving Phenomenon on the Alternating Sign Matrices. Noah Stephens-Davidowitz; and Alex Cloninger. 2007.
The Cyclic Sieving Phenomenon on the Alternating Sign Matrices [pdf]Paper   link   bibtex   31 downloads  
On link patterns and Alternating Sign Matrices. Fraser Chiu Kim Hong; Alex Cloninger; and Noah Stephens-Davidowitz. 2007.
On link patterns and Alternating Sign Matrices [pdf]Paper   link   bibtex   17 downloads  

Selected Talks

(A much more complete list of talks is available in my CV.)

Advising

I am fortunate to advise three wonderful PhD students: Yael Eisenberg, Spencer Peters, and Surendra Ghentiyala.

Other