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

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

TL;DR

This paper introduces a novel method using a variant of Hölder's inequality to establish a lower bound on the trace norm of Boolean matrices. This leads to a significant finding: an exponential separation between the depth of randomized parity decision trees and the spectral norm of Boolean functions, resolving a long-standing open question. This result has cascading implications, providing exponential separations in communication complexity and decision tree sizes.

What Problem Does This Paper Address?

The paper tackles fundamental questions in computational complexity theory concerning the power of randomness and the relationships between different complexity measures for Boolean functions. Specifically, it addresses the gap between randomized and deterministic computation models, particularly in the context of parity decision trees and communication complexity. A key question explored is whether the spectral norm (a measure related to Fourier analysis) of a Boolean function can be exponentially larger than its randomized parity decision tree depth. This is crucial because such a separation would imply that certain computational models cannot be efficiently simulated by others, revealing fundamental limitations. The paper also investigates the power of oracles, specifically the Equality oracle, in communication complexity and its relationship with randomized communication.

Methods

The core of the paper's methodology lies in a clever application of Hölder's inequality. The authors leverage a specific parametrization of Hölder's inequality (referred to as "the Hölder's inequality" in the paper) that relates the $L_1$-norm (spectral norm for functions, trace norm for matrices) to higher-order norms. This inequality is then applied to carefully constructed Boolean functions and matrices.

For the main result concerning decision trees, the authors construct a specific Boolean function that is the indicator of a Sidon set. Sidon sets are combinatorial objects with properties that allow for a large spectral norm while simultaneously having a small randomized parity decision tree complexity.

In the realm of communication complexity, the paper utilizes the same Hölder's inequality framework to simplify and provide elementary proofs for existing lower bounds on communication protocols with oracle access, particularly for the Integer Inner Product (IIP) function.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions of Boolean functions and matrices rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Hölder's Inequality as a Universal Tool: The paper demonstrates the surprising power and versatility of a specific form of Hölder's inequality in bridging different complexity measures, from spectral norms of functions to trace norms of matrices and communication complexity.
  • Sidon Sets as Complexity Witnesses: The construction of Boolean functions based on Sidon sets is a key insight. These sets, with their additive structure properties, provide a natural way to construct functions that exhibit large spectral norms while being efficiently computable by randomized parity decision trees.
  • Exponential Separation is Achievable: The paper definitively shows that exponential separations between seemingly related complexity measures are not only possible but can be achieved with relatively simple constructions. This challenges assumptions about the inherent relationships between different computational models.
  • Simplifying Complex Proofs: The Hölder's inequality approach offers a more elementary and combinatorial path to proving existing lower bounds in communication complexity, making these results more accessible.

Key Results

  • Exponential Separation: Spectral Norm vs. RPDT Depth: The paper proves the existence of a Boolean function $f$ such that its randomized parity decision tree depth is $O(\log n)$ while its spectral norm (Fourier $L_1$-norm) is $\Omega(n)$. This resolves an open question and shows that these measures are not polynomially related.
  • Exponential Separation: Randomized vs. Deterministic Parity Decision Tree Size: An immediate consequence is an exponential separation between the logarithmic size of randomized and deterministic parity decision trees. This contrasts sharply with the standard binary decision tree setting.
  • Exponential Separation: Approximate vs. Exact Spectral Norm: The paper demonstrates an exponential separation between the approximate and exact spectral norms for Boolean functions.
  • Communication Complexity Improvements:
    • An exponential separation is shown for XOR functions between deterministic communication complexity with an Equality oracle ($D^{EQ}$) and randomized communication complexity.
  • The paper provides an elementary and short proof for the exponential $D^{EQ}$ lower bound for the Integer Inner Product (IIP) function.

Limitations and Future Work

  • Logarithmic Gap in NEQ Complexity: For the NEQ model (nondeterministic communication with an Equality oracle), the paper achieves an almost linear lower bound for IIPk, but leaves a logarithmic gap as an open question.
  • Separation for Log RPDTsize vs. Log PDTsize: It remains an open problem whether an $O(1)$ vs. $\Omega(n)$ separation is possible for the logarithmic size of randomized parity decision trees and deterministic parity decision trees, analogous to the depth separation for the OR function.
  • Generalization of Hölder's Inequality Application: While the paper focuses on a specific parametrization of Hölder's inequality, exploring other parametrizations might yield further insights into the relationships between various norms and complexity measures.

Summary updated

Abstract

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₁-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 (D^EQ) 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 (IIP) function. - Finally, our method gives an elementary and short proof for the mentioned exponential D^EQ lower bound of Chattopadhyay, Lovett, and Vinyals for Integer Inner Product (IIP).
BibTeX
@inproceedings{cheung2025lower,
  author = {Tsun-Ming Cheung and Hamed Hatami and Kaave Hosseini and Aleksandar Nikolov and Toniann Pitassi and Morgan Shirley},
  title = {{A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications}},
  booktitle = {ITCS},
  year = {2025},
  url = {https://openreview.net/forum?id=mSBgYnYHx1},
}
Figure