3 citations · 15 across the 20 of their papers we have counts for
3 papers · 1 filter
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…