Open Problems: Discrepancy Minimization and Rounding Heuristics for IP

Discrepancy Minimization:

Komlós and Beck-Fiala Conjecture:

The Komlós can be stated as follows: there exists a universal constant \(c>0\) s.t. for every \(v_1,v_2,...,v_t \in \mathbb{R}^n, \|v_i\|_2 \leq 1, \forall i \in [t]\), there exist signs \(\varepsilon_1,\dots,\varepsilon_t \in \{-1,1\}\) s.t. \(\|\sum_{i=1}^t \varepsilon_i v_i\|_\infty \leq c\). The best known bound of \( O(\log (\min \{n,t\})) \) was given by [Banaszczyk 98] and [Naor 05].
The Beck-Fiala conjecture is special case of the Komlós conjecture restricted to set systems. Precisely, given a a family of sets \(\mathcal{F} = \{S_1,\dots,S_m\}\) on \(n\) elements such, where no element appears in more than \(t\)-sets, the Beck-Fiala conjecture is that there always exists a coloring achieving discrepancy \(O(\sqrt{t})\). This follows from the Komlós conjecture by examining the incidence matrix of the set system \(M\), where \(M_{ij} = 1\) if element \(j\) is in set \(i\) and \(0\) otherwise. Here one would apply Komlós to the matrix \(M/\sqrt{t}\), noting that the columns now have \(\ell_2\) norm at most \(1\).
An interesting special case of the Beck-Fiala conjecture is for set systems where every set has size at most \(t\) and every element appears in at most \(t\) sets. In this case, using the Lovász local lemma, one can show a discrepancy bound of \(O(\sqrt{t \log t})\). Here it would be interesting to remove the \(O(\sqrt{\log t})\) dependence. The analogous restriction for the Kómlos conjecture is to work with a matrix \(M \in \mathbb{R}^{n \times n}\) whose rows and columns both have \(\ell_2\) norm at most \(1\). In this special case, the \(O(\sqrt{\log n})\) bound of [Banaszczyk 98] can already be recovered by analyzing the discrepancy of a uniformly random \(\{-1,1\}\) coloring. Nothing beyond the trivial random coloring bound is known in this setting.

Steinitz Conjecture:

For any sequence of vectors \(v_1,\dots,v_t \in \mathbb{R}^n\), \(\|v_i\|_\infty \leq 1, \forall i \in [t]\), such that \(\sum_{i=1}^t v_i = 0\), there exists a permutation \(\pi: [t] \rightarrow [t]\) such that \(\|\sum_{i=1}^k v_{\pi[i]}\|_\infty \leq O(\sqrt{n}), \forall k \in [t].\) The best known bound of \(\min \{n,\sqrt{n \log t}\}\) was given by [Grinberg, Sevastyanov 80] (first term) and [Banaszczyk 11] (second term).

Counterexamples to Discrepancy Conjectures:

Very little effort has been invested to try and build counterexamples to the many conjectures in discrepancy theory. An important exception is the beautiful work of Newman, Neiman and Nikolov in 2011 providing a counterexample of Beck's 3 permutations conjecture, linked here. Can one extend the techniques used in the above paper to give counterexamples to other conjectures?

Coloring in Input Sparsity Time:

For any of the known partial / full coloring algorithms (Lovett-Meka, Eldan-Singh, Gram-Schmidt, etc.), given a matrix \(A \in \mathbb{R}^{m \times n}\), can one produce a partial / full coloring of the columns of \(A\) in \(\widetilde{O}({\rm NNZ}(A))\) time?

Rounding Heuristics for IP:

Discrepancy in Practice:

Can one implement any of the known discrepancy algorithms and make them work in practice?

Structure of "Easy to Round" Instances:

Can one come up with non-trivial characterizations of what some easy to round instances look like? In particular, can one point to structured sparsity conditions, polyhedral considerations, or subdeterminant conditions (i.e. relaxations of TUness) that would imply that an instance is easy?

Other open problems we should mention? Please email your suggestions to Daniel Dadush (dndadush@gmail.com).