Noah Stephens-Davidowitz
Contact
I am an assistant professor in Cornell's computer science department. My research to date has focused on the study of lattices and using the tools of theoretical computer science to answer fundamental questions about the security of widely deployed real-world cryptography, particularly post-quantum lattice-based cryptography. 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 (at) gmail (dot) com.
Publications
Fine-grained hardness of CVP(P)- -- Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, NSD
SODA, 2021
Dimension-preserving reductions between SVP and CVP in different p-norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, NSD
SODA, 2021
Divesh Aggarwal, Zeyong Li, NSD
Eurocrypt, 2021
On the hardness of average-case $k$-SUM
Zvika Brakerski, Noah {Stephens-Davidowitz}, Vinod Vaikuntanathan
RANDOM, 2021
No time to hash: On superefficient entropy accumulation
Yevgeniy Dodis, Siyao Guo, Noah {Stephens-Davidowitz}, Zhiye Xie
CRYPTO, 2021
Online linear extractors for independent sources
Yevgeniy Dodis, Siyao Guo, Noah {Stephens-Davidowitz}, Zhiye Xie
ITC, 2021
Extractor lower bounds, revisited
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Jo\~ao Ribeiro, Noah {Stephens-Davidowitz}
RANDOM, 2020
Slide reduction, revisited---Filling the gaps in SVP approximation
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah {Stephens-Davidowitz}
CRYPTO, 2020
Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP
Tamalika Mukherjee, Noah {Stephens-Davidowitz}
CRYPTO, 2020
An improved constant in {Banaszczyk}'s transference theorem
Divesh Aggarwal, Noah {Stephens-Davidowitz}
2019
Kissing numbers and transference theorems from generalized tail bounds
Stephen D. Miller, Noah {Stephens-Davidowitz}
SIDMA, vol. 33, 2019
A time-distance trade-off for GDD with preprocessing--Instantiating the DLW heuristic
Noah {Stephens-Davidowitz}
CCC, 2019
Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP)
Divesh Aggarwal, Noah {Stephens-Davidowitz}
SOSA, 2018
New (and old) proof systems for lattice problems
Navid Alamati, Chris Peikert, Noah {Stephens-Davidowitz}
PKC, 2018
On the quantitative hardness of CVP
Huck Bennett, Alexander Golovnev, Noah {Stephens-Davidowitz}
FOCS, 2017
Implementing BP-Obfuscation using Graph-Induced Encoding
Shai Halevi, Tzipora Halevi, Victor Shoup, Noah {Stephens-Davidowitz}
CCS, 2017
Pseudorandomness of Ring-LWE for any ring and modulus
Chris Peikert, Oded Regev, Noah {Stephens-Davidowitz}
STOC, 2017
Message transmission with Reverse Firewalls--secure communication on corrupted machines
Yevgeniy Dodis, Ilya Mironov, Noah {Stephens-Davidowitz}
CRYPTO, 2016
Noah {Stephens-Davidowitz}
APPROX, 2016
Solving the Shortest Vector Problem in $2^n$ time via Discrete Gaussian Sampling
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah {Stephens-Davidowitz}
STOC, 2015
Solving the Closest Vector Problem in $2^n$ time--The discrete Gaussian strikes again!
Divesh Aggarwal, Daniel Dadush, Noah {Stephens-Davidowitz}
FOCS, 2015
On the Closest Vector Problem with a distance guarantee
Daniel Dadush, Oded Regev, Noah {Stephens-Davidowitz}
CCC, 2014
How to eat your entropy and have it too -- optimal recovery strategies for compromised RNGs
Yevgeniy Dodis, Adi Shamir, Noah {Stephens-Davidowitz}, Daniel Wichs
CRYPTO, 2014
On link patterns and Alternating Sign Matrices
Fraser Chiu Kim Hong, Alex Cloninger, Noah {Stephens-Davidowitz}
2007
The Cyclic Sieving Phenomenon on the Alternating Sign Matrices
Noah {Stephens-Davidowitz}, Alex Cloninger
2007