On the sensitivity complexity of bipartite graph properties

DOI10.1016/J.TCS.2012.11.006zbMATH Open1266.68117OpenAlexW1974514669MaRDI QIDQ1935792FDOQ1935792

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

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

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)

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)