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 Rabin postdoc at Harvard University, and a research scientist at Columbia University and Yahoo Research. You can find my CV here.

Current Teaching: Matrix Rigidity, Fall 2020.

I am also one of the creators of Coursera's 5-Course Specialization on Discrete Math.

My email address is alex.golovnev@gmail.com.


Publications

CONFERENCE PAPERS

Optimal Streaming Approximations for all Boolean Max-2CSPs.
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy.
FOCS 2020
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

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 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

PREPRINTS

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

Circuit Depth Reductions.
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams.
Submitted, 2019
PDF

Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else).
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz.
Submitted, 2019
PDF

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.
Submitted, 2019
PDF

JOURNAL PAPERS

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


Teaching

2018. On Problems as Hard as Satisfiability, Lead Instructor

Summer school on Recent Advances in Algorithms, St. Petersburg

2017. Selected Topics in Circuit Complexity, Lead Instructor

Computer Science Center, St. Petersburg

2017. Specialization on Discrete Math, Lead Instructor

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

2016. Algorithms, Teaching Assistant

Graduate course at NYU. Homework sets, recitations, office hours, grading.

2016-2019. Circuit Complexity and Discrete Math, Guest Lecturer

Classes taught by Boaz Barak, Ben Rossman, Leslie Valiant and Ryan Williams

2016. Random Graphs, Tutor

Graduate course at NYU

2014. Advanced Algorithms, Lead Instructor

Minsk, Belarus

2013. .Net, Lead Instructor

Minsk, Belarus

2008-2010. Algorithms, Lead Instructor

Minsk, Belarus