1 citations · 1 across the 4 of their papers we have counts for
9 papers
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Hartmut Klauck, Robert Spalek, Ronald de Wolf
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overa…
Individual Communication Complexity
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin +1
We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correc…
Quantum Time-Space Tradeoffs for Sorting
Hartmut Klauck
We investigate the complexity of sorting in the model of sequential quantum circuits. While it is known that in general a quantum algorithm based on comparisons alone cannot outper…
Rectangle Size Bounds and Threshold Covers in Communication Complexity
Hartmut Klauck
We investigate the power of the most important lower bound technique in randomized communication complexity, which is based on an evaluation of the maximal size of approximately mo…
One-way communication complexity and the Neciporuk lower bound on formula size
Hartmut Klauck
In this paper the Neciporuk method for proving lower bounds on the size of Boolean formulae is reformulated in terms of one-way communication complexity. We investigate the scenari…
On quantum and approximate privacy
Hartmut Klauck
This paper studies privacy and secure function evaluation in communication complexity. The focus is on quantum versions of the model and on protocols with only approximate privacy…