3 citations · 15 across the 20 of their papers we have counts for
32 papers
Sumset Structure in Local Computation
Alexander Golovnev, Mohit Gurumukhani
We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study -local decision trees, in which each internal node q…
Improved Time-Space Tradeoffs for 3SUM-Indexing
Itai Dinur, Alexander Golovnev
3SUM-Indexing is a preprocessing variant of the 3SUM problem that has recently received a lot of attention. The best known time-space tradeoff for the problem is (u…
Matrix Multiplication Verification Using Coding Theory
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev +1
We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three matrices , , and as input, to decide whether . A classic…
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje +1
Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit , , the task is to find a outside the range of $…
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur +2
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quan…
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
Polynomial formulations as a barrier for reduction-based hardness proofs
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov +2
The Strong Exponential Time Hypothesis (SETH) asserts that for every there exists such that -SAT requires time . The field of fine-grained…
Sketching Approximability of (Weak) Monarchy Predicates
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi +2
We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals.…
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur +1
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time…
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
Since 1989, the best known lower bound on static data structures was Siegel's classical cell sampling lower bound. Siegel showed an explicit problem with inputs and possibl…
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
Sketching approximability of all finite CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
A constraint satisfaction problem (CSP), , is specified by a finite set of constraints for positive int…
Approximability of all Boolean CSPs with linear sketches
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
In this work we consider the approximability of in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Sp…
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an…
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
Alexander Golovnev, Ishay Haviv
The orthogonality dimension of a graph over a field is the smallest integer for which there exists an assignment of a vector with…
Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev +1
We show a number of fine-grained hardness results for the Closest Vector Problem in the norm (), and its approximate and non-uniform variants. First, we sh…
An Attack on the the Encryption Scheme of the Moscow Internet Voting System
Alexander Golovnev
The next Moscow City Duma elections will be held on September 8th with an option of Internet voting. Some source code of the voting system is posted online for public testing. Pier…
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel +2
This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic app…
On the computational complexity of the probabilistic label tree algorithms
Robert Busa-Fekete, Krzysztof Dembczynski, Alexander Golovnev +4
Label tree-based algorithms are widely used to tackle multi-class and multi-label problems with a large number of labels. We focus on a particular subclass of these algorithms that…
The information-theoretic value of unlabeled data in semi-supervised learning
Alexander Golovnev, Dávid Pál, Balázs Szörényi
We quantify the separation between the numbers of labeled examples required to learn in two settings: Settings with and without the knowledge of the distribution of the unlabeled d…
Circuit Depth Reductions
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
The best known size lower bounds against unrestricted circuits have remained around for several decades. Moreover, the only known technique for proving lower bounds in this mo…
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir, Alexander Golovnev, Omri Weinstein
We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower boun…
Collapsing Superstring Conjecture
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov +2
In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find a shortest string containing each of them as a substring. SCS admits $2\fr…
String Matching: Communication, Circuits, and Learning
Alexander Golovnev, Mika Göös, Daniel Reichman +1
String matching is the problem of deciding whether a given -bit string contains a given -bit pattern. We study the complexity of this problem in three settings. Communication…