On the sensitivity of cyclically-invariant Boolean functions

MaRDI QIDQ5414559zbMATH OpenFDO

Authors Sourav Chakraborty

Publication date 6 May 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2050/0.html

zbMATH Keywords

cyclically invariant functionssensitivity

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Block sensitivity of minterm-transitive functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• On the sensitivity conjecture
• Block sensitivity of weakly symmetric functions

Cited in

(10)

• Minterm-transitive functions with asymptotically smallest block sensitivity
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
• Testing Odd-Cycle-Freeness in Boolean Functions
• On fractional block sensitivity
• scientific article; zbMATH DE number 6850428 (Why is no real title available?)
• scientific article; zbMATH DE number 7559433 (Why is no real title available?)
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• Separations between combinatorial measures for transitive functions
• Block sensitivity of minterm-transitive functions

This page was built for publication: On the sensitivity of cyclically-invariant Boolean functions

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