[go: up one dir, main page]

Follow
Alexander Golovnev
Alexander Golovnev
Georgetown University
Verified email at cims.nyu.edu - Homepage
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
217*2023
A formal treatment of backdoored pseudorandom generators
Y Dodis, C Ganesh, A Golovnev, A Juels, T Ristenpart
Eurocrypt 2015, 101-126, 2015
1112015
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
502017
Breaking the encryption scheme of the Moscow internet voting system
P Gaudry, A Golovnev
FC 2020, 2020
462020
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
422020
Static data structure lower bounds imply rigidity
Z Dvir, A Golovnev, O Weinstein
STOC 2019, 967-978, 2019
402019
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
382019
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
362021
The minrank of random graphs
A Golovnev, O Regev, O Weinstein
IEEE Transactions on Information Theory (ToIT) 64 (11), 6990-6995, 2018
342018
Linear space streaming lower bounds for approximating CSPs
CN Chou, A Golovnev, M Sudan, A Velingker, S Velusamy
STOC 2022, 275-288, 2022
272022
Approximating shortest superstring problem using de Bruijn graphs
A Golovnev, AS Kulikov, I Mihajlin
CPM 2013, 120-129, 2013
252013
A new algorithm for parameterized MAX-SAT
I Bliznets, A Golovnev
IPEC 2012, 37-48, 2012
242012
Circuit depth reductions
A Golovnev, AS Kulikov, RR Williams
ITCS 2021, 2018
222018
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
K Gajulapalli, A Golovnev, S Nagargoje, S Saraogi
RANDOM 2023, 2023
212023
Worst-case to average-case reductions via additive combinatorics
VR Asadi, A Golovnev, T Gur, I Shinkar
STOC 2022, 1566-1574, 2022
212022
Approximability of all finite CSPs with linear sketches
CN Chou, A Golovnev, M Sudan, S Velusamy
FOCS 2021, 1197-1208, 2022
182022
The (generalized) orthogonality dimension of (generalized) Kneser graphs: Bounds and applications
A Golovnev, I Haviv
CCC 2021, 2020
172020
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
A Golovnev, AS Kulikov
ITCS 2016, 405-411, 2016
172016
The system can't perform the operation now. Try again later.
Articles 1–20