### Abstract

We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of A, namely the value of p for which a randomgraph from G(n, p) has property A with probability 1/2. Then the expected number of queries made by any decision tree for A on such a randomgraph is at least Ω(n^{2}/ max{pn, log n}). Our lower bound holds in the subcube partition model, which generalizes the decision tree model. The proof combines a simple combinatorial lemma on subcube partitions (which may be of independent interest) with simple graph packing arguments. Our approach motivates the study of packing of "typical" graphs, which may yield better lower bounds.

Original language | English (US) |
---|---|

Title of host publication | Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings |

Editors | Salil Vadhan, Jose D. P. Rolim |

Publisher | Springer Verlag |

Pages | 105-113 |

Number of pages | 9 |

ISBN (Print) | 3540441476, 9783540457268 |

DOIs | |

State | Published - Jan 1 2002 |

Event | 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 - Cambridge, United States Duration: Sep 13 2002 → Sep 15 2002 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2483 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 |
---|---|

Country | United States |

City | Cambridge |

Period | 9/13/02 → 9/15/02 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Computing graph properties by randomized subcube partitions'. Together they form a unique fingerprint.

## Cite this

*Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings*(pp. 105-113). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2483). Springer Verlag. https://doi.org/10.1007/3-540-45726-7_9