| Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS A Golovnev, J Lee, S Setty, J Thaler, RS Wahby CRYPTO 2023, 193-226, 2023 | 217* | 2023 |
| A formal treatment of backdoored pseudorandom generators Y Dodis, C Ganesh, A Golovnev, A Juels, T Ristenpart Eurocrypt 2015, 101-126, 2015 | 111 | 2015 |
| Tight bounds for graph homomorphism and subgraph isomorphism M Cygan, FV Fomin, A Golovnev, AS Kulikov, I Mihajlin, J Pachocki, ... Journal of the ACM (JACM) 64 (3), 1--22, 2017 | 71* | 2017 |
| On the quantitative hardness of CVP H Bennett, A Golovnev, N Stephens-Davidowitz FOCS 2017, 13-24, 2017 | 50 | 2017 |
| Breaking the encryption scheme of the Moscow internet voting system P Gaudry, A Golovnev FC 2020, 2020 | 46 | 2020 |
| 3SUM with preprocessing: algorithms, lower bounds and cryptographic applications A Golovnev, S Guo, T Horel, S Park, V Vaikuntanathan STOC 2020, 2020 | 44* | 2020 |
| Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT CN Chou, A Golovnev, S Velusamy FOCS 2020, 330-341, 2020 | 42 | 2020 |
| Static data structure lower bounds imply rigidity Z Dvir, A Golovnev, O Weinstein STOC 2019, 967-978, 2019 | 40 | 2019 |
| AC^ 0 [p] Lower Bounds Against MCSP via the Coin Problem A Golovnev, R Ilango, R Impagliazzo, V Kabanets, A Kolokolova, A Tal ICALP 2019, 2019 | 38 | 2019 |
| Fine-grained hardness of CVP (P)—Everything that we can prove (and nothing else) D Aggarwal, H Bennett, A Golovnev, N Stephens-Davidowitz SODA 2021, 1816-1835, 2021 | 36 | 2021 |
| The minrank of random graphs A Golovnev, O Regev, O Weinstein IEEE Transactions on Information Theory (ToIT) 64 (11), 6990-6995, 2018 | 34 | 2018 |
| Linear space streaming lower bounds for approximating CSPs CN Chou, A Golovnev, M Sudan, A Velingker, S Velusamy STOC 2022, 275-288, 2022 | 27 | 2022 |
| Approximating shortest superstring problem using de Bruijn graphs A Golovnev, AS Kulikov, I Mihajlin CPM 2013, 120-129, 2013 | 25 | 2013 |
| A new algorithm for parameterized MAX-SAT I Bliznets, A Golovnev IPEC 2012, 37-48, 2012 | 24 | 2012 |
| Circuit depth reductions A Golovnev, AS Kulikov, RR Williams ITCS 2021, 2018 | 22 | 2018 |
| Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms K Gajulapalli, A Golovnev, S Nagargoje, S Saraogi RANDOM 2023, 2023 | 21 | 2023 |
| Worst-case to average-case reductions via additive combinatorics VR Asadi, A Golovnev, T Gur, I Shinkar STOC 2022, 1566-1574, 2022 | 21 | 2022 |
| Approximability of all finite CSPs with linear sketches CN Chou, A Golovnev, M Sudan, S Velusamy FOCS 2021, 1197-1208, 2022 | 18 | 2022 |
| The (generalized) orthogonality dimension of (generalized) Kneser graphs: Bounds and applications A Golovnev, I Haviv CCC 2021, 2020 | 17 | 2020 |
| Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds A Golovnev, AS Kulikov ITCS 2016, 405-411, 2016 | 17 | 2016 |
Alexander S. KulikovJetBrainsVerified email at logic.pdmi.ras.ru
