15
$\begingroup$

Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find weights $w_i\in\{-1,1\}$ such that $\left\lVert w_1v_1+\cdots+w_nv_n\right\rVert _{\infty}<K$.

I would like to ask what the current state of this conjecture is? Is it true that the best result towards this conjecture is that for fixed $d$ one can show the latter statement with $K=K(n)\approx \log n$?

$\endgroup$
7
$\begingroup$

For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$.

Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ balls of radius $\frac{1}{2}$, for some absolute constant $C$. Let $v_1,\dots,v_n$ be $n$ vectors in $\mathbb{R}^d$ of norm at most $1$. If $n>2C^d$, then one can find $v_i,v_j$, for some $i<j$, belonging to the same ball of radius $\frac{1}{2}$; in particular $||v_i-v_j||_2 \leq 1$. By considering, the finite list $v_i- v_j, v_1,\dots,\hat{v_{i}},\dots,\hat{v_j}, \dots v_n$, one reduces to the case of $n-1$ vectors of norm at most $1$. Iterating this process, one reduces to the case $n \leq 2C^d$. Then one applies Banaszczyk's result to get a bound $O(\log^{\frac{1}{2}} 2C^{d}) = O(\sqrt{d})$.

$\endgroup$
12
$\begingroup$

As far as I know, the state of the art is that one can actually achieve $K=K(n)=O(\log^{\frac{1}{2}} n)$ independent of the dimension $d$. Moreover, one can actually find the weights $w_i$ via an efficient randomized algorithm. This matches the best non-constructive bound due to Banaszczyk. See this paper of Bansal, Dadush and Garg.

$\endgroup$
1
  • 1
    $\begingroup$ I think this might have been derandomized (at least a bit). $\endgroup$
    – Mr.
    Jul 11 '17 at 4:26
-1
$\begingroup$

There is a preprint just posted that claims to disprove it: https://www.preprints.org/manuscript/201902.0059/v1. They show that there is a lower bound for any n which diverges as n increases.

$\endgroup$
3
  • $\begingroup$ What do you mean by "any n which diverges as n increases?" $\endgroup$
    – Amir Sagiv
    Feb 6 '19 at 14:05
  • 4
    $\begingroup$ The allleged construction is in "Conclusion" section. I cannot make sense out of it. There are other worrying signs that undermine paper's credibility: poor English, written in Word, it appears in an unusual place, main results that are claimed are computations for low dimensions (which are less interesting than disproof of the conjecture of Komlos). $\endgroup$
    – Boris Bukh
    Feb 6 '19 at 14:54
  • 2
    $\begingroup$ An additional data point, which I do not know how to interpret: according to preprints.org/about#key-staff, Martyn Rittman is the "director" of the server that hosts this paper. $\endgroup$
    – Boris Bukh
    Feb 6 '19 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.