Computing graph properties by randomized subcube partitions

Ehud Friedgut, Jeff Kahn, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

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.

Original languageEnglish (US)
Title of host publicationRandomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings
EditorsSalil Vadhan, Jose D. P. Rolim
PublisherSpringer Verlag
Pages105-113
Number of pages9
ISBN (Print)3540441476, 9783540457268
DOIs
StatePublished - Jan 1 2002
Event6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 - Cambridge, United States
Duration: Sep 13 2002Sep 15 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2483
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002
CountryUnited States
CityCambridge
Period9/13/029/15/02

Fingerprint

Decision trees
Decision tree
Partition
Lower bound
Property A
Computing
Monotone
Graph Packing
Graph in graph theory
Simple Graph
Packing
Lemma
Query
Denote
Generalise
Model

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Friedgut, E., Kahn, J., & Wigderson, A. (2002). Computing graph properties by randomized subcube partitions. In S. Vadhan, & J. D. P. Rolim (Eds.), 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
Friedgut, Ehud ; Kahn, Jeff ; Wigderson, Avi. / Computing graph properties by randomized subcube partitions. Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings. editor / Salil Vadhan ; Jose D. P. Rolim. Springer Verlag, 2002. pp. 105-113 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@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 = "1",
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",

}

Friedgut, E, Kahn, J & Wigderson, A 2002, Computing graph properties by randomized subcube partitions. in S Vadhan & JDP Rolim (eds), Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2483, Springer Verlag, pp. 105-113, 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002, Cambridge, United States, 9/13/02. https://doi.org/10.1007/3-540-45726-7_9

Computing graph properties by randomized subcube partitions. / Friedgut, Ehud; Kahn, Jeff; Wigderson, Avi.

Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings. ed. / Salil Vadhan; Jose D. P. Rolim. Springer Verlag, 2002. p. 105-113 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2483).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Computing graph properties by randomized subcube partitions

AU - Friedgut, Ehud

AU - Kahn, Jeff

AU - Wigderson, Avi

PY - 2002/1/1

Y1 - 2002/1/1

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

ER -

Friedgut E, Kahn J, Wigderson A. Computing graph properties by randomized subcube partitions. In Vadhan S, Rolim JDP, editors, Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings. Springer Verlag. 2002. p. 105-113. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-45726-7_9