46 citations · 170 across the 27 of their papers we have counts for
30 papers
A Hierarchy for Constant Communication Complexity
Andris Ambainis, Hartmut Klauck, Debbie Lim
Similarly to the Chomsky hierarchy, we offer a classification of communication complexity measures such that these measures are organized into equivalence classes. Different from p…
The aBc Problem and Equator Sampling Renyi Divergences
Hartmut Klauck, Debbie Lim
We investigate the problem of approximating the product , where and , in models of communication complexity and streaming algorithms. The worst me…
The Power of One Clean Qubit in Communication Complexity
Hartmut Klauck, Debbie Lim
We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a…
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Let be a Boolean function. The certificate complexity is a complexity measure that is quadratically tight for the zero-error randomized que…
Equality, Revisited
Ralph C. Bottesch, Dmytro Gavinsky, Hartmut Klauck
We develop a new lower bound method for analysing the complexity of the Equality function (EQ) in the Simultaneous Message Passing (SMP) model of communication complexity. The new…
Correlation in Hard Distributions in Communication Complexity
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family o…