On the sensitivity complexity of k-uniform hypergraph properties

DOI10.1145/3448643zbMATH Open1495.68102OpenAlexW2962919971MaRDI QIDQ5065634FDOQ5065634

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

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

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)

Cited In (1)

• Elusive properties of infinite graphs

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)