31 citations · 199 across the 33 of their papers we have counts for
3 papers · 1 filter
Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
Aleksandrs Belovs, Ansis Rosmanis
In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equ…
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao +2
The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from gr…
Provably secure key establishment against quantum adversaries
Aleksandrs Belovs, Gilles Brassard, Peter Hoyer +3
At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally aga…