CONFERENCE PAPERS
Hilbert Functions and Low-Degree Randomness Extractors.
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan.
RANDOM 2024
PDF
Matrix Multiplication Verification Using Coding Theory.
Huck Bennett, Karthik Gajulapalli,
Alexander Golovnev, Evelyn Warton.
RANDOM 2024
PDF
On the Power of Adaptivity for Function Inversion.
Karthik Gajulapalli,
Alexander Golovnev, Samuel King.
ITC 2024
PDF
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
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
Difficulties Constructing Lattices with Exponential Kissing Number from Codes.
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz.
Preprint 2024
PDF
The hardness of range avoidance for randomized algorithms implies Minicrypt.
Eldon Chung,
Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz.
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
