Minterm-transitive functions with asymptotically smallest block sensitivity

DOI10.1016/J.IPL.2011.09.008zbMATH Open1260.68147OpenAlexW2090343252MaRDI QIDQ1944206FDOQ1944206

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

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

zbMATH Keywords

computational complexityBoolean functionsblock sensitivityminterm-transitive functionstight bounds

Mathematics Subject Classification ID

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

Cites Work

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

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)