On the discrepancy of random low degree set systems

Nikhil Bansal, Raghu MekaRandom Struct. Algorithms 2018 · DOI · OpenReview

TL;DR

This paper tackles the problem of minimizing the discrepancy of random set systems, which has applications in areas like approximation algorithms and optimization. The authors provide a tight bound of $O(\sqrt{t})$ for the expected discrepancy, improving upon previous results and covering all regimes of system parameters. This is achieved through a novel combination of techniques, including a reduction to a smaller system and a refined partial coloring algorithm.

What Problem Does This Paper Address?

The paper focuses on the discrepancy of set systems. In simple terms, imagine you have a collection of sets, and you want to color the elements of these sets with two colors (say, +1 and -1) such that each set is as "balanced" as possible between the two colors. The discrepancy of a set measures how far it is from being perfectly balanced. The discrepancy of the entire system is the minimum possible maximum imbalance across all sets, over all possible two-colorings.

A key question in this field is to understand this discrepancy for random low-degree set systems. Specifically, the authors consider a model where each of $n$ elements belongs to exactly $t$ randomly chosen sets out of $m$ total sets. Previous work by Ezra and Lovett established bounds of $O(\sqrt{t \log t})$ for $n \le m$ and $O(1)$ for $n \gg mt$. However, a tight bound of $O(\sqrt{t})$ for all parameter regimes was still open, especially for the case where $n \approx m$. This is particularly challenging because methods that work well for $n \le m$ (like the Lovász Local Lemma) often fail when $n$ is much larger than $m$.

Methods

The paper's core contribution lies in a two-pronged approach:

  1. Reduction to a smaller system: The authors first show that the problem for a general system with $n$ elements can be reduced to a system with $k = O(m \log^2 m)$ elements, with high probability. This reduction involves using the Beck-Fiala theorem to color a subset of elements and then leveraging LP duality and a counting argument to handle the remaining elements with fractional colors. This step is crucial for extending results from the $n \le m$ regime to the general case.
  2. Refined Partial Coloring: The second key technique is a sophisticated partial coloring algorithm. This algorithm, inspired by Lovett and Meka's work, iteratively colors variables to -1 or +1 while maintaining a low discrepancy. The novelty here is in adapting this procedure to the random set system model. The authors carefully analyze the properties of random matrices to ensure that the partial coloring process doesn't accumulate too much discrepancy, especially when the number of elements $k$ is large relative to $m$. This involves intricate probabilistic arguments and Chernoff bounds.

Datasets

Not discussed in the paper. The paper deals with theoretical results on random models rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tight $O(\sqrt{t})$ bound achieved: The most significant insight is the derivation of a tight $O(\sqrt{t})$ bound for the expected discrepancy in random low-degree set systems, valid across all parameter regimes ($n, m$). This resolves a long-standing open problem.
  • Bridging different regimes: The reduction technique is a powerful idea that allows leveraging existing results for smaller systems to solve problems for larger, more complex ones. This is a common theme in theoretical computer science, but its application here to connect different discrepancy regimes is noteworthy.
  • Exploiting randomness: The analysis heavily relies on the random nature of the set system. The authors show how to use probabilistic tools (like Chernoff bounds and properties of random matrices) to control the discrepancy, which is not possible with deterministic methods.
  • The role of $t = (\log \log m)^2$: The condition $t = (\log \log m)^2$ arises naturally from the interplay between the reduction step (which requires $k = O(m \log^2 m)$) and the partial coloring step. This condition highlights how the complexity of the problem scales with the degree $t$ and the number of sets $m$.

Key Results

  • Theorem 1: For a random set system with $n$ elements, $m$ sets, and degree $t$, the expected discrepancy is $O(\sqrt{t})$, provided $t = \Omega((\log \log m)^2)$. This bound is tight.
  • Theorem 2: Establishes a condition for a random matrix $A$ of size $m \times k$ to satisfy $2t\mathbb{B}_\infty \subseteq P$, where $P$ is the set of discrepancy vectors achievable by fractional colorings. This requires $k = O(m \log^2 m)$ and is crucial for the reduction step.
  • Theorem 3: Shows that for a random $m \times k$ matrix with degree $t$, if $t = \Omega(\log^2(ek/m))$, the discrepancy is $O(\sqrt{t})$ with high probability. This is the core result of the partial coloring part.

Limitations and Future Work

  • Condition on $t$: The main result requires $t = \Omega((\log \log m)^2)$. The authors mention that their methods might be improved to handle $t = \Omega(\log \log m)$ with more complex algorithms, but $t \approx \log \log m$ appears to be a natural bottleneck for their current techniques.
  • Algorithmic implementation: While the paper proves the existence of such a coloring, it also states that the algorithm can be implemented in randomized polynomial time. However, the specific details of the polynomial time implementation are not elaborated upon in the provided text.
  • Non-random systems: The results are specific to random set systems. Extending these tight bounds to general deterministic set systems remains an open and challenging problem.
  • Higher discrepancy bounds: The paper mentions that other groups have obtained $O(1)$ discrepancy for random low-degree systems in regimes where $n \gg m^2$ or $n \gg m^3$ using Fourier analytic methods, which are non-algorithmic. It would be interesting to see if algorithmic versions of these results can be developed.

Summary updated

Abstract

Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Love...
BibTeX
@article{bansal2018discrepancy,
  author = {Nikhil Bansal and Raghu Meka},
  title = {{On the discrepancy of random low degree set systems}},
  journal = {Random Struct. Algorithms},
  year = {2018},
  doi = {10.1002/rsa.20935},
}
Figure