14 citations · 69 across the 19 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.CC2018
On the Inner Product Predicate and a Generalization of Matching Vector Families
Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors.…
cs.CC2018
On Block Sensitivity and Fractional Block Sensitivity
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
We investigate the relation between the block sensitivity and fractional block sensitivity complexity measures of Boolean functions. While it is know…
quant-ph2018★ 1 cited
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids +3
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path i…