About

Noah Stephens-Davidowitz is an assistant professor in the Department of Computer Science at Cornell University. His research has primarily focused on the study of lattices, and he is also interested more broadly in theoretical computer science, cryptography, and geometry. He received his Ph.D. from New York University, advised by Professors Oded Regev and Yevgeniy Dodis. Before joining Cornell, he 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.

Research topics

• Mathematics
• Discrete mathematics
• Computer Science
• Combinatorics
• Mathematical analysis
• Artificial Intelligence
• Algorithm
• Geometry
• Physics

Selected publications

• Difficulties Constructing Lattices With Exponential Kissing Number From Codes

  IEEE Transactions on Information Theory · 2025-07-28

  articleSenior author

  In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-weight non-zero codewords and shortest non-zero lattice vectors. From these examples, we conclude that the main results in two works of Vlăduţ (Moscow J. Comb. Number Th., 2019 and Discrete Comput. Geom., 2021) on constructing lattices with exponential kissing number from error-correcting codes are invalid. A more recent preprint (arXiv, 2024) that Vlăduţ posted after an initial version of this work was made public is also invalid. Exhibiting a family of lattices with exponential kissing number therefore remains an open problem (as of July 2025).

  PublisherDOI

• Recursive lattice reduction—A framework for finding short lattice vectors

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapterSenior author

  We propose a new framework called recursive lattice reduction for finding short non-zero vectors in a lattice or for finding dense sublattices of a lattice. At a high level, the framework works by recursively searching for dense sublattices of dense sublattices (or their duals) with progressively lower rank. Eventually, the procedure encounters a recursive call on a lattice 𝓛 with relatively low rank k, at which point we can simply use a known algorithm to find a shortest non-zero vector in 𝓛.

  PublisherDOI

• A simple proof of a reverse Minkowski theorem for integral lattices

  Journal of Number Theory · 2025-07-21 · 1 citations

  articleSenior authorCorresponding
  PublisherDOI

• Guarding the Signal: Secure Messaging with Reverse Firewalls

  Lecture notes in computer science · 2025-01-01 · 1 citations

  book-chapter
  PublisherDOI

• The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions

  arXiv (Cornell University) · 2025-01-01

  preprintOpen accessSenior author

  We show a number of connections between two types of search problems: (1) the problem of finding an L-wise multicollision in the output of a function; and (2) the problem of finding two codewords in a code (or two vectors in a lattice) that are within distance d of each other. Specifically, we study these problems in the total regime, in which L and d are chosen so that such a solution is guaranteed to exist, though it might be hard to find. In more detail, we study the total search problem in which the input is a function 𝒞 : [A] → [B] (represented as a circuit) and the goal is to find L ≤ ⌈A/B⌉ distinct elements x_1,…, x_L ∈ A such that 𝒞(x_1) = ⋯ = 𝒞(x_L). The associated complexity classes Polynomial Multi-Pigeonhole Principle ((A,B)-PMPP^L) consist of all problems that reduce to this problem. We show close connections between (A,B)-PMPP^L and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding two distinct codewords or lattice points that are close to each other) are in (A,B)-PMPP^L, with a more-or-less smooth tradeoff between the distance d and the parameters A, B, and L. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes. Surprisingly, we also show that the computational problems associated with some bounds on the minimum distance of codes are actually hard for these classes (for codes represented by arbitrary circuits). In fact, we show that finding two vectors within a certain distance d is actually hard for the important (and well-studied) class PWPP = (B²,B)-PMPP² in essentially all parameter regimes for which an efficient algorithm is not known, so that our hardness results are essentially tight. In fact, for some d (depending on the block length, message length, and alphabet size), we obtain both hardness and containment. We therefore completely settle the complexity of this problem for such parameters and add coding problems to the short list of problems known to be complete for PWPP. We also study (A,B)-PMPP^L as an interesting family of complexity classes in its own right, and we uncover a rich structure. Specifically, we use recent techniques from the cryptographic literature on multicollision-resistant hash functions to (1) show inclusions of the form (A,B)-PMPP^L ⊆ (A',B')-PMPP^L' for certain non-trivial parameters; (2) black-box separations between such classes in different parameter regimes; and (3) a non-black-box proof that (A,B)-PMPP^L ∈ FP if (A',B')-PMPP^L' ∈ FP for yet another parameter regime. We also show that (A,B)-PMPP^L lies in the recently introduced complexity class Polynomial Long Choice for some parameters.

  PublisherOA PDFDOI

• Difficulties Constructing Lattices with Exponential Kissing Number from Codes

  arXiv (Cornell University) · 2024-10-22

  preprintOpen accessSenior author

  In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-weight non-zero codewords and shortest non-zero lattice vectors. From these examples, we conclude that the main results in two works of Vlăduţ (Moscow J. Comb. Number Th., 2019 and Discrete Comput. Geom., 2021) on constructing lattices with exponential kissing number from error-correcting codes are invalid. A more recent preprint (arXiv, 2024) that Vlăduţ posted after an initial version of this work was made public is also invalid. Exhibiting a family of lattices with exponential kissing number therefore remains an open problem (as of July 2025).

  PublisherOA PDFDOI

• More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More

  arXiv (Cornell University) · 2024-01-01

  preprintOpen accessSenior author

  We expand on recent exciting work of Debris-Alazard, Ducas, and van Woerden [Transactions on Information Theory, 2022], which introduced the notion of basis reduction for codes, in analogy with the extremely successful paradigm of basis reduction for lattices. We generalize DDvW's LLL algorithm and size-reduction algorithm from codes over $\mathbb{F}_2$ to codes over $\mathbb{F}_q$, and we further develop the theory of proper bases. We then show how to instantiate for codes the BKZ and slide-reduction algorithms, which are the two most important generalizations of the LLL algorithm for lattices. Perhaps most importantly, we show a new and very efficient basis-reduction algorithm for codes, called full backward reduction. This algorithm is quite specific to codes and seems to have no analogue in the lattice setting. We prove that this algorithm finds vectors as short as LLL does in the worst case (i.e., within the Griesmer bound) and does so in less time. We also provide both heuristic and empirical evidence that it outperforms LLL in practice, and we give a variant of the algorithm that provably outperforms LLL (in some sense) for random codes. Finally, we explore the promise and limitations of basis reduction for codes. In particular, we show upper and lower bounds on how ``good'' of a basis a code can have, and we show two additional illustrative algorithms that demonstrate some of the promise and the limitations of basis reduction for codes.

  PublisherOA PDFDOI

• Recursive lattice reduction -- A framework for finding short lattice vectors

  arXiv (Cornell University) · 2023-11-25

  preprintOpen accessSenior author

  We propose a recursive lattice reduction framework for finding short non-zero vectors or dense sublattices of a lattice. The framework works by recursively searching for dense sublattices of dense sublattices (or their duals) with progressively lower rank. When the procedure encounters a recursive call on a lattice $L$ with relatively low rank, we simply use a known algorithm to find a shortest non-zero vector in $L$. This new framework is complementary to basis reduction algorithms, which similarly work to reduce an $n$-dimensional lattice problem with some approximation factor $γ$ to a lower-dimensional exact lattice problem in some lower dimension $k$, with a tradeoff between $γ$, $n$, and $k$. Our framework provides an alternative and arguably simpler perspective. For example, our algorithms can be described at a high level without explicitly referencing any specific basis of the lattice, the Gram-Schmidt orthogonalization, or even projection (though, of course, concrete implementations of algorithms in this framework will likely make use of such things). We present a number of instantiations of our framework. Our main concrete result is an efficient reduction that matches the tradeoff achieved by the best-known basis reduction algorithms. This reduction also can be used to find dense sublattices with any rank $\ell$ satisfying $\min\{\ell,n-\ell\} \leq n-k+1$, using only an oracle for SVP in $k$ dimensions, with slightly better parameters than what was known using basis reduction. We also show a simple reduction with the same tradeoff for finding short vectors in quasipolynomial time, and a reduction from finding dense sublattices of a high-dimensional lattice to this problem in lower dimension. Finally, we present an automated search procedure that finds algorithms in this framework that (provably) achieve better approximations with fewer oracle calls.

  PublisherOA PDFDOI

• A simple proof of a reverse Minkowski theorem for integral lattices

  arXiv (Cornell University) · 2023-06-06 · 2 citations

  preprintOpen accessSenior author

  We prove that for any integral lattice $\mathcal{L} \subset \mathbb{R}^n$ (that is, a lattice $\mathcal{L}$ such that the inner product $\langle \mathbf{y}_1,\mathbf{y}_2 \rangle$ is an integer for all $\mathbf{y}_1, \mathbf{y}_2 \in \mathcal{L}$) and any positive integer $k$, \[ |\{ \mathbf{y} \in \mathcal{L} \ : \ \|\mathbf{y}\|^2 = k\}| \leq 2 \binom{n+2k-2}{2k-1} \; , \] giving a nearly tight reverse Minkowski theorem for integral lattices.

  PublisherOA PDFDOI

• A reverse Minkowski theorem

  Annals of Mathematics · 2023-12-30 · 8 citations

  articleSenior author

  We prove a conjecture due to Dadush, showing that if $\mathcal{L} \subset \mathbb{R}^n$ is a lattice such that $\det(\mathcal{L}') \ge 1$ for all sublattices $\mathcal{L}' \subseteq \mathcal{L}$, then $\sum_{\mathbf{y}\in \mathcal{L}} e^{-\pi t^2 \|\mathbf{y} \|^2} \le 3/2$, where $t := 10(\log n + 2)$. From this we derive bounds on the number of short lattice vectors, which can be viewed as a partial converse to Minkowski's celebrated first theorem. We also derive a bound on the covering radius.

  PublisherDOI

Recent grants

• Collaborative Research: CISE-ANR: CNS Core: Small: Cryptographic Hardness of Module Lattices

  NSF · $250k · 2021–2024

Frequent coauthors

• Divesh Aggarwal

  27 shared

• Oded Regev

  New York University

  22 shared

• Daniel Dadush

  Centrum Wiskunde & Informatica

  14 shared

• Huck Bennett

  14 shared

• Alexander Golovnev

  13 shared

• Zeyong Li

  Affiliated Hospital of North Sichuan Medical College

  8 shared

• Siyao Guo

  Sun Yat-sen University

  7 shared

• Vinod Vaikuntanathan

  7 shared

Awards & honors

• Packard Fellowship in Science and Engineering