On the sensitivity complexity of k-uniform hypergraph properties

DOI10.4230/LIPICS.STACS.2017.51MaRDI QIDQ4636652zbMATH OpenOpenAlexFDO

Authors Qian Li, Xiaoming Sun

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1608.06724

zbMATH Keywords

Boolean functionsensitivity complexity\(k\)-uniform hypergraph propertiesTurán's question

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)

Abstract: In this paper we investigate the sensitivity complexity of hypergraph properties. We present a $k$-uniform hypergraph property with sensitivity complexity $O(n^{lceilk/3ceil})$ for any $kgeq3$, where $n$ is the number of vertices. Moreover, we can do better when $kequiv1$ (mod 3) by presenting a $k$-uniform hypergraph property with sensitivity $O(n^{lceilk/3ceil-1/2})$. This result disproves a conjecture of Babai~cite{Babai}, which conjectures that the sensitivity complexity of $k$-uniform hypergraph properties is at least $Omega(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^{1/3})$, where $N$ is the number of variables. Finally, we give a lower bound for sensitivity of $k$-uniform hypergraph properties, which implies the {em sensitivity conjecture} of $k$-uniform hypergraph properties for any constant $k$.

Recommendations

• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• An improved lower bound on the sensitivity complexity of graph properties
• On the sensitivity complexity of bipartite graph properties
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On the sensitivity conjecture for read-\(k\) formulas

Cited in

(5)

• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• An improved lower bound on the sensitivity complexity of graph properties
• A tighter relation between sensitivity complexity and certificate complexity
• On the sensitivity complexity of bipartite graph properties

This page was built for publication: On the sensitivity complexity of \(k\)-uniform hypergraph properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636652)