Hartmut Klauck

I&C Journal 2026 Journal Article

A hierarchy of 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 previous attempts of this endeavour, we consider two communication complexity measures as equivalent, if, when one is constant, then the other is constant as well, and vice versa. Most previous considerations of similar topics have been using polylogarithmic input length as a defining characteristic of equivalence. In this paper, two measures C 1, C 2 are constant-equivalent, if and only if for all total Boolean (families of) functions f: { 0, 1 } n × { 0, 1 } n → { 0, 1 } we have C 1 ( f ) = O ( 1 ) if and only if C 2 ( f ) = O ( 1 ). We identify five equivalence classes according to the above equivalence relation. Interestingly, the classification is counter-intuitive in that powerful models of communication are grouped with weak ones, and seemingly weaker models end up on the top of the hierarchy.

MFCS Conference 2021 Conference Paper

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 random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.

MFCS Conference 2017 Conference Paper

The Complexity of Quantum Disjointness

• Hartmut Klauck

We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a candidate for the separation of the quantum communication complexity classes QMA and QCMA. The problem generalizes the Vector-in-Subspace and Non-Disjointness problems. We give tight bounds for the QMA, quantum, randomized communication complexities of the problem. We show polynomially related upper and lower bounds for the MA complexity. We also show an upper bound for QCMA protocols, and show that the bound is tight for a natural class of QCMA protocols for the problem. The latter lower bound is based on a geometric lemma, that states that every subset of the n-dimensional sphere of measure 2^-p must contain an ortho-normal set of points of size Omega(n/p). We also study a "small-spaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Non-disjointness for randomized protocols. Interestingly, for quantum modes the complexity depends only on the dimension of the smaller space, whereas for classical modes the dimension of the larger space matters.

SODA Conference 2015 Conference Paper

Distributed Computation of Large-scale Graph Problems

• Hartmut Klauck
• Danupon Nanongkai
• Gopal Pandurangan
• Peter Robinson 0002

Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a number of fundamental graph problems in the message-passing model, where we have k machines that jointly perform computation on an arbitrary n -node (typically, n ≫ k) input graph. The graph is assumed to be randomly partitioned among the k ≥ 2 machines (a common implementation in many real world systems). The communication is point-to-point, and the goal is to minimize the time complexity, i. e. , the number of communication rounds, of solving various fundamental graph problems. We present lower bounds that quantify the fundamental time limitations of distributively solving graph problems. We first show a lower bound of Ω( n/k ) rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT). We also show an Ω( n / k 2 ) lower bound for connectivity, ST verification and other related problems. Our lower bounds develop and use new bounds in random-partition communication complexity. To complement our lower bounds, we also give algorithms for various fundamental graph problems, e. g. , PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in Õ(n/k) time (the notation Õ hides polylog( n ) factors and an additive polylog( n ) term); this shows that one can achieve almost linear (in k ) speedup, whereas for shortest paths, we present algorithms that run in time (for (1 + ε)-factor approximation) and in time (for O (log n )-factor approximation) respectively. Our results step towards understanding the complexity of distributively solving large-scale graph problems.

STOC Conference 2010 Conference Paper

A strong direct product theorem for disjointness

• Hartmut Klauck

A strong direct product theorem states that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then the overall success probability will be exponentially small in k. We establish such a theorem for the randomized communication complexity of the Disjointness problem, i.e., with communication const• kn the success probability of solving k instances of size n can only be exponentially small in k. This solves an open problem of [KSW07, LSS08]. We also show that this bound even holds for $AM$-communication protocols with limited ambiguity. The main result implies a new lower bound for Disjointness in a restricted 3-player NOF protocol, and optimal communication-space tradeoffs for Boolean matrix product. Our main result follows from a solution to the dual of a linear programming problem, whose feasibility comes from a so-called Intersection Sampling Lemma that generalizes a result by Razborov [Raz92].

STOC Conference 2008 Conference Paper

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract

• Rahul Jain 0001
• Hartmut Klauck
• Ashwin Nayak 0001

A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. We investigate this question in various models of classical communication complexity. We introduce a new measure, the subdistribution bound , which is a relaxation of the well-studied rectangle or corruption bound in communication complexity. We nonetheless show that for the communication complexity of Boolean functions with constant error, the subdistribution bound is the same as the latter measure, up to a constant factor. We prove that the one-way version of this bound tightly captures the one-way public-coin randomized communication complexity of any relation, and the two-way version bounds the two-way public-coin randomized communication complexity from below. More importantly, we show that the bound satisfies the strong direct product property under product distributions for both one- and two-way protocols, and the weak direct product property under arbitrary distributions for two-way protocols. These results subsume and strengthen, in a unified manner, several recent results on the direct product question. The simplicity and broad applicability of our technique is perhaps an indication of its potential to solve yet more challenging questions regarding the direct product problem.

FOCS Conference 2004 Conference Paper

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 overall success probability is exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the disjointness function. These results imply a time-space tradeoff T/sup 2/S = /spl Omega/(N/sup 3/) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.

STOC Conference 2003 Conference Paper

Quantum time-space tradeoffs for sorting

• Hartmut Klauck

I&C Journal 2002 Journal Article

Communication Complexity Method for Measuring Nondeterminism in Finite Automata

• Juraj Hromkovič
• Sebastian Seibert
• Juhani Karhumäki
• Hartmut Klauck
• Georg Schnitger

While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows: 1. Deterministic communication complexity provides lower bounds on the size of nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way. 2. There is a family of languages KON k 2 with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by B. Ravikumar and O. Ibarra (1989, SIAM J. Comput. 18, 1263–1282) and H. Leung (1998, SIAM J. Comput. 27, 1073–1082).

STOC Conference 2001 Conference Paper

Interaction in quantum communication and the complexity of set disjointness

• Hartmut Klauck
• Ashwin Nayak 0001
• Amnon Ta-Shma
• David Zuckerman

One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. Moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties.

FOCS Conference 2001 Conference Paper

Lower Bounds for Quantum Communication Complexity

• Hartmut Klauck

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by R. Raz (1995) to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other Fourier based lower bound methods, notably showing that /spl radic/(s~(f)/log n) n, for the average sensitivity s~(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f (x/spl and/y/spl oplus/yz), where x is a Boolean word held by Alice and y, z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, only the previously applied general lower bound method based on discrepancy yields bounds that are O(log n).

STOC Conference 2000 Conference Paper

On quantum and probabilistic communication: Las Vegas and one-way protocols

• Hartmut Klauck