Zobrazeno 1 - 10
of 91
pro vyhledávání: '"Klauck, Hartmut"'
Autor:
Klauck, Hartmut, Lim, Debbie
We investigate the problem of approximating the product $a^TBc$, where $a,c\in S^{n-1}$ and $B\in O_n$, in models of communication complexity and streaming algorithms. The worst meaningful approximation is to simply decide whether the product is 1 or
Externí odkaz:
http://arxiv.org/abs/1912.11275
Autor:
Klauck, Hartmut, Lim, Debbie
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 inte
Externí odkaz:
http://arxiv.org/abs/1807.07762
Autor:
Gavinsky, Dmitry, Jain, Rahul, Klauck, Hartmut, Kundu, Srijita, Lee, Troy, Santha, Miklos, Sanyal, Swagato, Vihrovs, Jevgenijs
Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper
Externí odkaz:
http://arxiv.org/abs/1708.00822
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 technique gives tight lower bounds of $\Omega(\sqrt n)$ for both EQ an
Externí odkaz:
http://arxiv.org/abs/1511.01211
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 of complexity measures that interpolates between the two previously stu
Externí odkaz:
http://arxiv.org/abs/1508.05189
Autor:
Klauck, Hartmut, Podder, Supartha
We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown $\Theta(n)$ bounds for Inner Product mod 2 and Disjointness), as we
Externí odkaz:
http://arxiv.org/abs/1412.4904
Autor:
Klauck, Hartmut, Prakash, Ved
The exact computation of the number of distinct elements (frequency moment $F_0$) is a fundamental problem in the study of data streaming algorithms. We denote the length of the stream by $n$ where each symbol is drawn from a universe of size $m$. Wh
Externí odkaz:
http://arxiv.org/abs/1402.6800
Autor:
Klauck, Hartmut, Podder, Supartha
We show two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication protocol by a deterministic message, establishing that for all partial Bo
Externí odkaz:
http://arxiv.org/abs/1402.4312
Autor:
Hourani, Khalid, Klauck, Hartmut, Moses Jr., William K., Nanongkai, Danupon, Pandurangan, Gopal, Robinson, Peter, Scquizzato, Michele
Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, called $k$-machine model, where we have $k$ machines that jointly perfor
Externí odkaz:
http://arxiv.org/abs/1311.6209