A Lower Bound on the Trace Norm of Boolean Matrices and its Applications

期刊论文
发表日期：

2026年6月8日

查看全文

Tsun-Ming Cheung,
Hamed Hatami,
Kaave Hosseini,
Aleksandar Nikolov,
Toniann Pitassi,
Morgan Shirley

摘要

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$ $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.