An amazing result giving the first improvement in the “Komlós combinatorial discrepancy problem” in almost 30 years (and it wasn’t done with AI).
Given N unit-length vectors in R^d, you want to partition them into two subsets, A and B, so the sum of the vectors in A and those in B differ in all of their components by as little as possible.
The new result, from Nikhil Bansal and Haotian Jiang, describes an algorithm that bounds the difference by O((log N)^{1/4}), improving on a previous result of O((log N)^{1/2}). János Komlós conjectured that the true bound is independent of N.
Great Quanta article covering the history of the problem:
https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/
Paper from Bansal and Jiang:
https://arxiv.org/abs/2508.03961
Greg Egan
npub12c…gd38p
2026-08-24 10:24:25 UTC
Author Public Key
npub12cuzzqzv8e8y7na77a9zv47mx2v6pec60qs5h7takzmv5p0mw0fsmgd38pSeen on
wss://relay.momostr.pinkPublished at
2026-08-24 10:24:25 UTCEvent JSON
{
"id": "2adc3987620ed18b8e505735638590471acfa6e381eee07549abe16dc048282b",
"pubkey": "563821004c3e4e4f4fbef74a2657db3299a0e71a78214bf97db0b6ca05fb73d3",
"created_at": 1787567065,
"kind": 1,
"tags": [
[
"proxy",
"https://mathstodon.xyz/@gregeganSF/117149995208617612",
"web"
],
[
"proxy",
"https://mathstodon.xyz/users/gregeganSF/statuses/117149995208617612",
"activitypub"
],
[
"L",
"pink.momostr"
],
[
"l",
"pink.momostr.activitypub:https://mathstodon.xyz/users/gregeganSF/statuses/117149995208617612",
"pink.momostr"
],
[
"-"
]
],
"content": "An amazing result giving the first improvement in the “Komlós combinatorial discrepancy problem” in almost 30 years (and it wasn’t done with AI).\n\nGiven N unit-length vectors in R^d, you want to partition them into two subsets, A and B, so the sum of the vectors in A and those in B differ in all of their components by as little as possible.\n\nThe new result, from Nikhil Bansal and Haotian Jiang, describes an algorithm that bounds the difference by O((log N)^{1/4}), improving on a previous result of O((log N)^{1/2}). János Komlós conjectured that the true bound is independent of N.\n\nGreat Quanta article covering the history of the problem:\nhttps://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/\n\nPaper from Bansal and Jiang:\nhttps://arxiv.org/abs/2508.03961",
"sig": "9c5b401d143a978b66e92377d6bbe1f6ac9f8c88077d0176ea5b2a30ef79dd532458d3f6c3563d8ad482bde6ee79b651afe329c9fb614681a670169886c5424d"
}