An improved lower bound on the sensitivity complexity of graph properties

DOI10.1016/J.TCS.2011.02.042MaRDI QIDQ551172zbMATH OpenOpenAlexFDO

Authors Xiaoming Sun

Publication date 14 July 2011

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

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

zbMATH Keywords

computational complexitydecision tree complexitygraph propertysensitivity complexity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the sensitivity complexity of bipartite graph properties
• On the sensitivity complexity of k-uniform hypergraph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• An asymptotic bound for the complexity of monotone graph properties
• scientific article; zbMATH DE number 1754599

Cites work

• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• scientific article; zbMATH DE number 3916178 (Why is no real title available?)
• On induced subgraphs of the cube
• On the degree of Boolean functions as real polynomials
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• The critical complexity of graph properties
• The equivalence of two problems on the cube
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(8)

• On the sensitivity complexity of bipartite graph properties
• Improved lower bounds on the randomized complexity of graph properties
• scientific article; zbMATH DE number 1754599 (Why is no real title available?)
• On the sensitivity complexity of k-uniform hypergraph properties
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the modulo degree complexity of Boolean functions
• On the relationship between energy complexity and other Boolean function measures
• Separations between combinatorial measures for transitive functions

This page was built for publication: An improved lower bound on the sensitivity complexity of graph properties

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