Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
On the quantum communication complexity of total functions
Dmytro Gavinsky
We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communica…
cs.CC2024
Unambiguous parity-query complexity
Dmytro Gavinsky
We give a lower bound of on the unambiguous randomised parity-query complexity of the approximate majority problem -- that is, on the lowest randomised parity-query co…
cs.CC2023
Patterned non-determinism in communication complexity
Dmytro Gavinsky
We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by . It generalises the known models $UP^{X\left…