2019/03/01 by Mark Bun, Nikhil S. Mande, Bun, Mark +3 · 1 citation
Computer Science · #68Q17 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC #msc:68Q17 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1903.00544
18 pages
arxiv created 2019/03/01 · openalex publication_date 2019/03/01 · arxiv updated 2019/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The communication class UPPcc 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(f)= O(log n), and UPP(f \wedge f) = Θ(log2 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 UPPcc, 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Ω(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.