License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08381.3
URN: urn:nbn:de:0030-drops-17768
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1776/
Go to the corresponding Portal

Lee, Troy ; Shraibman, Adi

Approximation norms and duality for communication complexity lower bounds

pdf-format:
08381.LeeTroy.Paper.1776.pdf (0.2 MB)

Abstract

Abstract: We will discuss a general norm based framework for showing
lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a
maximization problem, which can be more convenient to work with in showing lower bounds.

We discuss two applications of this approach.

1. The approximation rank of a matrix A is the minimum rank of a
matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We
show that an approximation norm known as gamma_2 is polynomially
related to approximation rank.
This results in a polynomial time algorithm to approximate
approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known.

2. By means of an approximation norm which lower bounds multiparty
number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.

BibTeX - Entry

@InProceedings{lee_et_al:DagSemProc.08381.3,
  author =	{Lee, Troy and Shraibman, Adi},
  title =	{{Approximation norms and duality for communication complexity lower bounds}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1776},
  URN =		{urn:nbn:de:0030-drops-17768},
  doi =		{10.4230/DagSemProc.08381.3},
  annote =	{Keywords: Communication complexity, lower bounds}
}

Keywords: Communication complexity, lower bounds
Collection: 08381 - Computational Complexity of Discrete Problems
Issue Date: 2008
Date of publication: 11.12.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI