An improved lower bound on the sensitivity complexity of graph properties
type: Item
instance of: scholarly article
title: An improved lower bound on the sensitivity complexity of graph properties
zbMATH Open document ID: 1217.68108
author: Xiaoming Sun
published in: Theoretical Computer Science
publication date: 2011-07-14T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5920429
zbMATH Keywords: computational complexity
zbMATH Keywords: decision tree complexity
zbMATH Keywords: sensitivity complexity
zbMATH Keywords: graph property
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.02.042
OpenAlex ID: W2039999266
cites work: Complexity measures and decision tree complexity: a survey.
cites work: On induced subgraphs of the cube
cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: The equivalence of two problems on the cube
cites work: Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
cites work: CREW PRAM<scp>s</scp> and Decision Trees
cites work: On the degree of Boolean functions as real polynomials
cites work: Q3674058
cites work: The critical complexity of graph properties
cites work: Q3691584
DOI: 10.1016/J.TCS.2011.02.042
description: scientific article; zbMATH DE number 5920429