Alexander Golovnev

ORCID

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 86

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

FOCS

STOC

Publications

Karthik Gajulapalli, Alexander Golovnev, Samuel King
On the Power of Adaptivity for Function Inversion. ITC (2024)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of All Finite CSPs. J. ACM 71 (2) (2024)
Karthik Gajulapalli, Alexander Golovnev, Samuel King
On the Power of Adaptivity for Function Inversion. Electron. Colloquium Comput. Complex. (2024)
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
Hilbert Functions and Low-Degree Randomness Extractors. CoRR (2024)
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
Hilbert Functions and Low-Degree Randomness Extractors. Electron. Colloquium Comput. Complex. (2024)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. SODA (2024)
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
Polynomial formulations as a barrier for reduction-based hardness proofs. SODA (2023)
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Philip G. Warton
Matrix Multiplication Verification Using Coding Theory. CoRR (2023)
Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. CRYPTO (2) (2023)
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
Improving 3N Circuit Complexity Lower Bounds. Comput. Complex. 32 (2) (2023)
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
Revisiting Time-Space Tradeoffs for Function Inversion. CRYPTO (2) (2023)
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. Electron. Colloquium Comput. Complex. (2023)
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. CoRR (2023)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. SOSA (2023)
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)
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. APPROX/RANDOM (2023)
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. APPROX/RANDOM (2023)
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. (2023)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-case to average-case reductions via additive combinatorics. STOC (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. Electron. Colloquium Comput. Complex. (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-Case to Average-Case Reductions via Additive Combinatorics. Electron. Colloquium Comput. Complex. 29 (2022)
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 (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. Electron. Colloquium Comput. Complex. (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-Case to Average-Case Reductions via Additive Combinatorics. CoRR (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. CoRR (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. CoRR (2022)
Alexander Golovnev, Ishay Haviv
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. Theory Comput. 18 (2022)
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
Revisiting Time-Space Tradeoffs for Function Inversion. Electron. Colloquium Comput. Complex. (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. APPROX/RANDOM (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. FOCS (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear space streaming lower bounds for approximating CSPs. STOC (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Classification of the streaming approximability of Boolean CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Brakedown: Linear-time and post-quantum SNARKs for R1CS. IACR Cryptol. ePrint Arch. 2021 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs in the dynamic streaming setting. CoRR (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. FOCS (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Classification of the streaming approximability of Boolean CSPs. CoRR (2021)
Alexander Golovnev, Ishay Haviv
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. Computational Complexity Conference (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs in the dynamic streaming setting. Electron. Colloquium Comput. Complex. 28 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
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. 28 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR (2021)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. CoRR (2021)
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)
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
Circuit Depth Reductions. ITCS (2021)
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan
Data structures meet cryptography: 3SUM with preprocessing. STOC (2020)
Alexander Golovnev, Ishay Haviv
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. CoRR (2020)
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model. FOCS (2020)
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
Optimal Streaming Approximations for all Boolean Max-2CSPs. CoRR (2020)
Pierrick Gaudry, Alexander Golovnev
Breaking the Encryption Scheme of the Moscow Internet Voting System. Financial Cryptography (2020)
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. FOCS (2020)
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan
3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications. CoRR (2019)
Róbert Busa-Fekete, Krzysztof Dembczynski, Alexander Golovnev, Kalina Jasinska, Mikhail Kuznetsov, Maxim Sviridenko, Chao Xu
On the computational complexity of the probabilistic label tree algorithms. CoRR (2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
[p] Lower Bounds Against MCSP via the Coin Problem. ICALP (2019)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev
Collapsing Superstring Conjecture. APPROX-RANDOM (2019)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). CoRR (2019)
Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar
String Matching: Communication, Circuits, and Learning. APPROX-RANDOM (2019)
Zeev Dvir, Alexander Golovnev, Omri Weinstein
Static data structure lower bounds imply rigidity. STOC (2019)
Alexander Golovnev, Dávid Pál, Balázs Szörényi
The information-theoretic value of unlabeled data in semi-supervised learning. ICML (2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander Golovnev, Dávid Pál, Balázs Szörényi
The information-theoretic value of unlabeled data in semi-supervised learning. CoRR (2019)
Zeev Dvir, Alexander Golovnev, Omri Weinstein
Static Data Structure Lower Bounds Imply Rigidity. Electron. Colloquium Comput. Complex. 25 (2018)
Alexander Golovnev, Alexander S. Kulikov
Circuit Depth Reductions. CoRR (2018)
Zeev Dvir, Alexander Golovnev, Omri Weinstein
Static Data Structure Lower Bounds Imply Rigidity. CoRR (2018)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
On the limits of gate elimination. J. Comput. Syst. Sci. 96 (2018)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin
Collapsing Superstring Conjecture. CoRR (2018)
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
Gate elimination: Circuit size lower bounds and #SAT upper bounds. Theor. Comput. Sci. 719 (2018)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. IEEE Trans. Inf. Theory 64 (11) (2018)
Alexander Golovnev, Alexander S. Kulikov
Circuit Depth Reductions. Electron. Colloquium Comput. Complex. 25 (2018)
Alexander Golovnev, Daniel Reichman, Igor Shinkar
Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem. CoRR (2017)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. APPROX-RANDOM (2017)
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
On the Quantitative Hardness of CVP. CoRR (2017)
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
On the Quantitative Hardness of CVP. FOCS (2017)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64 (3) (2017)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. CoRR (2016)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
On the Limits of Gate Elimination. Electron. Colloquium Comput. Complex. 23 (2016)
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. FOCS (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub W. Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. CoRR (2016)
Alexander Golovnev, Alexander S. Kulikov
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. ITCS (2016)
Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki
Circuit size lower bounds and #SAT upper bounds through a general framework. Electron. Colloquium Comput. Complex. 23 (2016)
Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart
A Formal Treatment of Backdoored Pseudorandom Generators. IACR Cryptol. ePrint Arch. 2016 (2016)
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. MFCS (2016)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
On the Limits of Gate Elimination. MFCS (2016)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms 12 (3) (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA (2016)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. CoRR (2015)
Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart
A Formal Treatment of Backdoored Pseudorandom Generators. EUROCRYPT (1) (2015)
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
A better-than-3n lower bound for the circuit complexity of an explicit function. Electron. Colloquium Comput. Complex. 22 (2015)
Divesh Aggarwal, Alexander Golovnev
A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys. IACR Cryptol. ePrint Arch. 2015 (2015)
Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
Condensed Unpredictability. IACR Cryptol. ePrint Arch. 2015 (2015)
Alexander Golovnev, Alexander S. Kulikov
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds. Electron. Colloquium Comput. Complex. 22 (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. CoRR (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. ICALP (1) (2015)
Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
Condensed Unpredictability. CoRR (2015)
Divesh Aggarwal, Alexander Golovnev
A note on lower bounds for non-interactive message authentication using weak keys. ITW Fall (2015)
Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
Condensed Unpredictability. ICALP (1) (2015)
Alexander Golovnev, Konstantin Kutzkov
New exact algorithms for the 2-constraint satisfaction problem. Theor. Comput. Sci. 526 (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with Infants: A General Approach to Solve Hard Partition Problems. ICALP (1) (2014)
Alexander Golovnev
Approximating Asymmetric TSP in exponential Time. Int. J. Found. Comput. Sci. 25 (1) (2014)

Alexander Golovnev.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Alexander Golovnev