Composition limits and separating examples for some boolean function complexity measures

Justin Gilmer, Michael Saks, Srikanth Srinivasan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Block sensitivity ($bs(f)$), certificate complexity ($C(f)$) and fractional certificate complexity ($C^$(f)$) are three fundamental combinatorial measures of complexity of a boolean function $f$. It has long been known that $bs(f) \leq C^{\ast}(f) \leq C(f) =O(bs(f)2)$. We provide an infinite family of examples for which $C(f)$ grows quadratic ally in $C^{\ast}(f)$ (and also $bs(f)$) giving optimal separations between these measures. Previously the biggest separation known was $C(f)=C^{\ast}(f)^{\log-{4.5}5}$. We also give a family of examples for which $C^{\ast}(f)=\Omega(bs(f)^{3/2})$. These examples are obtained by composing boolean functions in various ways. Here the composition $f \circ g$ of $f$ with $g$ is obtained by substituting for each variable of $f$ a copy of $g$ on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure $s(f)$. The measures $s(f)$, $C(f)$ and $C^{\ast}(f)$ behave nicely under composition: they are sub multiplicative (where measure $m$ is sub multiplicative if $m(f \circ g) \leq m(f)m(g)$) with equality holding under some fairly general conditions. The measure $bs(f)$ is qualitatively different: it is not sub multiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure $m$ at function $f$, $m^{\lim}(f)$ to be the limit as $k$ grows of $m(f^{(k)})^{1/k}$, where $f^{(k)}$ is the iterated composition of $f$ with itself $k$-times. For any function $f$ we show that $bs^{\lim}(f) = (C^$)^{\lim}(f)$ and characterize $s^{\lim}(f), (C^$)^{\lim}(f)$, and $C^{\lim}(f) $ in terms of the largest eigenvalue of a certain set of $2\times 2$ matrices associated with $f$.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013
Pages185-196
Number of pages12
DOIs
StatePublished - 2013
Event2013 IEEE Conference on Computational Complexity, CCC 2013 - Palo Alto, CA, United States
Duration: Jun 5 2013Jun 7 2013

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other2013 IEEE Conference on Computational Complexity, CCC 2013
Country/TerritoryUnited States
CityPalo Alto, CA
Period6/5/136/7/13

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Keywords

  • Block sensitivity
  • Certificate complexity
  • Fractional Certificate complexity
  • Iterated composition

Fingerprint

Dive into the research topics of 'Composition limits and separating examples for some boolean function complexity measures'. Together they form a unique fingerprint.

Cite this