A short list of Equalities induces large sign-rank

We exhibit a natural function Fn on n variables that can be computed by just a linear-size decision list of "Equalities," but whose sign-rank is 2Ω (n1/4). This yields the following two new unconditional complexity class separations. 1. Boolean circuit complexity. The function Fn can be computed by linear-size depth-two threshold formulas when the weights of the threshold gates are unrestricted (THR ∘ THR), but any THR ∘ MAJ circuit (the weights of the bottom threshold gates are polynomially bounded in n) computing Fn requires size 2Ω (n1/4). This provides the first separation between the Boolean circuit complexity classes THR ∘ MAJ and THR ∘ THR. While Amano and Maruoka [Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, 2005, pp. 107-118] and Hansen and Podolskii [Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010, pp. 270-279] emphasized that superpolynomial separations between the two classes remained a basic open problem, our separation is in fact exponential. In contrast, Goldmann, Håstad, and Razborov [Comput. Complexity, 2 (1992), pp. 277-300] showed more than twenty-five years ago that functions efficiently computable by MAJ ∘ THR circuits can also be efficiently computed by MAJ ∘ MAJ circuits. In view of this, it was not even clear if THR ∘ THR was significantly more powerful than THR ∘ MAJ until our work, and there was no candidate function identified for the potential separation. 2. Communication complexity. The function Fn (under the natural partition of the inputs) lies in the communication complexity class PMA. Since Fn has large sign-rank, this implies PMA ⊈ UPP, strongly resolving a recent open problem posed by Göös, Pitassi, and Watson [Comput. Complexity, 27 (2018), pp. 245-304]. In order to prove our main result, we view Fn as an XOR function and develop a technique to lower bound the sign-rank of such functions. This requires novel approximation-theoretic arguments against polynomials of unrestricted degree. Further, our work highlights for the first time the class "decision lists of exact thresholds" as a common frontier for making progress on longstanding open problems in threshold circuits and communication complexity.

• View at Publisher

Free Full Text ( Final Version , 576kb )