License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.30
URN: urn:nbn:de:0030-drops-106067
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10606/
Go to the corresponding LIPIcs Volume Portal

Bun, Mark ; Mande, Nikhil S. ; Thaler, Justin

Sign-Rank Can Increase Under Intersection

pdf-format:
LIPIcs-ICALP-2019-30.pdf (0.5 MB)

Abstract

The communication class UPP^{cc} is a communication analog of the Turing Machine complexity class PP. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.
For a communication problem f, let f wedge f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP^{cc}(f)= O(log n), and UPP^{cc}(f wedge f) = Theta(log^2 n). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP^{cc}, the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection.
Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n^{Omega(log n)}. This matches an upper bound of (Klivans, O'Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.

BibTeX - Entry

@InProceedings{bun_et_al:LIPIcs:2019:10606,
  author =	{Mark Bun and Nikhil S. Mande and Justin Thaler},
  title =	{{Sign-Rank Can Increase Under Intersection}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10606},
  URN =		{urn:nbn:de:0030-drops-106067},
  doi =		{10.4230/LIPIcs.ICALP.2019.30},
  annote =	{Keywords: Sign rank, dimension complexity, communication complexity, learning theory}
}

Keywords: Sign rank, dimension complexity, communication complexity, learning theory
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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