default search action
Noah Stephens-Davidowitz
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c33]Surendra Ghentiyala, Noah Stephens-Davidowitz:
More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More. APPROX/RANDOM 2024: 19:1-19:22 - [i37]Surendra Ghentiyala, Noah Stephens-Davidowitz:
More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more. CoRR abs/2408.08507 (2024) - [i36]Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
Difficulties Constructing Lattices with Exponential Kissing Number from Codes. CoRR abs/2410.16660 (2024) - [i35]Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz:
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c32]Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz:
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. APPROX/RANDOM 2023: 10:1-10:20 - [c31]Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz:
Revisiting Time-Space Tradeoffs for Function Inversion. CRYPTO (2) 2023: 453-481 - [c30]Huck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-Davidowitz:
Just How Hard Are Rotations of $\mathbb {Z}^n$? Algorithms and Cryptography with the Simplest Lattice. EUROCRYPT (5) 2023: 252-281 - [c29]Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
Lattice Problems beyond Polynomial Time. STOC 2023: 1516-1526 - [i34]Divesh Aggarwal, Thomas Espitau, Spencer Peters, Noah Stephens-Davidowitz:
Recursive lattice reduction - A framework for finding short lattice vectors. CoRR abs/2311.15064 (2023) - [i33]Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz:
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c28]Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan
, Noah Stephens-Davidowitz, Stefano Tessaro:
On Seedless PRNGs and Premature Next. ITC 2022: 9:1-9:20 - [i32]Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
Lattice Problems Beyond Polynomial Time. CoRR abs/2211.11693 (2022) - [i31]Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz:
Revisiting Time-Space Tradeoffs for Function Inversion. Electron. Colloquium Comput. Complex. TR22 (2022) - [i30]Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, Stefano Tessaro:
On Seedless PRNGs and Premature Next. IACR Cryptol. ePrint Arch. 2022: 558 (2022) - 2021
- [c27]Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
On the Hardness of Average-Case k-SUM. APPROX-RANDOM 2021: 29:1-29:19 - [c26]Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie:
Online Linear Extractors for Independent Sources. ITC 2021: 14:1-14:14 - [c25]Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie:
No Time to Hash: On Super-Efficient Entropy Accumulation. CRYPTO (4) 2021: 548-576 - [c24]Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz:
A 2n/2-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP. EUROCRYPT (1) 2021: 467-497 - [c23]Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). SODA 2021: 1816-1835 - [c22]Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms. SODA 2021: 2444-2462 - [i29]Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz:
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms. CoRR abs/2104.06576 (2021) - [i28]Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz:
On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization. Electron. Colloquium Comput. Complex. TR21 (2021) - [i27]Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie:
No Time to Hash: On Superefficient Entropy Accumulation. IACR Cryptol. ePrint Arch. 2021: 523 (2021) - [i26]Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie:
Online Linear Extractors for Independent Sources. IACR Cryptol. ePrint Arch. 2021: 1002 (2021) - [i25]Huck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-Davidowitz:
Just how hard are rotations of ℤn? Algorithms and cryptography with the simplest lattice. IACR Cryptol. ePrint Arch. 2021: 1548 (2021) - 2020
- [c21]Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro
Extractor Lower Bounds, Revisited. APPROX-RANDOM 2020: 1:1-1:20 - [c20]Tamalika Mukherjee, Noah Stephens-Davidowitz:
Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP. CRYPTO (2) 2020: 213-242 - [c19]Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz:
Slide Reduction, Revisited - Filling the Gaps in SVP Approximation. CRYPTO (2) 2020: 274-295 - [i24]Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz:
A 2n/2-Time Algorithm for √n-SVP and √n-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP. CoRR abs/2007.09556 (2020) - [i23]Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
On the Hardness of Average-case k-SUM. CoRR abs/2010.08821 (2020)
2010 – 2019
- 2019
- [j3]Stephen D. Miller
Kissing Numbers and Transference Theorems from Generalized Tail Bounds. SIAM J. Discret. Math. 33(3): 1313-1325 (2019) - [c18]Noah Stephens-Davidowitz:
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic. CCC 2019: 11:1-11:8 - [c17]Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
SETH-Hardness of Coding Problems. FOCS 2019: 287-301 - [i22]Noah Stephens-Davidowitz:
A time-distance trade-off for GDD with preprocessing - Instantiating the DLW heuristic. CoRR abs/1902.08340 (2019) - [i21]Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz:
Slide Reduction, Revisited - Filling the Gaps in SVP Approximation. CoRR abs/1908.03724 (2019) - [i20]Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). CoRR abs/1911.02440 (2019) - [i19]Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro, Noah Stephens-Davidowitz:
Extractor Lower Bounds, Revisited. Electron. Colloquium Comput. Complex. TR19 (2019) - [i18]Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
SETH-hardness of Coding Problems. Electron. Colloquium Comput. Complex. TR19 (2019) - [i17]Tamalika Mukherjee, Noah Stephens-Davidowitz:
Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP. IACR Cryptol. ePrint Arch. 2019: 1142 (2019) - 2018
- [c16]Navid Alamati, Chris Peikert, Noah Stephens-Davidowitz:
New (and Old) Proof Systems for Lattice Problems. Public Key Cryptography (2) 2018: 619-643 - [c15]Divesh Aggarwal, Noah Stephens-Davidowitz:
Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP). SOSA 2018: 12:1-12:19 - [c14]Divesh Aggarwal, Noah Stephens-Davidowitz:
(Gap/S)ETH hardness of SVP. STOC 2018: 228-238 - [i16]Stephen D. Miller, Noah Stephens-Davidowitz:
Generalizations of Banaszczyk's transference theorems and tail bound. IACR Cryptol. ePrint Arch. 2018: 188 (2018) - 2017
- [b1]Noah Stephens-Davidowitz:
On the Gaussian Measure Over Lattices. New York University, USA, 2017 - [j2]Yevgeniy Dodis, Adi Shamir, Noah Stephens-Davidowitz, Daniel Wichs:
How to Eat Your Entropy and Have it Too: Optimal Recovery Strategies for Compromised RNGs. Algorithmica 79(4): 1196-1232 (2017) - [j1]Oded Regev, Noah Stephens-Davidowitz:
An Inequality for Gaussians on Lattices. SIAM J. Discret. Math. 31(2): 749-757 (2017) - [c13]Shai Halevi, Tzipora Halevi, Victor Shoup, Noah Stephens-Davidowitz:
Implementing BP-Obfuscation Using Graph-Induced Encoding. CCS 2017: 783-798 - [c12]Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
On the Quantitative Hardness of CVP. FOCS 2017: 13-24 - [c11]Chris Peikert, Oded Regev, Noah Stephens-Davidowitz:
Pseudorandomness of ring-LWE for any ring and modulus. STOC 2017: 461-473 - [c10]Oded Regev, Noah Stephens-Davidowitz:
A reverse Minkowski theorem. STOC 2017: 941-953 - [i15]Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
On the Quantitative Hardness of CVP. CoRR abs/1704.03928 (2017) - [i14]Divesh Aggarwal, Noah Stephens-Davidowitz:
Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP). CoRR abs/1709.01535 (2017) - [i13]Divesh Aggarwal, Noah Stephens-Davidowitz:
(Gap/S)ETH Hardness of SVP. CoRR abs/1712.00942 (2017) - [i12]Shai Halevi, Tzipora Halevi, Victor Shoup, Noah Stephens-Davidowitz:
Implementing BP-Obfuscation Using Graph-Induced Encoding. IACR Cryptol. ePrint Arch. 2017: 104 (2017) - [i11]Chris Peikert, Oded Regev, Noah Stephens-Davidowitz:
Pseudorandomness of Ring-LWE for Any Ring and Modulus. IACR Cryptol. ePrint Arch. 2017: 258 (2017) - [i10]Navid Alamati, Chris Peikert, Noah Stephens-Davidowitz:
New (and Old) Proof Systems for Lattice Problems. IACR Cryptol. ePrint Arch. 2017: 1226 (2017) - 2016
- [c9]Noah Stephens-Davidowitz:
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One. APPROX-RANDOM 2016: 19:1-19:18 - [c8]Yevgeniy Dodis, Ilya Mironov
Message Transmission with Reverse Firewalls - Secure Communication on Corrupted Machines. CRYPTO (1) 2016: 341-372 - [c7]Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz:
On the Lattice Distortion Problem. ESA 2016: 9:1-9:17 - [c6]Noah Stephens-Davidowitz:
Discrete Gaussian Sampling Reduces to CVP and SVP. SODA 2016: 1748-1764 - [i9]Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz:
On the Lattice Distortion Problem. CoRR abs/1605.03613 (2016) - 2015
- [c5]Ilya Mironov
Cryptographic Reverse Firewalls. EUROCRYPT (2) 2015: 657-686 - [c4]Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz:
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again! FOCS 2015: 563-582 - [c3]Divesh Aggarwal, Daniel Dadush
Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract. STOC 2015: 733-742 - [i8]Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz:
Solving the Closest Vector Problem in $2^n$ Time - The Discrete Gaussian Strikes Again! CoRR abs/1504.01995 (2015) - [i7]Noah Stephens-Davidowitz:
Discrete Gaussian Sampling Reduces to CVP and SVP. CoRR abs/1506.07490 (2015) - [i6]Noah Stephens-Davidowitz:
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One. CoRR abs/1512.04138 (2015) - [i5]Yevgeniy Dodis, Ilya Mironov, Noah Stephens-Davidowitz:
Message Transmission with Reverse Firewalls - Secure Communication on Corrupted Machines. IACR Cryptol. ePrint Arch. 2015: 548 (2015) - 2014
- [c2]Daniel Dadush
On the Closest Vector Problem with a Distance Guarantee. CCC 2014: 98-109 - [c1]Yevgeniy Dodis, Adi Shamir, Noah Stephens-Davidowitz, Daniel Wichs:
How to Eat Your Entropy and Have It Too - Optimal Recovery Strategies for Compromised RNGs. CRYPTO (2) 2014: 37-54 - [i4]Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz:
On the Closest Vector Problem with a Distance Guarantee. CoRR abs/1409.8063 (2014) - [i3]Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz:
Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling. CoRR abs/1412.7994 (2014) - [i2]Yevgeniy Dodis, Adi Shamir, Noah Stephens-Davidowitz, Daniel Wichs:
How to Eat Your Entropy and Have it Too - Optimal Recovery Strategies for Compromised RNGs. IACR Cryptol. ePrint Arch. 2014: 167 (2014) - [i1]Ilya Mironov, Noah Stephens-Davidowitz:
Cryptographic Reverse Firewalls. IACR Cryptol. ePrint Arch. 2014: 758 (2014)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-01 01:12 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: