
1. Open problems

1. Komlós conjecture

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 Komlós

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

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})$. Komló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

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

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

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

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

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.

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}}$.

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

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

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

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

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.