Block sensitivity of minterm-transitive functions

Andrew Drucker

doi:10.1016/j.tcs.2011.06.025

Block sensitivity of minterm-transitive functions

Andrew Drucker

Research output: Contribution to journal › Article › peer-review

Abstract

Boolean functions with a high degree of symmetry are interesting from a complexity theory perspective: extensive research has shown that these functions, if nonconstant, must have high complexity according to various measures.

In a recent work of this type, Sun (2007) [9] gave lower bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f)=Ω(N1/3)bs(f)=Ω(N1/3). He also showed that there exists such a function for which bs(f)=O(N3/7lnN)bs(f)=O(N3/7lnN). His example belongs to a subclass of transitively invariant functions called “minterm-transitive” functions, defined by Chakraborty (2005) [3].

We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f)=Ω(N3/7)bs(f)=Ω(N3/7). Thus, Sun’s example has nearly minimal block sensitivity for this subclass. Second, we improve Sun’s example: we exhibit a minterm-transitive function for which bs(f)=O(N3/7ln1/7N)bs(f)=O(N3/7ln1/7N).

Original language	English
Pages (from-to)	5796-5801
Number of pages	6
Journal	Theoretical Computer Science
Volume	412
Issue number	41
DOIs	https://doi.org/10.1016/j.tcs.2011.06.025
Publication status	Published - 2011

Access to Document

10.1016/j.tcs.2011.06.025

Drucker 2011 Block sensitivity of minterm-transitive functionsAccepted author manuscript, 217 KB

http://dx.doi.org/10.1016/j.tcs.2011.06.025

Fingerprint Dive into the research topics of 'Block sensitivity of minterm-transitive functions'. Together they form a unique fingerprint.

Cite this

@article{5ddcb06d101647f1b7cc3708456659eb,

title = "Block sensitivity of minterm-transitive functions",

abstract = "Boolean functions with a high degree of symmetry are interesting from a complexity theory perspective: extensive research has shown that these functions, if nonconstant, must have high complexity according to various measures.In a recent work of this type, Sun (2007) [9] gave lower bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f)=Ω(N1/3)bs(f)=Ω(N1/3). He also showed that there exists such a function for which bs(f)=O(N3/7lnN)bs(f)=O(N3/7lnN). His example belongs to a subclass of transitively invariant functions called “minterm-transitive” functions, defined by Chakraborty (2005) [3].We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f)=Ω(N3/7)bs(f)=Ω(N3/7). Thus, Sun{\textquoteright}s example has nearly minimal block sensitivity for this subclass. Second, we improve Sun{\textquoteright}s example: we exhibit a minterm-transitive function for which bs(f)=O(N3/7ln1/7N)bs(f)=O(N3/7ln1/7N).",

author = "Andrew Drucker",

year = "2011",

doi = "10.1016/j.tcs.2011.06.025",

language = "English",

volume = "412",

pages = "5796--5801",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "41",

}

TY - JOUR

T1 - Block sensitivity of minterm-transitive functions

AU - Drucker, Andrew

PY - 2011

Y1 - 2011

N2 - Boolean functions with a high degree of symmetry are interesting from a complexity theory perspective: extensive research has shown that these functions, if nonconstant, must have high complexity according to various measures.In a recent work of this type, Sun (2007) [9] gave lower bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f)=Ω(N1/3)bs(f)=Ω(N1/3). He also showed that there exists such a function for which bs(f)=O(N3/7lnN)bs(f)=O(N3/7lnN). His example belongs to a subclass of transitively invariant functions called “minterm-transitive” functions, defined by Chakraborty (2005) [3].We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f)=Ω(N3/7)bs(f)=Ω(N3/7). Thus, Sun’s example has nearly minimal block sensitivity for this subclass. Second, we improve Sun’s example: we exhibit a minterm-transitive function for which bs(f)=O(N3/7ln1/7N)bs(f)=O(N3/7ln1/7N).

AB - Boolean functions with a high degree of symmetry are interesting from a complexity theory perspective: extensive research has shown that these functions, if nonconstant, must have high complexity according to various measures.In a recent work of this type, Sun (2007) [9] gave lower bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f)=Ω(N1/3)bs(f)=Ω(N1/3). He also showed that there exists such a function for which bs(f)=O(N3/7lnN)bs(f)=O(N3/7lnN). His example belongs to a subclass of transitively invariant functions called “minterm-transitive” functions, defined by Chakraborty (2005) [3].We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f)=Ω(N3/7)bs(f)=Ω(N3/7). Thus, Sun’s example has nearly minimal block sensitivity for this subclass. Second, we improve Sun’s example: we exhibit a minterm-transitive function for which bs(f)=O(N3/7ln1/7N)bs(f)=O(N3/7ln1/7N).

U2 - 10.1016/j.tcs.2011.06.025

DO - 10.1016/j.tcs.2011.06.025

M3 - Article

VL - 412

SP - 5796

EP - 5801

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 41

ER -