Tight Hardness Results for Minimizing Discrepancy

Moses Charikar, Alantha Newman, Aleksandar NikolovSODA 2011 · DOI

TL;DR

This paper proves that current efficient algorithms for minimizing discrepancy in set systems are fundamentally limited. They demonstrate that it's NP-hard to distinguish between set systems with perfect solutions and those with only slightly worse solutions, implying that no algorithm can efficiently achieve significantly better guarantees than what's already known for general cases.

What Problem Does This Paper Address?

The "discrepancy problem" involves assigning binary values (+1 or -1) to elements to minimize the maximum "discrepancy" across a collection of sets. This problem has deep connections to various fields, including mathematics and theoretical computer science. While a theoretical upper bound on discrepancy exists (O(√N) for M=O(N) sets), finding an efficient algorithm to achieve this bound was a long-standing challenge, only recently solved by Bansal. However, Bansal's algorithm provides a worst-case guarantee. This paper tackles a crucial question: can we do better if the optimal discrepancy for a specific instance is very small (e.g., zero)? They show that, computationally, we cannot efficiently find solutions much better than the general worst-case guarantee, even if a perfect solution exists. This implies that Bansal's algorithm is, in a sense, "tight" in terms of computational hardness. They also extend this hardness result to set systems with bounded shatter functions, showing that existing bounds are also tight in this restricted setting.

Methods

The core of the paper's contribution lies in a novel composition technique. They construct new, larger set systems by combining existing "high discrepancy" set systems with instances of the MAX-2-2-SET-SPLITTING problem. This problem is known to be NP-hard to distinguish between "splittable" (perfectly balanced) and "unsplittable" instances.

Here's a breakdown of the approach:

  • MAX-2-2-SET-SPLITTING Reduction: They leverage the NP-hardness of MAX-2-2-SET-SPLITTING, where the goal is to assign binary values to elements to maximize the number of "split" sets (where the sum of assigned values is zero). They show it's hard to distinguish between instances where all sets can be split and instances where a significant fraction must remain "unsplit."
  • Hadamard Matrices (for general case): For general set systems, they use Hadamard matrices to construct high-discrepancy instances. By composing these with MAX-2-2-SET-SPLITTING instances, they amplify the zero-vs-non-zero discrepancy gap, proving that it's NP-hard to distinguish between zero discrepancy and Ω(√N) discrepancy.
  • Halfspace Systems (for bounded shatter function): For set systems with polynomially bounded shatter functions (relevant in computational geometry and learning theory), they use systems of halfspaces as their high-discrepancy building blocks. Again, composition with MAX-2-2-SET-SPLITTING allows them to prove tight hardness results for this specific class of set systems.
  • Key Lemma (Lemma 3.1): A crucial lemma, adapted from Chazelle, establishes a lower bound on the norm of a vector multiplied by a matrix derived from a Hadamard matrix and an all-ones matrix. This lemma is instrumental in showing how the discrepancy of the MAX-2-2-SET-SPLITTING instance translates to the discrepancy of the constructed set system.

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness results and constructs artificial instances rather than evaluating on existing datasets.

Key Insights and Ideas

  • Fundamental Limits of Efficiency: The most significant insight is that even if a perfect solution (zero discrepancy) exists for a set system, efficient algorithms cannot guarantee finding a solution significantly better than the general worst-case bound (o(√N)). This implies that current algorithmic approaches are likely near-optimal in terms of computational complexity for general set systems.
  • Composition as a Powerful Hardness Tool: The paper demonstrates the power of composing known NP-hard problems (like MAX-2-2-SET-SPLITTING) with specific structures (Hadamard matrices, halfspaces) to prove hardness for new problem classes. This technique is generalizable.
  • Tightness of Existing Bounds: The results confirm that the theoretical upper bounds for discrepancy (both general and for bounded shatter functions) are not just theoretical curiosities but reflect inherent computational limitations.
  • Discrepancy of Zero vs. Near-Zero: The hardness results specifically target the gap between zero discrepancy and a small, non-zero discrepancy (Ω(√N) or Ω(√t)). This is a critical distinction for understanding the practical implications of these hardness results.

Key Results

  • Main Theorem (Theorem 1.1): It is NP-hard to distinguish between set systems on N elements with discrepancy zero and those with discrepancy Ω(√N). This implies that no efficient algorithm can find a coloring with discrepancy o(√N) if the optimal discrepancy is zero.
  • Theorem 2.1: For M × N matrices with M=O(N), it is NP-hard to distinguish between cases where D₂(A) = 0 and D₂(A) > Ω(N²).
  • Theorem 5.1: For set systems with polynomially bounded shatter functions (πs(s) = O(sd)), it is NP-hard to distinguish between discrepancy zero and Ω(N¹/²⁻¹/²ᵈ). This shows that Matoušek's upper bounds for such systems are tight.
  • Theorem 4.1: For M × N matrices with M=O(N) and columns with at most t 1's, it is NP-hard to distinguish between D∞(A) = 0 and D∞(A) ≥ Ω(√t).

Limitations and Future Work

  • Focus on NP-Hardness: The paper establishes NP-hardness, which is a strong theoretical limitation. However, it doesn't preclude the existence of approximation algorithms that might perform well in practice or for specific types of instances not covered by the hardness proofs.
  • Specific Constructions: The hardness proofs rely on specific constructions (Hadamard matrices, halfspaces). While the paper suggests the framework is general, applying it to other restricted set systems might require tailoring these constructions.
  • Future Work: The authors suggest that their general framework could be applied to other restricted set systems. The paper's approach of composing known hard problems with specific structures is a promising avenue for future research in proving hardness for various computational problems. The paper also opens the door to exploring whether there are specific structural properties of set systems that would allow for efficient algorithms to achieve better-than-worst-case discrepancy guarantees.

Summary updated

BibTeX
@inproceedings{charikar2011tight,
  author = {Moses Charikar and Alantha Newman and Aleksandar Nikolov},
  title = {{Tight Hardness Results for Minimizing Discrepancy}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.124},
}
Figure