Title: Tight Hardness Results for Minimizing Discrepancy
Speaker: Aleksandar Nikolov, Rutgers University
Date: Wednesday, March 2, 2011 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
In the discrepancy problem, we are given $M$ sets $\{S_1,\ldots,S_M\}$ on $N$ elements. Our goal is to find an assignment $\chi$ of $\{-1,+1\}$ values to elements, so as to minimize the maximum discrepancy $\max_{j} |\sum_{i \in S_j} \chi(i)|$. Recently, Bansal gave an efficient algorithm for achieving $O(\sqrt{N})$ discrepancy for any set system where $M=O(N)$, giving a constructive version of Spencer's proof that the discrepancy of any set system is at most $O(\sqrt{N})$ for this range of $M$.
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 $\Omega(\sqrt{N})$. This means that even if the optimal solution has discrepancy zero, we cannot hope to efficiently find a coloring with discrepancy $o(\sqrt{N})$.
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. The framework provides a general method to derive computational hardness results from combinatorial lower bounds on discrepancy.
No prior knowledge of discrepancy theory or complexity theory will be required. The proofs are short and I will try to present them in as much detail as possible. Joint work with Alantha Newman and Moses Charikar.