My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
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. pdf ps.gz

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
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal