Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-061 | 21st April 2014 11:29

#### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

TR14-061
Authors: Raghav Kulkarni, Youming Qiao, Xiaoming Sun
Publication: 21st April 2014 19:23
Keywords:

Abstract:

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