Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Henning Wunderlich:

TR10-086 | 17th May 2010
Henning Wunderlich

On a Theorem of Razborov

In an unpublished Russian manuscript Razborov proved that a matrix family with high
rigidity over a finite field would yield a language outside the polynomial hierarchy
in communication complexity.

We present an alternative proof that strengthens the original result in several ways.
In particular, we replace rigidity by the strictly ... more >>>

TR10-024 | 21st February 2010
Henning Wunderlich, Stefan Arnold

On a singular value method in quantum communication complexity

Comments: 1

We introduce a new lower bound method for bounded-error quantum communication complexity,
the \emph{singular value method (svm)}, based on sums of squared singular values of the
communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the
spectral ... more >>>

ISSN 1433-8092 | Imprint