Alexander Golovnev

Cited by

	All	Since 2020
Citations	972	700
h-index	17	14
i10-index	29	19

220

110

165

20132014201520162017201820192020202120222023202420253 7 31 54 44 59 62 79 92 118 155 203 51

Public access

View all

24 articles

0 articles

available

not available

Based on funding mandates

Co-authors

Alexander S. KulikovJetBrainsVerified 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
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
Siyao GUONYU ShanghaiVerified email at nyu.edu
Divesh AggarwalNUSVerified email at nus.edu.sg
Igor ShinkarSimon Fraser UniversityVerified email at sfu.ca
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
Edward A. HirschFull Professor, Department of Computer Science, 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
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS A Golovnev, J Lee, S Setty, J Thaler, RS Wahby CRYPTO 2023, 193-226, 2023	141*	2023
A formal treatment of backdoored pseudorandom generators Y Dodis, C Ganesh, A Golovnev, A Juels, T Ristenpart Eurocrypt 2015, 101-126, 2015	106	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	64*	2017
On the quantitative hardness of CVP H Bennett, A Golovnev, N Stephens-Davidowitz FOCS 2017, 13-24, 2017	46	2017
Breaking the encryption scheme of the Moscow internet voting system P Gaudry, A Golovnev FC 2020, 2020	38	2020
3SUM with preprocessing: algorithms, lower bounds and cryptographic applications A Golovnev, S Guo, T Horel, S Park, V Vaikuntanathan STOC 2020, 2020	36*	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	36	2019
Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT CN Chou, A Golovnev, S Velusamy FOCS 2020, 330-341, 2020	35	2020
Static data structure lower bounds imply rigidity Z Dvir, A Golovnev, O Weinstein STOC 2019, 967-978, 2019	34	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
The minrank of random graphs A Golovnev, O Regev, O Weinstein IEEE Transactions on Information Theory (ToIT) 64 (11), 6990-6995, 2018	30	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	23	2012
Linear space streaming lower bounds for approximating CSPs CN Chou, A Golovnev, M Sudan, A Velingker, S Velusamy STOC 2022, 275-288, 2022	19	2022
Circuit depth reductions A Golovnev, AS Kulikov, RR Williams ITCS 2021, 2018	18	2018
Approximability of all finite CSPs with linear sketches CN Chou, A Golovnev, M Sudan, S Velusamy FOCS 2021, 1197-1208, 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 size lower bounds and #SAT upper bounds through a general framework A Golovnev, AS Kulikov, AV Smal, S Tamaki MFCS 2016, 2016	16*	2016
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	16	2014
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	15	2018

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