Daphne Koller

Papers

Daphne Koller Publications

Constructing Small Sample Spaces Satisfying Given Constraints (1994)

by D. Koller and N. Megiddo

Abstract: The subject of this paper is finding small sample spaces for joint distributions of n discrete random variables. Such distributions are often only required to obey a certain limited set of constraints of the form Pr(Event) = pi. We show that the problem of deciding whether there exists any distribution satisfying a given set of constraints is NP-hard. However, if the constraints are consistent, then there exists a distribution satisfying them which is supported by a ``small'' sample space (one whose cardinality is equal to the number of constraints). For the important case of independence constraints, where the constraints have a certain form and are consistent with a joint distribution of independent random variables, a small sample space can be constructed in polynomial time. This last result can be used to derandomize algorithms; we demonstrate this by an application to the problem of finding large independent sets in sparse hypergraphs.

Download Information

D. Koller and N. Megiddo (1994). "Constructing Small Sample Spaces Satisfying Given Constraints." Siam Journal on Discrete Mathematics, 7(2), 260-274. Full version of paper in STOC '93.

Bibtex citation

@article{Koller+Megiddo:94,
  author =       "D. Koller and N. Megiddo",
  title =        "Constructing Small Sample Spaces Satisfying Given
                 Constraints",
  journal =      "Siam Journal on Discrete Mathematics",
  volume =       "7",
  number =       "2",
  pages =        "260--274",
  year =         "1994",
  note = "Full version of paper in STOC '93",
}

full list