Alexander Golovnev
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
30
Venues
11
Active years
2013–2026
Best venue rank
A*
Where they publish
Papers
30 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | ICALP | Improved Time-Space Tradeoffs for 3SUM-Indexing. | Itai Dinur, Alexander Golovnev |
| 2026 | SODA | Online Orthogonal Vectors Revisited. | Karthik Gajulapalli, Alexander Golovnev, Samuel King, Sidhant Saraogi |
| 2024 | SODA | Quantum Worst-Case to Average-Case Reductions for All Linear Problems. | Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian |
| 2023 | CRYPTO | Revisiting Time-Space Tradeoffs for Function Inversion. | Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz |
| 2023 | CRYPTO | Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. | Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby |
| 2023 | SODA | Polynomial formulations as a barrier for reduction-based hardness proofs. | Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov |
| 2023 | STOC | Lattice Problems beyond Polynomial Time. | Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan |
| 2022 | STOC | Worst-case to average-case reductions via additive combinatorics. | Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar |
| 2022 | STOC | Linear space streaming lower bounds for approximating CSPs. | Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy |
| 2021 | FOCS | Approximability of all finite CSPs with linear sketches. | Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy |
| 2021 | SODA | Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). | Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz |
| 2020 | FC | Breaking the Encryption Scheme of the Moscow Internet Voting System. | Pierrick Gaudry, Alexander Golovnev |
| 2020 | FOCS | Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. | Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy |
| 2020 | FOCS | Polynomial Data Structure Lower Bounds in the Group Model. | Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein |
| 2020 | STOC | Data structures meet cryptography: 3SUM with preprocessing. | Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan |
| 2019 | ICALP | AC | Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal |
| 2019 | ICML | The information-theoretic value of unlabeled data in semi-supervised learning. | Alexander Golovnev, Dvid Pl, Balzs Szrnyi |
| 2019 | STOC | Static data structure lower bounds imply rigidity. | Zeev Dvir, Alexander Golovnev, Omri Weinstein |
| 2017 | FOCS | On the Quantitative Hardness of CVP. | Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz |
| 2016 | FOCS | A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. | Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov |
| 2016 | MFCS | On the Limits of Gate Elimination. | Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov |
| 2016 | MFCS | Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. | Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki |
| 2016 | SODA | Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. | Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala |
| 2015 | EuroCrypt | A Formal Treatment of Backdoored Pseudorandom Generators. | Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart |
| 2015 | ICALP | Lower Bounds for the Graph Homomorphism Problem. | Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin |
| 2015 | ICALP | Condensed Unpredictability. | Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak |
| 2015 | ITW | A note on lower bounds for non-interactive message authentication using weak keys. | Divesh Aggarwal, Alexander Golovnev |
| 2014 | ICALP | Families with Infants: A General Approach to Solve Hard Partition Problems. | Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin |
| 2013 | CPM | Approximating Shortest Superstring Problem Using de Bruijn Graphs. | Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin |
| 2013 | MFCS | Solving 3-Superstring in 3 n/3 Time. | Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin |