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

A New Algorithm for Parameterized MAX-SAT. - Ivan Bliznets; Alexander Golovnev (IPEC, 2012)

Approximating Shortest Superstring Problem Using de Bruijn Graphs. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (CPM, 2013)

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

Families with Infants: A General Approach to Solve Hard Partition Problems. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (ICALP (1), 2014)

Approximating Asymmetric TSP in exponential Time. - Alexander Golovnev (Int. J. Found. Comput. Sci., 2014)

Solving SCS for bounded length strings in fewer than 2n steps. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (Inf. Process. Lett., 2014)

New exact algorithms for the 2-constraint satisfaction problem. - Alexander Golovnev; Konstantin Kutzkov (Theor. Comput. Sci., 2014)

Lower Bounds for the Graph Homomorphism Problem. - Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (ICALP (1), 2015)

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. - Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (CoRR, 2015)

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 (Electron. Colloquium Comput. Complex., 2015)

Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds. - Alexander Golovnev; Alexander S. Kulikov (Electron. Colloquium Comput. Complex., 2015)

A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys. - Divesh Aggarwal; Alexander Golovnev (IACR Cryptol. ePrint Arch., 2015)

Condensed Unpredictability. - Maciej Skorski; Alexander Golovnev; Krzysztof Pietrzak (IACR Cryptol. ePrint Arch., 2015)

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. - Marek Cygan; Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Jakub Pachocki; Arkadiusz Socala (SODA, 2016)

Circuit size lower bounds and #SAT upper bounds through a general framework. - Alexander Golovnev; Alexander S. Kulikov; Alexander Smal; Suguru Tamaki (Electron. Colloquium Comput. Complex., 2016)

The Minrank of Random Graphs. - Alexander Golovnev; Oded Regev 001; Omri Weinstein (Electron. Colloquium Comput. Complex., 2016)

A Formal Treatment of Backdoored Pseudorandom Generators. - Yevgeniy Dodis; Chaya Ganesh; Alexander Golovnev; Ari Juels; Thomas Ristenpart (IACR Cryptol. ePrint Arch., 2016)

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (ACM Trans. Algorithms, 2016)

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

Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem. - Alexander Golovnev; Daniel Reichman 001; Igor Shinkar (CoRR, 2017)

Tight Lower Bounds on Graph Embedding Problems. - Marek Cygan; Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Jakub Pachocki; Arkadiusz Socala (J. ACM, 2017)

Circuit Complexity: New Techniques and Their Limitations. - Alexander Golovnev (2017)

Collapsing Superstring Conjecture. - Alexander Golovnev; Alexander S. Kulikov; Alexander Logunov; Ivan Mihajlin (CoRR, 2018)

Static Data Structure Lower Bounds Imply Rigidity. - Zeev Dvir; Alexander Golovnev; Omri Weinstein (Electron. Colloquium Comput. Complex., 2018)

Circuit Depth Reductions. - Alexander Golovnev; Alexander S. Kulikov (Electron. Colloquium Comput. Complex., 2018)

On the limits of gate elimination. - Alexander Golovnev; Edward A. Hirsch; Alexander Knop; Alexander S. Kulikov (J. Comput. Syst. Sci., 2018)

Gate elimination: Circuit size lower bounds and #SAT upper bounds. - Alexander Golovnev; Alexander S. Kulikov; Alexander V. Smal; Suguru Tamaki (Theor. Comput. Sci., 2018)

String Matching: Communication, Circuits, and Learning. - Alexander Golovnev; Mika Göös; Daniel Reichman 001; Igor Shinkar (APPROX-RANDOM, 2019)

Collapsing Superstring Conjecture. - Alexander Golovnev; Alexander S. Kulikov; Alexander Logunov; Ivan Mihajlin; Maksim Nikolaev (APPROX-RANDOM, 2019)

AC0[p] Lower Bounds Against MCSP via the Coin Problem. - Alexander Golovnev; Rahul Ilango; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova; Avishay Tal (ICALP, 2019)

The information-theoretic value of unlabeled data in semi-supervised learning. - Alexander Golovnev; Dávid Pál; Balázs Szörényi (ICML, 2019)

On the computational complexity of the probabilistic label tree algorithms. - Róbert Busa-Fekete; Krzysztof Dembczynski; Alexander Golovnev; Kalina Jasinska; Mikhail Kuznetsov; Maxim Sviridenko; Chao Xu (CoRR, 2019)

3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications. - Alexander Golovnev; Siyao Guo; Thibaut Horel; Sunoo Park; Vinod Vaikuntanathan (CoRR, 2019)

AC0[p] Lower Bounds against MCSP via the Coin Problem. - Alexander Golovnev; Rahul Ilango; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova; Avishay Tal (Electron. Colloquium Comput. Complex., 2019)

Breaking the Encryption Scheme of the Moscow Internet Voting System. - Pierrick Gaudry; Alexander Golovnev (Financial Cryptography, 2020)

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. - Chi-Ning Chou; Alexander Golovnev; Santhoshini Velusamy (FOCS, 2020)

Data structures meet cryptography: 3SUM with preprocessing. - Alexander Golovnev; Siyao Guo; Thibaut Horel; Sunoo Park; Vinod Vaikuntanathan (STOC, 2020)

