A Short List of Equalities Induces Large Sign Rank
Arkadev Chattopadhyay, Nikhil S. Mande · 2018
We exhibit a natural function F, that can be computed by just a linear sized decision list of 'Equalities', but whose sign rank is exponentially large. This yields the following two new unconditional complexity class separations. The first is an exponential separation between the depth-two threshold circuit classes Threshold-of Majority and Threshold-of-Threshold, answering an open question posed by Amano and Maruoka [MFCS '05] and Hansen and Podolskii [CCC '10]. The second separation shows that the communication complexity class P^MA is not contained in UPP, strongly resolving a recent open problem posed by Goos, Pitassi and Watson [ICALP '16]. In order to prove our main result, we view F 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.