Name
Abstract | ||
|---|---|---|
AbstractThe 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 ∧ 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 UPPcc(f) = O(log n), and UPPcc(f ∧ 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 nOmegaΩ(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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3470863 | ACM Transactions on Computation Theory |
Keywords | DocType | Volume |
Sign rank, dimension complexity, communication complexity, learning theory | Journal | 13 |
Issue | ISSN | Citations |
4 | 1942-3454 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Bun | 1 | 143 | 15.05 |
| Mande Nikhil S. | 2 | 5 | 4.13 |
| Thaler Justin | 3 | 273 | 20.17 |