Composition limits and separating examples for some Boolean function complexity measures

DOI10.1007/S00493-014-3189-XMaRDI QIDQ1701350zbMATH OpenOpenAlexFDO

Authors J. Gilmer, Srikanth Srinivasan, Michael Saks

Publication date 22 February 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.0630

zbMATH Keywords

block sensitivitycertificate complexityfractional certificate complexity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Boolean functions (06E30)

Abstract: Block sensitivity ($bs(f)$), certificate complexity ($C(f)$) and fractional certificate complexity ($C^{\ast }(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)leqC(f)=O(bs(f{)}^2)$. We provide an infinite family of examples for which $C(f)$ grows quadratically 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{)}^{lo{g}_{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 $fcircg$ 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 submultiplicative (where measure $m$ is submultiplicative if $m(fcircg)leqm(f)m(g)$) with equality holding under some fairly general conditions. The measure $bs(f)$ is qualitatively different: it is not submultiplicative. 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 $b{s}^{lim}(f)=(C^{\ast }{)}^{lim}(f)$ and characterize $s^{lim}(f),(C^{\ast }{)}^{lim}(f)$, and $C^{lim}(f)$ in terms of the largest eigenvalue of a certain set of $2imes2$ matrices associated with $f$.

Recommendations

• Properties and applications of Boolean function composition
• Sensitivity versus certificate complexity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
• Complexity measures and decision tree complexity: a survey.

Cites work

• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Properties and applications of Boolean function composition
• Properties of complexity measures for PRAMs and WRAMs
• Quantum certificate complexity

Cited in

(9)

• On fractional block sensitivity
• On block sensitivity and fractional block sensitivity
• A finite set of functions with an EXPTIME-complete composition problem
• All classical adversary methods are equivalent for total functions
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• scientific article; zbMATH DE number 7561557 (Why is no real title available?)
• On derandomized composition of Boolean functions
• New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
• Properties and applications of Boolean function composition

This page was built for publication: Composition limits and separating examples for some Boolean function complexity measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701350)