Minterm-transitive functions with asymptotically smallest block sensitivity

DOI10.1016/J.IPL.2011.09.008MaRDI QIDQ1944206zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.09.008

zbMATH Keywords

computational complexityBoolean functionsblock sensitivityminterm-transitive functionstight bounds

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Block sensitivity of minterm-transitive functions
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• On the sensitivity of cyclically-invariant Boolean functions
• Theory and Applications of Models of Computation
• Block sensitivity of weakly symmetric functions

Cites work

• Block sensitivity of minterm-transitive functions
• Block sensitivity of weakly symmetric functions
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Sensitivity versus block sensitivity of Boolean functions
• Tight bounds on the average sensitivity of k-CNF
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(2)

• Block sensitivity of minterm-transitive functions
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

This page was built for publication: Minterm-transitive functions with asymptotically smallest block sensitivity

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