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