Block sensitivity of minterm-transitive functions

DOI10.1016/j.tcs.2011.06.025zbMath1225.68092OpenAlexW1886041308MaRDI QIDQ719324

Andrew Drucker

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.025

zbMATH Keywords

Boolean functionsblock sensitivityminterm-transitive functionstransitively invariant functionsweakly symmetric functions

Mathematics Subject Classification ID

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

Related Items (5)

Minterm-transitive functions with asymptotically smallest block sensitivity ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ Unnamed Item ⋮ Certificate complexity of elementary symmetric Boolean functions

Cites Work

• Unnamed Item
• The critical complexity of graph properties
• On recognizing graph properties from adjacency matrices
• Block sensitivity of weakly symmetric functions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
• CREW PRAM<scp>s</scp> and Decision Trees
• New versions of Suen's correlation inequality
• Quantum lower bounds by polynomials

This page was built for publication: Block sensitivity of minterm-transitive functions