20220614
A short list of Equalities induces large signrank
Publication
Publication
SIAM Journal on Computing , Volume 51  Issue 3 p. 820 848
We exhibit a natural function Fn on n variables that can be computed by just a linearsize decision list of "Equalities," but whose signrank 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 linearsize depthtwo 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. 107118] and Hansen and Podolskii [Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010, pp. 270279] 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. 277300] showed more than twentyfive 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 signrank, this implies PMA ⊈ UPP, strongly resolving a recent open problem posed by Göös, Pitassi, and Watson [Comput. Complexity, 27 (2018), pp. 245304]. In order to prove our main result, we view Fn as an XOR function and develop a technique to lower bound the signrank of such functions. This requires novel approximationtheoretic 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.
Additional Metadata  

, , ,  
doi.org/10.1137/19M1271348  
SIAM Journal on Computing  
Organisation  Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands 
Chattopadhyay, A, & Mande, N.S. (2022). A short list of Equalities induces large signrank. SIAM Journal on Computing, 51(3), 820–848. doi:10.1137/19M1271348
