TECH Signal 392
Bansal and Jiang report near-constant discrepancy bound, first major advance on Komlós conjecture in 30 years
↗
Theoretical computer scientists Nikhil Bansal and Haotian Jiang found a new upper bound on combinatorial discrepancy that grows so slowly with dimension it nearly matches the constant predicted by the Komlós conjecture, the first significant progress on the problem since 1998.
The result brings the field close to resolving a decades-old open problem in discrepancy theory, and the algorithmic technique used may carry over to resource-allocation problems in operations research, physics, and machine learning. If the conjecture holds, it would mean that splitting objects into two balanced groups is always achievable regardless of how many attributes you track.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
The Komlós conjecture predicts that discrepancy when dividing objects into two groups never exceeds a universal constant, independent of the number of dimensions.
Bansal and Jiang's new bound changes so slowly with dimension that it is only a hair away from constant, improving on a 1998 result that still depended strongly on dimension.
The work has not fully proven the conjecture but has shifted researchers toward believing it is true, and the novel algorithmic approach may apply beyond discrepancy theory.
THE CLUSTER