Solution to Komlós conjecture was announced recently:
arxiv.org/pdf/2609.11189
I have not read the proof yet, but will do so when I have some time. Meanwhile, I want to briefly mention an implication for neural networks that does not seem to be discussed in the paper.
Neural networks repeatedly perform matrix multiplications, in particular products Wx, where W can be an astronomically large matrix of weights w_ij and x is a vector of activations.
Storing and moving high-precision weights and performing these multiplications require memory, time and energy. One therefore wants to round the weights to a grid hℤ, where h is a super small positive number, while keeping the outputs approximately unchanged.
This is called quantization. Its connection with discrepancy theory and the Komlós conjecture was already discussed by Lybrand and Saab:
arxiv.org/abs/2010.15979
For each weight w = w_ij, consider the two neighboring grid points:
h⌊w/h⌋ and h⌈w/h⌉ (floor and ceiling).
Can we coordinate these choices so that the outputs Wx remain almost unchanged across many inputs x simultaneously?
More precisely, fix inputs x⁽¹⁾, …, x⁽ᵐ⁾, and define
L = maxⱼ √(∑ₛ |xⱼ⁽ˢ⁾|²),
We seek a rounded weight matrix H such that
maxₛ ‖Hx⁽ˢ⁾ − Wx⁽ˢ⁾‖_∞ ≤ C h L,
where C is an absolute constant, independent of the dimensions, weights and inputs.
There are two questions:
1. Does such a rounding exist?
2. what is the reasonable in time algorithm doing this?
If the announced proof is correct, the answer to the first question is yes, with C = 3√(2π).
The paper does not provide a polynomial-time algorithm achieving this guarantee.
P.S. This controls computations Wx on specified inputs x. It does not by itself guarantee accuracy on unseen prompts or control accumulated errors throughout a transformer. It establishes that simultaneous output preservation at lower precision is possible under the stated bound.