Alexander Golovnev

Cited by

	All	Since 2019
Citations	862	661
h-index	16	14
i10-index	26	16

160

120

2013201420152016201720182019202020212022202320243 7 29 53 45 57 62 81 94 120 152 148

Public access

View all

22 articles

0 articles

available

not available

Based on funding mandates

Co-authors

Alexander S. KulikovSteklov Institute of Mathematics at St. PetersburgVerified email at logic.pdmi.ras.ru
Ivan MihajlinUCSDVerified email at eng.ucsd.edu
Chi-Ning ChouFlatiron InstituteVerified email at flatironinstitute.org
Santhoshini VelusamyToyota Technological Institute at ChicagoVerified email at ttic.edu
Madhu SudanGordon McKay Professor of Computer Science, Harvard UniversityVerified email at cs.harvard.edu
Noah Stephens-DavidowitzCornell UniversityVerified email at cornell.edu
Huck BennettUniversity of Colorado BoulderVerified email at colorado.edu
Fedor V. FominProfessor of Computer Science, University of BergenVerified email at uib.no
Siyao GUONYU ShanghaiVerified email at nyu.edu
Justin ThalerGeorgetown UniversityVerified email at georgetown.edu
Srinath SettyPrincipal Researcher at Microsoft ResearchVerified email at microsoft.com
Riad S. WahbyCarnegie Mellon UniversityVerified email at cmu.edu
Divesh AggarwalNUSVerified email at nus.edu.sg
Vinod VaikuntanathanProfessor of Computer Science, Massachusetts Institute of TechnologyVerified email at csail.mit.edu
Marek CyganUniversity of WarsawVerified email at mimuw.edu.pl
Arkadiusz SocałaUniversity of WarsawVerified email at mimuw.edu.pl
Igor ShinkarSimon Fraser UniversityVerified email at sfu.ca
Edward A. HirschProfessor of Computer Science at Ariel UniversityVerified email at ariel.ac.il
Thomas RistenpartProfessor of Computer Science, Cornell TechVerified email at cornell.edu
Yevgeniy DodisProfessor, New York UniversityVerified email at cs.nyu.edu

Alexander Golovnev

Georgetown University

Verified email at cims.nyu.edu - Homepage

Computational Complexity Algorithms Circuit Complexity Cryptography


Title Sort by citations Sort by year Sort by title	Cited by Cited by	Year
A formal treatment of backdoored pseudorandom generators Y Dodis, C Ganesh, A Golovnev, A Juels, T Ristenpart Eurocrypt 2015, 101-126, 2015	102	2015
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS A Golovnev, J Lee, S Setty, J Thaler, RS Wahby CRYPTO 2023, 193-226, 2023	98*	2023
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	62*	2017
On the quantitative hardness of CVP H Bennett, A Golovnev, N Stephens-Davidowitz FOCS 2017, 13-24, 2017	44	2017
Breaking the encryption scheme of the Moscow internet voting system P Gaudry, A Golovnev FC 2020, 2020	35	2020
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	34	2019
Static data structure lower bounds imply rigidity Z Dvir, A Golovnev, O Weinstein STOC 2019, 967-978, 2019	33	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	31	2021
Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT CN Chou, A Golovnev, S Velusamy FOCS 2020, 330-341, 2020	31	2020
3SUM with preprocessing: algorithms, lower bounds and cryptographic applications A Golovnev, S Guo, T Horel, S Park, V Vaikuntanathan STOC 2020, 2020	29*	2020
The minrank of random graphs A Golovnev, O Regev, O Weinstein IEEE Transactions on Information Theory (ToIT) 64 (11), 6990-6995, 2018	29	2018
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	22	2012
Linear space streaming lower bounds for approximating CSPs CN Chou, A Golovnev, M Sudan, A Velingker, S Velusamy STOC 2022, 275-288, 2022	18	2022
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds A Golovnev, AS Kulikov ITCS 2016, 405-411, 2016	18	2016
Approximability of all finite CSPs with linear sketches CN Chou, A Golovnev, M Sudan, S Velusamy FOCS 2021, 1197-1208, 2022	16	2022
Circuit depth reductions A Golovnev, AS Kulikov, RR Williams ITCS 2021, 2018	16	2018
Circuit size lower bounds and #SAT upper bounds through a general framework A Golovnev, AS Kulikov, AV Smal, S Tamaki MFCS 2016, 2016	15*	2016
On the limits of gate elimination A Golovnev, EA Hirsch, A Knop, AS Kulikov Journal of Computer and System Sciences (JCSS) 96, 107-119, 2018	14	2018
Solving SCS for bounded length strings in fewer than 2n steps A Golovnev, AS Kulikov, I Mihajlin Information Processing Letters (IPL) 114 (8), 421-425, 2014	14	2014

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow

Cited by

Co-authors