3 citations · 15 across the 20 of their papers we have counts for
15 papers · 1 filter
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…
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 $…
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.…
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…
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…
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…
On the Quantitative Hardness of CVP
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
$ \newcommand{\eps}{\varepsilon} \newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{\CVP}{\problem{CVP}} \newcommand{\SVP}{\problem{SVP}} \newcommand{\CVPP}{\problem{C…
The Minrank of Random Graphs
Alexander Golovnev, Oded Regev, Omri Weinstein
The minrank of a graph is the minimum rank of a matrix that can be obtained from the adjacency matrix of by switching some ones to zeros (i.e., deleting edges) and then…