Alexander Golovnev

Orcid: 0000-0002-7847-1027

According to our database1, Alexander Golovnev authored at least 65 papers between 2011 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Sketching Approximability of All Finite CSPs.
J. ACM, April, 2024

Hilbert Functions and Low-Degree Randomness Extractors.
Electron. Colloquium Comput. Complex., 2024

On the Power of Adaptivity for Function Inversion.
Electron. Colloquium Comput. Complex., 2024

Matrix Multiplication Verification Using Coding Theory.
Proceedings of the Approximation, 2024

2023
Improving 3N Circuit Complexity Lower Bounds.
Comput. Complex., December, 2023

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.
Electron. Colloquium Comput. Complex., 2023

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity.
Electron. Colloquium Comput. Complex., 2023

Lattice Problems beyond Polynomial Time.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Derandomization of Cell Sampling.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Polynomial formulations as a barrier for reduction-based hardness proofs.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS.
Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems.
Proceedings of the Approximation, 2023

2022
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications.
Theory Comput., 2022

Revisiting Time-Space Tradeoffs for Function Inversion.
Electron. Colloquium Comput. Complex., 2022

Sketching Approximability of (Weak) Monarchy Predicates.
Electron. Colloquium Comput. Complex., 2022

Quantum Worst-Case to Average-Case Reductions for All Linear Problems.
Electron. Colloquium Comput. Complex., 2022

Worst-Case to Average-Case Reductions via Additive Combinatorics.
Electron. Colloquium Comput. Complex., 2022

2021
Brakedown: Linear-time and post-quantum SNARKs for R1CS.
IACR Cryptol. ePrint Arch., 2021

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization.
Electron. Colloquium Comput. Complex., 2021

Linear Space Streaming Lower Bounds for Approximating CSPs.
Electron. Colloquium Comput. Complex., 2021

Approximability of all finite CSPs in the dynamic streaming setting.
Electron. Colloquium Comput. Complex., 2021

Classification of the streaming approximability of Boolean CSPs.
Electron. Colloquium Comput. Complex., 2021

Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else).
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Circuit Depth Reductions.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Approximability of all finite CSPs with linear sketches.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Polynomial Data Structure Lower Bounds in the Group Model.
Electron. Colloquium Comput. Complex., 2020

Optimal Streaming Approximations for all Boolean Max-2CSPs.
CoRR, 2020

Data structures meet cryptography: 3SUM with preprocessing.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Breaking the Encryption Scheme of the Moscow Internet Voting System.
Proceedings of the Financial Cryptography and Data Security, 2020

2019
AC0[p] Lower Bounds against MCSP via the Coin Problem.
Electron. Colloquium Comput. Complex., 2019

3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications.
CoRR, 2019

On the computational complexity of the probabilistic label tree algorithms.
CoRR, 2019

The information-theoretic value of unlabeled data in semi-supervised learning.
Proceedings of the 36th International Conference on Machine Learning, 2019

AC<sup>0</sup>[p] Lower Bounds Against MCSP via the Coin Problem.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Collapsing Superstring Conjecture.
Proceedings of the Approximation, 2019

String Matching: Communication, Circuits, and Learning.
Proceedings of the Approximation, 2019

2018
Gate elimination: Circuit size lower bounds and #SAT upper bounds.
Theor. Comput. Sci., 2018

On the limits of gate elimination.
J. Comput. Syst. Sci., 2018

Circuit Depth Reductions.
Electron. Colloquium Comput. Complex., 2018

Static Data Structure Lower Bounds Imply Rigidity.
Electron. Colloquium Comput. Complex., 2018

Collapsing Superstring Conjecture.
CoRR, 2018

2017
Circuit Complexity: New Techniques and Their Limitations.
PhD thesis, 2017

Tight Lower Bounds on Graph Embedding Problems.
J. ACM, 2017

Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem.
CoRR, 2017

On the Quantitative Hardness of CVP.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT.
ACM Trans. Algorithms, 2016

A Formal Treatment of Backdoored Pseudorandom Generators.
IACR Cryptol. ePrint Arch., 2016

The Minrank of Random Graphs.
Electron. Colloquium Comput. Complex., 2016

Circuit size lower bounds and #SAT upper bounds through a general framework.
Electron. Colloquium Comput. Complex., 2016

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
Condensed Unpredictability.
IACR Cryptol. ePrint Arch., 2015

A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys.
IACR Cryptol. ePrint Arch., 2015

Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds.
Electron. Colloquium Comput. Complex., 2015

A better-than-3n lower bound for the circuit complexity of an explicit function.
Electron. Colloquium Comput. Complex., 2015

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism.
CoRR, 2015

Lower Bounds for the Graph Homomorphism Problem.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
New exact algorithms for the 2-constraint satisfaction problem.
Theor. Comput. Sci., 2014

Solving SCS for bounded length strings in fewer than 2<sup>n</sup> steps.
Inf. Process. Lett., 2014

Approximating Asymmetric TSP in exponential Time.
Int. J. Found. Comput. Sci., 2014

Families with Infants: A General Approach to Solve Hard Partition Problems.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Solving 3-Superstring in 3 n/3 Time.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Approximating Shortest Superstring Problem Using de Bruijn Graphs.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012
A New Algorithm for Parameterized MAX-SAT.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011


  Loading...