Tight Hardness Results for Minimizing Discrepancy

Abstract

In the Discrepancy problem, we are given M sets {S1, …, SM} on N elements. Our goal is to find an assignment χ of {– 1, +1} values to elements, so as to minimize the maximum discrepancy . Recently, Bansal gave an efficient algorithm for achieving O(√N) discrepancy for any set system where M = O(N) [Ban10], giving a constructive version of Spencer's proof that the discrepancy of any set system is at most O(√N) for this range of M [Spe85]. We show that from the perspective of computational efficiency, these results are tight for general set systems where M = O(N). Specifically, we show that it is NP-hard to distinguish between such set systems with discrepancy zero and those with discrepancy Ω(√ N). This means that even if the optimal solution has discrepancy zero, we cannot hope to efficiently find a coloring with discrepancy o(√N). We also consider the hardness of the Discrepancy problem on sets with bounded shatter function, and show that the upper bounds due to Matoušek [Mat95] are tight for these sets systems as well. The hardness results in both settings are obtained from a common framework: we compose a family of high discrepancy set systems with set systems for which it is NP-hard to distinguish instances with discrepancy zero from instances in which a large number of the sets (i.e. constant fraction of the sets) have non-zero discrepancy. Our composition amplifies this zero versus non-zero gap.