I am an Assistant Professor at Georgetown University. My research interests include Computational Complexity, Algorithms, Pseudorandomness, Learning Theory, and Cryptography.

I received my PhD in 2017 from NYU where I was advised by Oded Regev and Yevgeniy Dodis. After that, I was a research scientist at Columbia University and Yahoo Research, and a Rabin postdoc at Harvard University. You can find my CV here. My email address is alex.golovnev@gmail.com.

Current Teaching: Gems of Theoretical Computer Science, Fall 2023.

Service: A 5-Course Specialization on Discrete Math; an FSTTCS'20 satellite workshop on Matrix Rigidity, and an FSTTCS'22 satellite workshop on Fine-Grained Cryptography; PC for CSR'22, FOCS'22, STOC'24, CCC'24.


Publications

CONFERENCE PAPERS

Quantum Worst-Case to Average-Case Reductions for All Linear Problems.
Vahid Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian.
SODA 2024
QIP 2023
PDF


Lattice Problems Beyond Polynomial Time.
Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan.
STOC 2023
PDF

Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs.
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov.
SODA 2023
Invited to the SODA 2023 special issue.
PDF

Derandomization of Cell Sampling.
Alexander Golovnev, Tom Gur, Igor Shinkar.
SOSA 2023
PDF

Revisiting Time-Space Tradeoffs for Function Inversion.
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz.
CRYPTO 2023
PDF

Brakedown: Linear-time and Field-Agnostic SNARKs for R1CS.
Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, Riad S. Wahby.
CRYPTO 2023
PDF

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi.
RANDOM 2023
PDF

The (im)possibility of Simple Search-to-Decision Reductions for Approximate Optimization.
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz.
APPROX 2023
PDF


Linear Space Streaming Lower Bounds for Approximating CSPs.
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy.
STOC 2022
PDF

Worst-Case to Average-Case Reductions via Additive Combinatorics.
Vahid Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar.
STOC 2022
PDF

Sketching Approximability of (Weak) Monarchy Predicates.
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy.
APPROX 2022
PDF


Approximability of All Finite CSPs with Linear Sketches.
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy.
FOCS 2021
PDF

Fine-Grained Hardness of CVP(P)— Everything that we Can Prove (and Nothing Else).
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz.
SODA 2021
PDF

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications.
Alexander Golovnev, Ishay Haviv.
CCC 2021
PDF

Circuit Depth Reductions.
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams.
ITCS 2021
PDF


Polynomial Data Structure Lower Bounds in the Group Model.
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein.
FOCS 2020
Invited to the FOCS 2020 special issue.
PDF

Optimal Streaming Approximations for All Boolean Max-2CSPs and Max-kSAT.
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy.
FOCS 2020
PDF

Data Structures Meet Cryptography: 3SUM with Preprocessing.
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan.
STOC 2020
PDF

Breaking the Encryption Scheme of the Moscow Internet Voting System.
Pierrick Gaudry, Alexander Golovnev
FC 2020
PDF


Static Data Structure Lower Bounds Imply Rigidity.
Zeev Dvir, Alexander Golovnev, Omri Weinstein.
STOC 2019
PDF

The Information-theoretic Value of Unlabeled Data in Semi-supervised Learning.
Alexander Golovnev, Dávid Pál, Balázs Szörényi.
ICML 2019
PDF

AC0[p] Lower Bounds against MCSP via the Coin Problem.
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal.
ICALP 2019
PDF

String Matching: Communication, Circuits, and Learning.
Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar.
RANDOM 2019
PDF

Collapsing Superstring Conjecture.
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev.
APPROX 2019
PDF
Visualization

On the Computational Complexity of the Probabilistic Label Tree Algorithms.
Róbert Busa-Fekete, Krzysztof Dembczyński, Alexander Golovnev, Kalina Jasinska, Mikhail Kuznetsov, Maxim Sviridenko, Chao Xu.
Preprint, 2019
PDF


On the Quantitative Hardness of CVP.
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz.
FOCS 2017
PDF

The Minrank of Random Graphs.
Alexander Golovnev, Oded Regev, Omri Weinstein.
RANDOM 2017
PDF


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.
FOCS 2016
PDF

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała.
SODA 2016
HALG 2016
PDF

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds.
Alexander Golovnev, Alexander S. Kulikov.
ITCS 2016
PDF

Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki.
MFCS 2016
PDF

On the Limits of Gate Elimination.
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov.
MFCS 2016
PDF


A Formal Treatment of Backdoored Pseudorandom Generators.
Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart.
Eurocrypt 2015
PDF

Condensed Unpredictability.
Maciej Skórski, Alexander Golovnev, Krzysztof Pietrzak.
ICALP 2015
PDF

