On the sensitivity complexity of k-uniform hypergraph properties

DOI10.1145/3448643MaRDI QIDQ5065634zbMATH OpenOpenAlexFDO

Authors Qian Li, Xiaoming Sun

Publication date 22 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3448643

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)

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 resolution of the sensitivity conjecture

Cited in

(4)

• Elusive properties of infinite graphs
• An improved lower bound on the sensitivity complexity of graph properties
• On the sensitivity complexity of bipartite graph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph 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 Q5065634)