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