Alexander Golovnev

Cited by

	All	Since 2019
Citations	821	622
h-index	16	14
i10-index	26	16

180

135

2013201420152016201720182019202020212022202320243 7 29 53 45 57 62 80 94 120 161 102

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
Fedor V. FominProfessor of Computer Science, University of BergenVerified email at uib.no
Huck BennettUniversity of Colorado BoulderVerified email at colorado.edu
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	101	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	84*	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	61*	2017
On the quantitative hardness of CVP H Bennett, A Golovnev, N Stephens-Davidowitz FOCS 2017, 13-24, 2017	41	2017
Breaking the encryption scheme of the Moscow internet voting system P Gaudry, A Golovnev FC 2020, 2020	34	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	32	2019
Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT CN Chou, A Golovnev, S Velusamy FOCS 2020, 330-341, 2020	30	2020
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	29	2021
The minrank of random graphs A Golovnev, O Regev, O Weinstein IEEE Transactions on Information Theory (ToIT) 64 (11), 6990-6995, 2018	28	2018
3SUM with preprocessing: algorithms, lower bounds and cryptographic applications A Golovnev, S Guo, T Horel, S Park, V Vaikuntanathan STOC 2020, 2020	27*	2020
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	21	2012
Linear space streaming lower bounds for approximating CSPs CN Chou, A Golovnev, M Sudan, A Velingker, S Velusamy STOC 2022, 275-288, 2022	17	2022
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds A Golovnev, AS Kulikov ITCS 2016, 405-411, 2016	17	2016
Circuit depth reductions A Golovnev, AS Kulikov, RR Williams ITCS 2021, 2018	16	2018
Approximability of all finite CSPs with linear sketches CN Chou, A Golovnev, M Sudan, S Velusamy FOCS 2021, 1197-1208, 2022	15	2022
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
Lower bounds for the graph homomorphism problem FV Fomin, A Golovnev, AS Kulikov, I Mihajlin ICALP 2015, 481-493, 2015	13	2015

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