TY - GEN
T1 - Computing graph properties by randomized subcube partitions
AU - Friedgut, Ehud
AU - Kahn, Jeff
AU - Wigderson, Avi
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84883427213&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883427213&partnerID=8YFLogxK
U2 - 10.1007/3-540-45726-7_9
DO - 10.1007/3-540-45726-7_9
M3 - Conference contribution
AN - SCOPUS:84883427213
SN - 3540441476
SN - 9783540457268
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 105
EP - 113
BT - Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings
A2 - Vadhan, Salil
A2 - Rolim, Jose D. P.
PB - Springer Verlag
T2 - 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002
Y2 - 13 September 2002 through 15 September 2002
ER -