Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-061 | 21st April 2014 11:29

Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive



For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,
Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to \{0, 1\}$ of $n$-vertex graphs has $D(\mathcal{P}) = \Omega(n^2).$

We extend their result to $3$-uniform hypergraphs. In particular, we show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 3} \to \{0, 1\}$ of $n$-vertex $3$-uniform hypergraphs has $D(\mathcal{P}) = \Omega(n^3).$

Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant. Interestingly, our proof makes use of Vinogradov's Theorem (weak Goldbach Conjecture), inspired by its recent use by Babai et. al. \cite{bbkn} in the context of the topological approach. Our work leaves the generalization to $k$-uniform hypergraphs as an intriguing open question.

ISSN 1433-8092 | Imprint