We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations. In all cases, the sizes of the objects ar e optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen such object has the required properties with positive yet tiny pr obability. The main technical ingredient is a special local central limit theorem for suitable lattice ra ndom walks with finitely many steps.
One relaxation is to allow a set @math with a non-uniform distribution @math . For many practical applications of @math -designs and @math -wise permutations in statistics and computer science, but not quite every application, this relaxation is as good as the uniform question. The existence of a solution with small support is guaranteed by Carath 'eodory's theorem, using the fact that the constraints on @math are all linear equalities and inequalities. Moreover, such a solution can be found efficiently, as was shown by Karp and Papadimitriou @cite_2 and in more general settings by Koller and Megiddo @cite_6 . Alon and Lovett @cite_3 give a strongly explicit analog of this in the case of @math -wise permutations and more generally in the case of group actions.
@cite_3 @cite_6 @cite_2
2006637813 2018198126
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) = @math . It is shown 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; this is demonstrated by an application to the problem of finding large independent sets in sparse hypergraphs. We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP = co-NP—a very unlikely event. We also apply the ellipsoid method for linear programming to show that a combinatorial optimization problem is solvable in polynomial time if and only if it admits a small generator of violated inequalities.