| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

1. Open problems

    1. Komlós conjecture


      Add remark

      Problem 1.05.

      There is a universal constant $c>0$ s.t. for every $v_1,v_2,...,v_n \in \mathbb{B_2}^d$, there exist signs $\epsilon_1,...,\epsilon_n\in \{-1,1\}$ s.t. $|| \sum_{i=1}^n \epsilon_i v_i||_{\infty} \le c$
          $c=O(\sqrt{\log min\{d,n\}})$ was given by [Banaszczyk’98] and [Naor’05]

        • Constructive Komlós


          Add remark

          Problem 1.1.

          Find a polynomial time algorithm to find the signs above.
              $O(\log min\{d,n\})$ [Bansal’10, Lovett-Meka’14, Rothvoss’15]

            • Beck-Fiala conjecture and making it constructive


              Add remark

              Problem 1.15.

              Given a set system $(V,\mathcal{S})$ with $V=[n]$, $\mathcal{S}=S_1,...,S_m$. Each $i\in V$ occurs in at most $t$ sets from $\mathcal{S}$. Then there is a coloring to the elements of $V$ achieving a discrepancy of $O(\sqrt{t})$. Komlós conjecture implies this by treating the incidence vector of each $i\in V$ as a vector and scaling it down by $\sqrt{t}$.
                  A $2t-1$ guarantee which is also algorithmic was given by Beck-Fiala. Recently, [Bukh] gave a guarantee of $2t-\log^*t$. Banaszczyk’s result implies a bound of $O(\sqrt{t\log m})$ but is non-constructive. Other algorithmic guarantees are $O(\sqrt{t}\log n)$ [Bansal’10, Lovett-Meka’12, Rothvoss’15] and $O(\sqrt{t\log n\log|S_j|})$ [Bansal-Garg’15].

                • Beck-Fiala for random set system


                  Add remark

                  Problem 1.2.

                  [Esther Ezra, Shachar Lovett] Each element $i\in [n]$ lies in $t$ randomly selected sets from $\mathcal{S}$.
                      They show that when $m\ge n$, hereditary discrepancy of the set system is $O(\sqrt{t\log t})$ whp. When $n\ge m^t$, hereditary discrepancy is $O(1)$. An open question is to explore this setting for the remaining range of parameters i.e. when $n^{1/t} < m < n$.

                    • Hypercube set system


                      Add remark

                      Problem 1.25.

                      [Shachar Lovett] Given a set system where the elements are the vertices of the hypercube $\{0,1\}^n$. Corresponding to each vertex $v$, there is a set $S_v$ which is generated by picking a random subset of the neighbours of $v$ in the hypercube. What is the discrepancy of this set system?
                          If instead of picking a random subset of the neighbours, $S_v$ was the full set of neighbours of $v$, then there is an easy solution giving discrepancy 1. Color each vertex depending on the parity of its first $n/2$ bits.

                        • Discrepancy of permutations


                          Add remark

                          Problem 1.3.

                          a) discrepancy of k-permutations

                          For $k=3$, $[NNN'12]$ showed a lower bound of $\Omega(\log n)$ where $n$ is the number of elements in the ground set. For general $k$, we know that the answer lies in $[\sqrt{k}+\log n,\sqrt{k}\log n]$. An open question is to clsoe this gap.

                          b) discrepancy of k-random permutations

                          A lower bound of $\Omega(\sqrt{k})$ is known.

                            • Matrix Spencer


                              Add remark

                              Problem 1.35.

                              Given matrices $A_1,...,A_n \in\mathbb{R}^{n\times n}$ satisfying $||A_i||_{op} \le 1$ where $||.||_{op}$ is the operator norm of matrices. Do there exists signs $\epsilon_1,...,\epsilon_n\in\{-1,1\}$ s.t. $||\sum_{i=1}^n\epsilon_i A_i || =O(\sqrt{n})$.
                                  We can assume that the matrices are symmetric. Matrix chernoff gives a bound of $O(\sqrt{n\log n})$.

                                • Steinitz conjecture


                                  Add remark

                                  Problem 1.4.

                                  Given vectors $v_1,...,v_n\in\mathbb{R}^d$ and a norm $X$ satisfying $\sum_{i=1}^n v_i=0$ and $||v_i||_X\le 1$ for all $i$. Define $S_n(X,d)=min_{\pi\in S^n}max_{k=1,...,n}|| \sum_{i=1}^k v_{\pi(i)}||_X$ where $S^n$ is the set of all permutations of $[n]$. Let $S(X,d)=sup_n S_n(X,d)$. Then, $S(X,d) =O(\sqrt{d})$.
                                      i) Sevastiyanov showed $S(X,d) \le d$. For $X$ a symmetric norm, Banaszczyk improved this to $d-\frac{1}{d}$

                                  ii) If $X=l_p$ for $1< p < 2$, $S(X,d) =\Omega(d)$

                                  iii) For $X=l_2$, Banaszczyk’13 gave a bound of $O(\sqrt{d}+\sqrt{\log n})$. A lower bound of $\sqrt{d}$ is known here.

                                  iv) It is known that $S(X,d) \ge \alpha(X,X,d)$ [Chobanyan] (refer to vector balancing problem below for definition of $\alpha$) . Given in Barany’s epic document. Moreover, for a given set of vectors $v_1,..,v_n$ , given a signing of it achieving discrepancy $\alpha$, we can recover a permutation achieving a guarantee of $\alpha$ in the Steinitz setting [Harvey].
                                    1. Remark. An algorithmic guarantee of $\sqrt{d}log\,n$ was worked upon in the workshop.

                                        • Vector Balancing

                                              Let $X,Y$ be norms on $\mathbb{R}^d$. Given vectors $v_1,...,v_n\in \mathbb{R}^d$ satisfying $||v_i||_X\le 1$ for all $i$. We want to find signs $\epsilon_i \in \{-1,1\}$ to minimize $|| \sum_{i=1}^n\epsilon_iv_i ||_Y$. Call this the discrepancy of the vectors. Define $\alpha_n(X,Y,d)$ as the maximum of this discrepancy over all choice of $n$ vectors satisfying $||v_i||_X\le 1$ and $\alpha(X,Y,d) =sup_n \alpha_n(X,Y,d)$. Banaszczyk proved $\alpha(X,Y,d) \ge \sqrt{d}(\frac{vol(B_X)}{vol(B_Y)})^{1/d}$ where $B_X,B_Y$ are the unit balls of the corresponding norms.

                                          Add remark

                                          Problem 1.5.

                                          Is this lower bound also an upper bound for $\alpha(X,Y,d)$ upto $\log d$ factors?
                                            1. Remark. [Sasho Nikolov] In fact, this lower bound can be too small by a factor of $\sqrt{d}$, for example when $X = Y = \ell_1^d$. However, the following stronger lower bound may in fact also be an upper bound, up to logarithmic factors: $\max_{k = 1}^{d}\max_{W: \mathrm{dim}(W) = k} \min_{B_Y \cap W \subseteq E} \sqrt{d} \frac{vol(E)^{1/d}}{vol(B_X \cap W)^{1/d}}$, where the maximum is over subspaces $W$ of dimension $k$ and the minimum is over ellipsoids $E$ containing $B_Y \cap W$.
                                                • Remark. [Sasho Nikolov] The formula above should be $\max_{k = 1}^d \max_{W: \mathrm{dim}(W) = k} \min_{E: B_X \cap W \subseteq E} \sqrt{k} \frac{vol(E)^{1/k}}{vol(B_Y \cap W)^{1/k}}$.

                                                    • Tusnady’s problem


                                                      Add remark

                                                      Problem 1.65.

                                                      Let $d_n$ be the discrepancy of $n$ points in $\mathbb{R}^2$ wrt all alix-aligned rectangles i.e. the set system comprises of all axis-aligned rectangles in $\mathbb{R}^2$ as sets, maximised over all choices of $n$ points. Tusnady’s problem then asks for the exact value of $d_n$.

                                                      We can also ask for the same question in $\mathbb{R}^d$.
                                                          In $\mathbb{R^2}$, we know a lower bound of $O(\log n)$ on $d_n$ and an upper bound of $O(\log^{2.5}n)$. In $\mathbb{R}^d$, we know that $d_n\in[\log^{d-1}n,log^{d+1/2}n]$

                                                        • Beating LLL


                                                          Add remark

                                                          Problem 1.7.

                                                          Consider a matrix where both columns are rows are t-sparse. LLL gives a discrepancy bound of $O(\sqrt{t\log t})$ here. If we assume the stronger property that every pair of rows intersect in at most one element, can we get a $O(\sqrt{t})$?

                                                            • Hardness of Komlos


                                                              Add remark

                                                              Problem 1.75.

                                                              Can we prove some hardness statement about finding a coloring achieving Komlos guarantee or the Banaszczyk discrepancy guarantee?

                                                                • Reverse Banaszczyk-type problems


                                                                  Add remark

                                                                  Problem 1.8.

                                                                  Say that a convex body $K$ has property B if for any set of vectors of length no more than $c$ (some small constant), there exists a signing of them s.t. this signed sum lies inside $K$.

                                                                  What is the convex body with the smallest gaussian volume which has property $B$?
                                                                    1. Remark. [Daniel Dadush] During the workshop it was shown that if $K$ has property $B$, then $\mathbb{E} \|G\|_K = (\log n)^O(1)$, where $G$ is a standard Gaussian random vector.

                                                                        • Polysize list of colorings


                                                                          Add remark

                                                                          Problem 1.85.

                                                                          Is there a list of colorings of polynomial size such that for any subset of the columns, one of these colorings gives it a discrepancy of O(h), where $h$ is the hereditary discrepancy?
                                                                              This was answered in the negative. Counterexample is a simple set system comprising of $\sqrt{n}$ disjoint rows of size $\sqrt{n}$ each.

                                                                              Cite this as: AimPL: Hereditary discrepancy and factorization norms, available at http://aimpl.org/hereddiscrep.