Noah Stephens-Davidowitz
According to our database1,
Noah Stephens-Davidowitz
authored at least 47 papers
between 2014 and 2024.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
On csauthors.net:
Bibliography
2024
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices.
Electron. Colloquium Comput. Complex., 2024
CoRR, 2024
More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More.
Proceedings of the Approximation, 2024
2023
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity.
Electron. Colloquium Comput. Complex., 2023
CoRR, 2023
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Just How Hard Are Rotations of $\mathbb {Z}^n$? Algorithms and Cryptography with the Simplest Lattice.
Proceedings of the Advances in Cryptology - EUROCRYPT 2023, 2023
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems.
Proceedings of the Approximation, 2023
2022
Electron. Colloquium Comput. Complex., 2022
2021
IACR Cryptol. ePrint Arch., 2021
Just how hard are rotations of ℤ<sup>n</sup>? Algorithms and cryptography with the simplest lattice.
IACR Cryptol. ePrint Arch., 2021
On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization.
Electron. Colloquium Comput. Complex., 2021
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
A 2<sup>n/2</sup>-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP.
Proceedings of the Advances in Cryptology - EUROCRYPT 2021, 2021
Proceedings of the Advances in Cryptology - CRYPTO 2021, 2021
2020
A 2<sup>n/2</sup>-Time Algorithm for √n-SVP and √n-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP.
CoRR, 2020
Proceedings of the Advances in Cryptology - CRYPTO 2020, 2020
2019
SIAM J. Discret. Math., 2019
IACR Cryptol. ePrint Arch., 2019
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic.
Proceedings of the 34th Computational Complexity Conference, 2019
2018
IACR Cryptol. ePrint Arch., 2018
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP).
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018
2017
IACR Cryptol. ePrint Arch., 2017
IACR Cryptol. ePrint Arch., 2017
How to Eat Your Entropy and Have it Too: Optimal Recovery Strategies for Compromised RNGs.
Algorithmica, 2017
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
2016
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Proceedings of the 24th Annual European Symposium on Algorithms, 2016
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One.
Proceedings of the Approximation, 2016
2015
Message Transmission with Reverse Firewalls - Secure Communication on Corrupted Machines.
IACR Cryptol. ePrint Arch., 2015
Solving the Shortest Vector Problem in 2<sup>n</sup> Time Using Discrete Gaussian Sampling: Extended Abstract.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
2014
CoRR, 2014
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014