Abstract
The communication class UPP^{cc} is a communication analog of the Turing Machine complexity class PP. It is characterized by a matrixanalytic complexity measure called signrank (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 polylogarithmiccost 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 = {{SignRank Can Increase Under Intersection}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {30:130:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10606},
URN = {urn:nbn:de:0030drops106067},
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 