We present a simple method based on a variant of Hölder's inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier $L_1$-norm) of a Boolean function. This answers an open question of Cheung, Hatami, Hosseini and Shirley (CCC 2023).
As immediate consequences, we obtain the following results.
We give an exponential separation between the logarithm of the randomized and the deterministic parity decision tree size. This is in sharp contrast with the standard binary decision tree setting where the logarithms of randomized and deterministic decision tree size are essentially polynomially related, as shown recently by Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (STOC 2023).
We give an exponential separation between the approximate and the exact spectral norm for Boolean functions.
We give an exponential separation for XOR functions between the deterministic communication complexity with oracle access to Equality function and randomized communication complexity. Previously, such a separation was known for general Boolean matrices by Chattopadhyay, Lovett, and Vinyals (CCC 2019) using the Integer Inner Product function.
Finally, our method gives an elementary and short proof for the mentioned exponential Equality oracle lower bound of Chattopadhyay, Lovett, and Vinyals for Integer Inner Product.