Loading Web-Font TeX/Math/Italic
| 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.