I am a research scientist at Columbia University and at Yahoo Research. I recently earned my PhD at NYU advised by Oded Regev and Yevgeniy Dodis. Prior to NYU, I completed my MSc at St. Petersburg Academic University under the supervision of Alexander S. Kulikov.

My research interests include Computational Complexity, Algorithms for NP-hard Problems, and Foundations of Cryptography. You can find my CV here.

Teaching

2017. Selected Topics in Circuit Complexity at CS Center in St. Petersburg

A Crash course on Circuit Complexity

2017. Specialization Introduction to Discrete Mathematics on Coursera

Lectures for the Graph Theory course, materials and exercises for the other courses

2016. Graduate course on Algorithms at NYU

Teaching Assistant: Homework sets, recitations, office hours, grading

2016. Graduate course on Random Graphs at NYU

Private Tutor

2014. Advanced Algorithms

Lectures on Advanced Algorithms in Minsk, Belarus

2013. .Net

Lectures on .NET and C# in Minsk, Belarus

2008-2010. Algorithms

Lectures on Algorithms and Data Structures for high school students in Minsk, Belarus


Publications

CONFERENCE PAPERS

Detecting Patterns Can Be Hard: Circuit Lower Bounds for the Pattern Matching Problem.
Alexander Golovnev, Daniel Reichman, Igor Shinkar.
Submitted
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 Risterpart.
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

JOURNAL PAPERS

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

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