Improved lower bounds on the randomized complexity of graph properties | Zendy

Chakrabarti Amit | Zendy; Khot Subhash | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research