Minterm-transitive functions with asymptotically smallest block sensitivity

DOI10.1016/j.ipl.2011.09.008zbMath1260.68147OpenAlexW2090343252MaRDI QIDQ1944206

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)

Related Items (1)

Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

Cites Work

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

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