Abstract
We exhibit a natural function F on n variables, that can be computed by just a linear sized decision list of `Equalities', but whose sign rank is at least exp(n^(1/4)). This yields the following two new unconditional complexity class separations.
(a) The function F can be computed by linear sized depth-two threshold `formulas' when the weights of the threshold gates are unrestricted, but restricting the weights of the bottom threshold gates to even slightly sub-exponential requires `circuits' to have size exp(n^(1/4)) to compute F. This provides the first separation between the boolean circuit classes THR o MAJ and THR o THR, that was posed as an open problem first by Amano-Maruoka [2005] and again by Hansen and Podolskii[2010]. Our result perhaps explains why obtaining super-polynomial lower bounds against THR o THR have remained elusive.
(b) Communication complexity: The function F (under the natural partition of the inputs) lies in the communication complexity class P^MA. Since F has large sign rank, this implies P^MA is not in UPP, resolving a recent open problem posed by G{\"o}{\"o}s, Pitassi and Watson [ICALP '16]. P^MA seems tantalizingly out of reach of current lower bound techniques.
This is based on joint work with Nikhil Mande (TIFR).