On the sensitivity complexity of bipartite graph properties

DOI10.1016/J.TCS.2012.11.006MaRDI QIDQ1935792zbMATH OpenOpenAlexFDO

Authors Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo

Publication date 19 February 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.11.006

zbMATH Keywords

decision treebipartite graphgraph propertiessensitivity complexityTuran conjecture

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• An improved lower bound on the sensitivity complexity of graph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the sensitivity conjecture
• Sensitivity versus certificate complexity of Boolean functions

Cited in

(5)

• An improved lower bound on the sensitivity complexity of graph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the relationship between energy complexity and other Boolean function measures
• The complexity of short schedules for uet bipartite graphs

This page was built for publication: On the sensitivity complexity of bipartite graph properties

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