An improved lower bound on the sensitivity complexity of graph properties

DOI10.1016/j.tcs.2011.02.042zbMath1217.68108OpenAlexW2039999266MaRDI QIDQ551172

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 complexitygraph propertydecision tree complexitysensitivity complexity

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On the modulo degree complexity of Boolean functions ⋮ On the relationship between energy complexity and other Boolean function measures

Cites Work

• Unnamed Item
• Unnamed Item
• The critical complexity of graph properties
• On induced subgraphs of the cube
• The equivalence of two problems on the cube
• On the degree of Boolean functions as real polynomials
• Complexity measures and decision tree complexity: a survey.
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees

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