Improved lower bounds on the randomized complexity of graph properties

Amit Chakrabarti, Subhash Khot

Research output: Contribution to journalArticle

Abstract

We prove a lower bound of Ω(n4/3 log1/3 n) on the randomized decision tree complexity of any nontrivial monotone n-vertex graph property, and of any nontrivial monotone bipartite graph property with bipartitions of size n. This improves the previous best bound of Ω(n 4/3) due to Hajnal (Combinatorica 11 (1991) 131-143). Our proof works by improving a graph packing lemma used in earlier work, and this improvement in turn stems from a novel probabilistic analysis. Graph packing being a well-studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it may be of independent interest.

Original languageEnglish (US)
Pages (from-to)427-440
Number of pages14
JournalRandom Structures and Algorithms
Volume30
Issue number3
DOIs
StatePublished - May 2007

Keywords

  • Complexity
  • Decision trees
  • Graph packing
  • Graph properties
  • Probabilistic method
  • Randomized algorithms

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Improved lower bounds on the randomized complexity of graph properties'. Together they form a unique fingerprint.

  • Cite this