Lower Bounds for the Graph Homomorphism Problem.
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
ICALP 2015
PDF

A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys.
Divesh Aggarwal, Alexander Golovnev.
ITW 2015
PDF


Families with Infants: a General Approach to Solve Hard Partition Problems.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
ICALP 2014
PDF


Solving 3-Superstring in 3n/3 Time.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
MFCS 2013
PDF

Approximating Shortest Superstring Problem Using de Bruijn Graphs.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
CPM 2013
PDF


A New Algorithm for Parameterized MAX-SAT.
Ivan Bliznets, Alexander Golovnev.
IPEC 2012
Excellent Student Paper Award.
PDF

Approximating Asymmetric TSP in Exponential Time.
Alexander Golovnev.
CiE 2012
PDF


New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree.
Alexander Golovnev.
IPEC 2011
PDF

BOOK

Discrete Mathematics for Computer Science.
Marie Brodsky, Alexander Golovnev, Alexander S. Kulikov, Vladimir V. Podolskii, Alexander Shen.
2020
Link

PREPRINTS

On the Power of Adaptivity for Function Inversion.
Karthik Gajulapalli, Alexander Golovnev, Samuel King.
Prepring 2024
PDF

On the Randomized Complexity of Range Avoidance, with Applications to Cryptography and Metacomplexity.
Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz.
Preprint 2023
PDF

Matrix Multiplication Verification Using Coding Theory.
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Philip G. Warton.
Preprint 2023
PDF

JOURNAL PAPERS

Sketching approximability of all finite CSPs.
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy.
Journal of the ACM, 2024
PDF

Improving 3n Circuit Complexity Lower Bounds.
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov.
Computational Complexity, 2023
PDF

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications.
Alexander Golovnev, Ishay Haviv.
Theory of Computing, 2022
PDF

Polynomial Data Structure Lower Bounds in the Group Model.
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein.
SIAM Journal on Computing, 2022
Special issue for FOCS 2020
PDF

On the Limits of Gate Elimination.
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov.
Journal of Computer and System Sciences, 2018
PDF

The Minrank of Random Graphs.
Alexander Golovnev, Oded Regev, Omri Weinstein.
Transactions on Information Theory, 2018
PDF

Gate Elimination: Circuit Size Lower Bounds and #SAT Upper Bounds.
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki.
Theoretical Computer Science, 2018
PDF

Tight Lower Bounds on Graph Embedding Problems.
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała.
Journal of the ACM, 2017
PDF

Families with Infants: Speeding up Algorithms for NP-hard Problems Using FFT.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
ACM Transactions on Algorithms, 2016
PDF

New Exact Algorithms for the 2-Constraint Satisfaction Problem.
Alexander Golovnev, Konstantin Kutzkov.
Theoretical Computer Science, 2014
PDF

Solving SCS for Bounded Length Strings in Fewer than 2n Steps.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
Information Processing Letters, 2014
PDF

Approximating Asymmetric TSP in Exponential Time.
Alexander Golovnev.
International Journal of Foundations of Computer Science, 2014
PDF

TECHNICAL REPORTS

Detecting Phishing Emails.
Hao Chen, Alexander Golovnev, Dávid Pál.
TechPulse, 2018

Fighting Spam with Nearest Neighbor and Clustering.
Travis Dick, Alexander Golovnev, Dávid Pál.
Yahoo Research, 2018

THESES

Circuit Complexity: New Techniques and Their Limitations.
Ph.D. Thesis (NYU), 2017.
PDF

Efficient Exponential Algorithms for Solving Combinatorial Problems.
Ph.D. Thesis (Belarusian Academy of Sciences), 2015.
PDF

Approximation Algorithms for Permutation Problems.
M.Sc. Thesis (St. Petersburg Academic University), 2012.
PDF


Advising

I'm lucky to advise the following students: Sidhant Saraogi (2020-present, joint with Justin Thaler), Karthik Gajulapalli (2021-present), Samuel King (2021-present), Satyajeet Nagargoje (M.Sc. 2021-present).


Teaching

2023. Gems of Theoretical Computer Science

Georgetown University

2022. Graduate Gems of Theoretical Computer Science

Georgetown University

2021. Graduate Gems of Theoretical Computer Science

Georgetown University

2021. Gems of Theoretical Computer Science

Georgetown University

2020. Matrix Rigidity

Georgetown University

2018. On Problems as Hard as Satisfiability

Summer school on Recent Advances in Algorithms, St. Petersburg

2017. Selected Topics in Circuit Complexity

Computer Science Center, St. Petersburg

2017. Specialization on Discrete Math

5 Courses taught through Coursera (together with 4 other instructors)