Optimal Streaming Approximations for all Boolean Max-2CSPs. - Chi-Ning Chou; Alexander Golovnev; Santhoshini Velusamy (CoRR, 2020)

Approximability of all finite CSPs with linear sketches. - Chi-Ning Chou; Alexander Golovnev; Madhu Sudan 001; Santhoshini Velusamy (FOCS, 2021)

Circuit Depth Reductions. - Alexander Golovnev; Alexander S. Kulikov; R. Ryan Williams (ITCS, 2021)

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)

Classification of the streaming approximability of Boolean CSPs. - Chi-Ning Chou; Alexander Golovnev; Madhu Sudan 001; Santhoshini Velusamy (Electron. Colloquium Comput. Complex., 2021)

Approximability of all finite CSPs in the dynamic streaming setting. - Chi-Ning Chou; Alexander Golovnev; Madhu Sudan 001; Santhoshini Velusamy (Electron. Colloquium Comput. Complex., 2021)

Linear Space Streaming Lower Bounds for Approximating CSPs. - Chi-Ning Chou; Alexander Golovnev; Madhu Sudan 001; Ameya Velingker; Santhoshini Velusamy (Electron. Colloquium Comput. Complex., 2021)

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization. - Alexander Golovnev; Siyao Guo; Spencer Peters; Noah Stephens-Davidowitz (Electron. Colloquium Comput. Complex., 2021)

Brakedown: Linear-time and post-quantum SNARKs for R1CS. - Alexander Golovnev; Jonathan Lee 003; Srinath T. V. Setty; Justin Thaler; Riad S. Wahby (IACR Cryptol. ePrint Arch., 2021)

Worst-Case to Average-Case Reductions via Additive Combinatorics. - Vahid R. Asadi; Alexander Golovnev; Tom Gur; Igor Shinkar (Electron. Colloquium Comput. Complex., 2022)

Quantum Worst-Case to Average-Case Reductions for All Linear Problems. - Vahid R. Asadi; Alexander Golovnev; Tom Gur; Igor Shinkar; Sathyawageeswar Subramanian (Electron. Colloquium Comput. Complex., 2022)

Sketching Approximability of (Weak) Monarchy Predicates. - Chi-Ning Chou; Alexander Golovnev; Amirbehshad Shahrasbi; Madhu Sudan 001; Santhoshini Velusamy (Electron. Colloquium Comput. Complex., 2022)

Revisiting Time-Space Tradeoffs for Function Inversion. - Alexander Golovnev; Siyao Guo; Spencer Peters; Noah Stephens-Davidowitz (Electron. Colloquium Comput. Complex., 2022)

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. - Alexander Golovnev; Ishay Haviv (Adv. Math. Commun., 2022)

The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. - Alexander Golovnev; Siyao Guo; Spencer Peters; Noah Stephens-Davidowitz (APPROX/RANDOM, 2023)

Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. - Alexander Golovnev; Jonathan Lee 003; Srinath T. V. Setty; Justin Thaler; Riad S. Wahby (CRYPTO (2), 2023)

Polynomial formulations as a barrier for reduction-based hardness proofs. - Tatiana Belova; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Denil Sharipov (SODA, 2023)

Derandomization of Cell Sampling. - Alexander Golovnev; Tom Gur; Igor Shinkar (SOSA, 2023)

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

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 (Electron. Colloquium Comput. Complex., 2023)

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. - Karthik Gajulapalli; Alexander Golovnev; Satyajeet Nagargoje; Sidhant Saraogi (Electron. Colloquium Comput. Complex., 2023)

Improving 3N Circuit Complexity Lower Bounds. - Magnus Gausdal Find; Alexander Golovnev; Edward A. Hirsch; Alexander S. Kulikov (Comput. Complex., 2023)

Matrix Multiplication Verification Using Coding Theory. - Huck Bennett; Karthik Gajulapalli; Alexander Golovnev; Philip G. Warton (APPROX/RANDOM, 2024)

Difficulties Constructing Lattices with Exponential Kissing Number from Codes. - Huck Bennett; Alexander Golovnev; Noah Stephens-Davidowitz (CoRR, 2024)

On the Power of Adaptivity for Function Inversion. - Karthik Gajulapalli; Alexander Golovnev; Samuel King (Electron. Colloquium Comput. Complex., 2024)

Hilbert Functions and Low-Degree Randomness Extractors. - Alexander Golovnev; Zeyu Guo 001; Pooya Hatami; Satyajeet Nagargoje; Chao Yan (Electron. Colloquium Comput. Complex., 2024)

Polynomial Data Structure Lower Bounds in the Group Model. - Alexander Golovnev; Gleb Posobin; Oded Regev 001; Omri Weinstein (SIAM J. Comput., 2024)

Sketching Approximability of All Finite CSPs. - Chi-Ning Chou; Alexander Golovnev; Madhu Sudan 001; Santhoshini Velusamy (J. ACM, 2024)

Output-Sparse Matrix Multiplication Using Compressed Sensing. - Huck Bennett; Karthik Gajulapalli; Alexander Golovnev; Philip G. Warton (CoRR, 2025)