language: en

Constructing Small Sample Spaces Satisfying Given Constraints

Daphne Koller
e-mail: daphne@cs.stanford.edu
Nimrod Megiddo
e-mail: megiddo@almaden.ibm.com

Abstract 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 P r(E) = . 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 n independent random variables, a small sample space can be constructed in polynomial time. This last result is also useful for de-randomizing algorithms. We demonstrate this technique by an application to the problem of finding large independent sets in sparse hypergraphs.

Department of Computer Science, Stanford University,
Stanford, CA 94305;
and IBM Almaden Research Center,
650 Harry Road, San Jose, CA 95120.
IBM Almaden Research Center,
650 Harry Road, San Jose, CA 95120;
and School of Mathematical Sciences, Tel Aviv University,
Tel Aviv, Israel.

[Research supported in part by ONR Contract N00014-91-C-0026 and by the Air Force Office of Scientific Research (AFSC), under Contract F49620-91-C-0080. (Paste copyright notice here.)]

1. Introduction