3 citations · 15 across the 20 of their papers we have counts for
12 papers · 1 filter
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…
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…
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…
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…
Tight Lower Bounds on Graph Embedding Problems
Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . We al…
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . Combined…
Lower Bounds for the Graph Homomorphism Problem
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
The graph homomorphism problem (HOM) asks whether the vertices of a given -vertex graph can be mapped to the vertices of a given -vertex graph such that each edge of…
Families with infants: speeding up algorithms for NP-hard problems using FFT
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Assume that a group of people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each…
Families with infants: a general approach to solve hard partition problems
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
We introduce a general approach for solving partition problems where the goal is to represent a given set as a union (either disjoint or not) of subsets satisfying certain properti…