@inproceedings{61591373d7e048b3976230e82d4c0d4c,
title = "Computing graph properties by randomized subcube partitions",
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 Ω(n2/ 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.",
author = "Ehud Friedgut and Jeff Kahn and Avi Wigderson",
year = "2002",
month = jan,
day = "1",
doi = "10.1007/3-540-45726-7_9",
language = "English (US)",
isbn = "3540441476",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "105--113",
editor = "Salil Vadhan and Rolim, {Jose D. P.}",
booktitle = "Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings",
address = "Germany",
note = "6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 ; Conference date: 13-09-2002 Through 15-09-2002",
}