On the Sensitivity Complexity of k-Uniform Hypergraph Properties

摘要

In this article, we investigate the sensitivity complexity of hypergraph properties. We present a k-uniform hypergraph property with sensitivity complexity O(n~([K/3])) for any k ≥ 3, where n is the number of vertices. Moreover, we can do better when k ≡ 1 (mod 3) by presenting a k-uniform hypergraph property with sensitivity O(n~([K/3]-1/2)). This result disproves a conjecture of Babai, which conjectures that the sensitivity complexity of k-uniform hypergraph properties is at least Ω(n~(k/2)). We also investigate the sensitivity complexity of other symmetric functions and show that for many classes of transitive Boolean functions the minimum achievable sensitivity complexity can be O(n~(k/2)), where N is the number of variables.