Composition limits and separating examples for some boolean function complexity measures

Justin Gilmer, Michael E. Saks, Srikanth SrinivasanComb 2016 · DOI

TL;DR

This paper introduces a new way to analyze how complexity measures of Boolean functions behave under composition. The authors provide optimal examples that show how much certain complexity measures can differ, improving on previous known separations and correcting errors in prior work. This work is important for understanding the fundamental limits of computation and the relationships between different measures of computational difficulty.

What Problem Does This Paper Address?

In theoretical computer science, understanding the "difficulty" of computing a function is crucial. This is often quantified by "complexity measures" like block sensitivity (bs(f)), certificate complexity (C(f)), and fractional certificate complexity (C(f)). Researchers have long sought to understand how these measures relate to each other, particularly how one measure can bound another. For instance, it's known that C(f) is at most quadratically larger than bs(f) or C(f). However, the tightest possible gap between these measures was not fully understood. This paper aims to:

  1. Provide optimal separations: Find examples of Boolean functions where the gap between these complexity measures is as large as theoretically possible.
  2. Analyze composition: Understand how these complexity measures change when Boolean functions are composed (i.e., one function's output becomes the input for another). This is a fundamental operation in building complex computations from simpler ones.
  3. Correct prior work: Address and rectify some inaccuracies found in previous research regarding the behavior of block sensitivity under composition.

Methods

The paper introduces and utilizes several key techniques:

  • Composition Limits: A central concept is the "composition limit" of a measure, denoted mlim(f). This is defined as the limit of m(f(k))^(1/k) as k goes to infinity, where f(k) is the function f composed with itself k times. This provides a way to understand the "growth rate" of a complexity measure under repeated composition.
  • Assemblages: The authors define a general framework called "assemblages" which provides a unified way to abstract and analyze various complexity measures (like sensitivity, certificate complexity, block sensitivity, etc.). This allows for a more systematic study of their properties.
  • Matrix Analysis: The behavior of complexity measures under composition is often related to matrix multiplication. The paper leverages techniques from non-negative matrix theory, specifically analyzing eigenvalues and matrix products, to derive bounds and separations.
  • Indexed Trees: To formally define and analyze function composition, the paper uses indexed trees, which provide a structured way to represent the recursive nature of composition.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Optimal Separations Achieved: The paper constructs infinite families of Boolean functions that demonstrate the largest possible quadratic separation between C(f) and C(f) (and also between C(f) and bs(f)). This means they found functions where C(f) is quadratically larger than C(f), matching the theoretical upper bound.
  • Block Sensitivity is "Different": The measure of block sensitivity (bs(f)) is shown to be qualitatively different from others like certificate complexity (C(f)) and fractional certificate complexity (C*(f)) under composition. Specifically, it's not "submultiplicative" in the same way, leading to corrections in prior literature.
  • Composition Limit Characterization: The paper provides a characterization of the composition limits for several measures (s(f), C(f), C*(f)) in terms of eigenvalues of specific matrices derived from the function.
  • bs(f) and C*(f) are Linked: A significant finding is that the composition limit of block sensitivity is equal to the composition limit of fractional certificate complexity (bslim(f) = (C*)lim(f)).

Key Results

  • Optimal Separations:
    • C(f) = Ω(C*(f)^2) and C(f) = Ω(bs(f)^2) (quadratic separation).
  • C*(f) = Ω(bs(f)^(3/2)) (a new lower bound).
  • Composition Limit Equalities: bslim(f) = (C*)lim(f) for any Boolean function f.
  • Characterization of Composition Limits: The composition limits for s(f), C(f), and C*(f) are characterized by the largest eigenvalue of certain 2x2 matrices associated with the function.
  • Corrected Bounds: The paper corrects errors in previous work, particularly regarding the analysis of bslim(f) for certain example functions.

Limitations and Future Work

  • Specific Measures: The analysis focuses on a particular set of complexity measures (sensitivity, certificate complexity, fractional certificate complexity, and block sensitivity). Extending these results to other complexity measures could be a future direction.
  • Specific Function Classes: While optimal separations are provided, the paper focuses on specific constructions. Exploring whether these separations hold for broader classes of functions or in different computational models might be interesting.
  • Generalizing Composition: The paper uses a formal definition of composition based on indexed trees. Further exploration of how different types of compositions affect complexity measures could be valuable.

Summary updated

BibTeX
@article{gilmer2016composition,
  author = {Justin Gilmer and Michael E. Saks and Srikanth Srinivasan},
  title = {{Composition limits and separating examples for some boolean function complexity measures}},
  journal = {comb.},
  year = {2016},
  doi = {10.1007/s00493-014-3189-x},
}
Figure