Sign-rank Can Increase under Intersection
Sign-rank Can Increase under Intersection
复制标题
DOI：
10.1145/3470863
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Mark Bun;Nikhil S. Mande;J. Thaler
中科院分区：
文献类型：
--
作者：
Mark Bun;Nikhil S. Mande;J. Thaler
通信类UPPcc是图灵机复杂性类PP的通信模拟。它的特点是矩阵分析的复杂性度量称为符号秩（也称为维数复杂性），本质上是最强大的通信类，我们知道如何证明下界。对于一个通信问题f，让f f表示在两个不相交的输入上计算f并输出结果的AND的函数。我们给出了一个通信问题f，其中UPPcc（f）= O（log n），且UPPcc（f <$f）= Θ（log 2 n）.这是第一个结果表明，UPP通信复杂度可以增加超过一个常数的因素下相交。我们认为这是第一步，表明UPPcc，与多功能成本的UPP通信协议的问题，是不是关闭下的交集。我们的结果表明，由n比特上两个多数的交集组成的函数类的维数复杂度为nOmegaΩ（log n）.这与（Klivans，奥唐纳和Servedio，FOCS 2002）的上限相匹配，他们用它来给出一个准多项式时间算法，用于PAC学习多个多数的交集。因此，将需要从根本上新的技术来学习这类函数在多项式时间。
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 ∧ 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.