Alexander Golovnev

117 papers A* 17A 9B 6Journal 72Unranked 12

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Online Orthogonal Vectors Revisited. SODA Karthik Gajulapalli, Alexander Golovnev, Samuel King, Sidhant Saraogi
2025	J	`jnl`	Difficulties Constructing Lattices With Exponential Kissing Number From Codes. IEEE Trans. Inf. Theory Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2025	J	`jnl`	Improved Time-Space Tradeoffs for 3SUM-Indexing. CoRR Itai Dinur, Alexander Golovnev
2025	J	`jnl`	Output-Sparse Matrix Multiplication Using Compressed Sensing. CoRR Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Evelyn Warton
2025	J	`jnl`	Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs. ACM Trans. Algorithms Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
2025	J	`jnl`	Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022). SIAM J. Comput. Lijie Chen, Alexander Golovnev, Huy Le Nguyen
2024	J	`jnl`	Difficulties Constructing Lattices with Exponential Kissing Number from Codes. CoRR Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2024	A	`conf`	Hilbert Functions and Low-Degree Randomness Extractors. APPROX/RANDOM Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
2024	J	`jnl`	Hilbert Functions and Low-Degree Randomness Extractors. CoRR Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
2024	J	`jnl`	Hilbert Functions and Low-Degree Randomness Extractors. Electron. Colloquium Comput. Complex. Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
2024	A	`conf`	Matrix Multiplication Verification Using Coding Theory. APPROX/RANDOM Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Evelyn Warton
2024	A	`conf`	On the Power of Adaptivity for Function Inversion. ITC Karthik Gajulapalli, Alexander Golovnev, Samuel King
2024	J	`jnl`	On the Power of Adaptivity for Function Inversion. Electron. Colloquium Comput. Complex. Karthik Gajulapalli, Alexander Golovnev, Samuel King
2024	J	`jnl`	Polynomial Data Structure Lower Bounds in the Group Model. SIAM J. Comput. Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2024	A*	`conf`	Quantum Worst-Case to Average-Case Reductions for All Linear Problems. SODA Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
2024	J	`jnl`	Sketching Approximability of All Finite CSPs. J. ACM Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2023	—	`conf`	Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. CRYPTO (2) Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
2023	—	`conf`	Derandomization of Cell Sampling. SOSA Alexander Golovnev, Tom Gur, Igor Shinkar
2023	J	`jnl`	Improving 3N Circuit Complexity Lower Bounds. Comput. Complex. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2023	A*	`conf`	Lattice Problems beyond Polynomial Time. STOC Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2023	J	`jnl`	Matrix Multiplication Verification Using Coding Theory. CoRR Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Evelyn Warton
2023	J	`jnl`	On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity. Electron. Colloquium Comput. Complex. Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz
2023	A*	`conf`	Polynomial formulations as a barrier for reduction-based hardness proofs. SODA Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
2023	A	`conf`	Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. APPROX/RANDOM Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
2023	J	`jnl`	Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. CoRR Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
2023	J	`jnl`	Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. Electron. Colloquium Comput. Complex. Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
2023	—	`conf`	Revisiting Time-Space Tradeoffs for Function Inversion. CRYPTO (2) Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2023	A	`conf`	The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. APPROX/RANDOM Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2022	J	`jnl`	Lattice Problems Beyond Polynomial Time. CoRR Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2022	A*	`conf`	Linear space streaming lower bounds for approximating CSPs. STOC Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
2022	J	`jnl`	Quantum Worst-Case to Average-Case Reductions for All Linear Problems. CoRR Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
2022	J	`jnl`	Quantum Worst-Case to Average-Case Reductions for All Linear Problems. Electron. Colloquium Comput. Complex. Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
2022	J	`jnl`	Revisiting Time-Space Tradeoffs for Function Inversion. Electron. Colloquium Comput. Complex. Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2022	A	`conf`	Sketching Approximability of (Weak) Monarchy Predicates. APPROX/RANDOM Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Sketching Approximability of (Weak) Monarchy Predicates. CoRR Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Sketching Approximability of (Weak) Monarchy Predicates. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. Theory Comput. Alexander Golovnev, Ishay Haviv
2022	J	`jnl`	Worst-Case to Average-Case Reductions via Additive Combinatorics. CoRR Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2022	J	`jnl`	Worst-Case to Average-Case Reductions via Additive Combinatorics. Electron. Colloquium Comput. Complex. Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2022	A*	`conf`	Worst-case to average-case reductions via additive combinatorics. STOC Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2021	J	`jnl`	Approximability of all finite CSPs in the dynamic streaming setting. CoRR Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Approximability of all finite CSPs in the dynamic streaming setting. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	A*	`conf`	Approximability of all finite CSPs with linear sketches. FOCS Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Brakedown: Linear-time and post-quantum SNARKs for R1CS. IACR Cryptol. ePrint Arch. Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
2021	A	`conf`	Circuit Depth Reductions. ITCS Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
2021	J	`jnl`	Classification of the streaming approximability of Boolean CSPs. CoRR Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Classification of the streaming approximability of Boolean CSPs. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Derandomization of Cell Sampling. CoRR Alexander Golovnev, Tom Gur, Igor Shinkar
2021	A*	`conf`	Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). SODA Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2021	J	`jnl`	Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
2021	J	`jnl`	Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
2021	J	`jnl`	On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization. Electron. Colloquium Comput. Complex. Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2021	A	`conf`	The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. CCC Alexander Golovnev, Ishay Haviv
2020	—	`conf`	Breaking the Encryption Scheme of the Moscow Internet Voting System. Financial Cryptography Pierrick Gaudry, Alexander Golovnev
2020	A*	`conf`	Data structures meet cryptography: 3SUM with preprocessing. STOC Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan
2020	A*	`conf`	Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. FOCS Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
2020	J	`jnl`	Optimal Streaming Approximations for all Boolean Max-2CSPs. CoRR Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
2020	A*	`conf`	Polynomial Data Structure Lower Bounds in the Group Model. FOCS Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2020	J	`jnl`	Polynomial Data Structure Lower Bounds in the Group Model. Electron. Colloquium Comput. Complex. Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2020	J	`jnl`	The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. CoRR Alexander Golovnev, Ishay Haviv
2019	J	`jnl`	3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications. CoRR Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan
2019	A*	`conf`	AC ICALP Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019	J	`jnl`	AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019	—	`conf`	Collapsing Superstring Conjecture. APPROX-RANDOM Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev
2019	J	`jnl`	Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). CoRR Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2019	J	`jnl`	On the computational complexity of the probabilistic label tree algorithms. CoRR Róbert Busa-Fekete, Krzysztof Dembczynski, Alexander Golovnev, Kalina Jasinska, Mikhail Kuznetsov, Maxim Sviridenko, Chao Xu
2019	A*	`conf`	Static data structure lower bounds imply rigidity. STOC Zeev Dvir, Alexander Golovnev, Omri Weinstein
2019	—	`conf`	String Matching: Communication, Circuits, and Learning. APPROX-RANDOM Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar
2019	A*	`conf`	The information-theoretic value of unlabeled data in semi-supervised learning. ICML Alexander Golovnev, Dávid Pál, Balázs Szörényi
2019	J	`jnl`	The information-theoretic value of unlabeled data in semi-supervised learning. CoRR Alexander Golovnev, Dávid Pál, Balázs Szörényi
2018	J	`jnl`	Circuit Depth Reductions. CoRR Alexander Golovnev, Alexander S. Kulikov
2018	J	`jnl`	Circuit Depth Reductions. Electron. Colloquium Comput. Complex. Alexander Golovnev, Alexander S. Kulikov
2018	J	`jnl`	Collapsing Superstring Conjecture. CoRR Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin
2018	J	`jnl`	Gate elimination: Circuit size lower bounds and #SAT upper bounds. Theor. Comput. Sci. Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
2018	J	`jnl`	On the limits of gate elimination. J. Comput. Syst. Sci. Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2018	J	`jnl`	Static Data Structure Lower Bounds Imply Rigidity. CoRR Zeev Dvir, Alexander Golovnev, Omri Weinstein
2018	J	`jnl`	Static Data Structure Lower Bounds Imply Rigidity. Electron. Colloquium Comput. Complex. Zeev Dvir, Alexander Golovnev, Omri Weinstein
2018	J	`jnl`	The Minrank of Random Graphs. IEEE Trans. Inf. Theory Alexander Golovnev, Oded Regev, Omri Weinstein
2017	—	`—`	Circuit Complexity: New Techniques and Their Limitations. Alexander Golovnev
2017	J	`jnl`	Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem. CoRR Alexander Golovnev, Daniel Reichman, Igor Shinkar
2017	A*	`conf`	On the Quantitative Hardness of CVP. FOCS Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2017	J	`jnl`	On the Quantitative Hardness of CVP. CoRR Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2017	—	`conf`	The Minrank of Random Graphs. APPROX-RANDOM Alexander Golovnev, Oded Regev, Omri Weinstein
2017	J	`jnl`	Tight Lower Bounds on Graph Embedding Problems. J. ACM Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016	A*	`conf`	A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. FOCS Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2016	J	`jnl`	A Formal Treatment of Backdoored Pseudorandom Generators. IACR Cryptol. ePrint Arch. Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart
2016	B	`conf`	Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. MFCS Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
2016	J	`jnl`	Circuit size lower bounds and #SAT upper bounds through a general framework. Electron. Colloquium Comput. Complex. Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki
2016	J	`jnl`	Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2016	B	`conf`	On the Limits of Gate Elimination. MFCS Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2016	J	`jnl`	On the Limits of Gate Elimination. Electron. Colloquium Comput. Complex. Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2016	J	`jnl`	The Minrank of Random Graphs. CoRR Alexander Golovnev, Oded Regev, Omri Weinstein
2016	J	`jnl`	The Minrank of Random Graphs. Electron. Colloquium Comput. Complex. Alexander Golovnev, Oded Regev, Omri Weinstein
2016	A*	`conf`	Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016	J	`jnl`	Tight Lower Bounds on Graph Embedding Problems. CoRR Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016	A	`conf`	Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. ITCS Alexander Golovnev, Alexander S. Kulikov
2015	—	`conf`	A Formal Treatment of Backdoored Pseudorandom Generators. EUROCRYPT (1) Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart
2015	J	`jnl`	A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys. IACR Cryptol. ePrint Arch. Divesh Aggarwal, Alexander Golovnev
2015	J	`jnl`	A better-than-3n lower bound for the circuit complexity of an explicit function. Electron. Colloquium Comput. Complex. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2015	—	`conf`	A note on lower bounds for non-interactive message authentication using weak keys. ITW Fall Divesh Aggarwal, Alexander Golovnev
2015	—	`conf`	Condensed Unpredictability. ICALP (1) Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
2015	J	`jnl`	Condensed Unpredictability. CoRR Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
2015	J	`jnl`	Condensed Unpredictability. IACR Cryptol. ePrint Arch. Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
2015	—	`conf`	Lower Bounds for the Graph Homomorphism Problem. ICALP (1) Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2015	J	`jnl`	Lower Bounds for the Graph Homomorphism Problem. CoRR Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2015	J	`jnl`	Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. CoRR Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2015	J	`jnl`	Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds. Electron. Colloquium Comput. Complex. Alexander Golovnev, Alexander S. Kulikov
2014	J	`jnl`	Approximating Asymmetric TSP in exponential Time. Int. J. Found. Comput. Sci. Alexander Golovnev
2014	—	`conf`	Families with Infants: A General Approach to Solve Hard Partition Problems. ICALP (1) Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2014	J	`jnl`	Families with infants: speeding up algorithms for NP-hard problems using FFT. CoRR Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2014	J	`jnl`	New exact algorithms for the 2-constraint satisfaction problem. Theor. Comput. Sci. Alexander Golovnev, Konstantin Kutzkov
2014	J	`jnl`	Solving SCS for bounded length strings in fewer than 2 Inf. Process. Lett. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2013	B	`conf`	Approximating Shortest Superstring Problem Using de Bruijn Graphs. CPM Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2013	J	`jnl`	Families with infants: a general approach to solve hard partition problems. CoRR Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2013	B	`conf`	Solving 3-Superstring in 3 n/3 Time. MFCS Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2012	B	`conf`	A New Algorithm for Parameterized MAX-SAT. IPEC Ivan Bliznets, Alexander Golovnev
2011	B	`conf`	New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree. IPEC Alexander Golovnev