Premium
Improved lower bounds on the randomized complexity of graph properties
Author(s) -
Chakrabarti Amit,
Khot Subhash
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20164
Subject(s) - mathematics , combinatorics , monotone polygon , lemma (botany) , bipartite graph , probabilistic logic , discrete mathematics , complete bipartite graph , graph , randomized algorithm , upper and lower bounds , vertex (graph theory) , probabilistic analysis of algorithms , statistics , ecology , mathematical analysis , geometry , poaceae , biology
We prove a lower bound of Ω( n 4/3 log 1/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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007