The Komlós problem asks for signs $\varepsilon\in\{-1,1\}^n$ with $\|A\varepsilon\|_\infty$ bounded by an absolute constant whenever the columns of $A\in\mathbb R^{m\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic $O(\sqrt t)$-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most $t$ sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.
Nan Lu, Ethan Lee, Ruicheng Ao, David Simchi-Levi, Junwei Lu
We study offline inference for the optimal value in reinforcement learning under finite state and action spaces. Two new nuisances are derived as fixed points of a self-induced Bellman equation, in which we approximate the maximum Bellman operator by its softmax correspondence. We propose a debiased estimator through the Neyman orthogonality and establish its asymptotic normality under diverging horizons even when the behavior policy changes with time, as long as the nuisances have the statistical rates that can be achieved by many machine learning methods. We provide a concrete estimating procedure for these nuisances and show they can lead to valid inference. Synthetic experiments validate the numerical performance of our inference method, and we implement it in real-life decision-making problems, including bike repositioning and AI agentic tool use.
Xiaoan Xu, Jesus A. De Loera, Ethan X. Fang, Junwei Lu, Luze Xu
Classical optimization and learning-guided search offer complementary approaches to open problems in discrete mathematics, but their outputs are difficult to compare when search spaces, validity checks, and stopping rules differ. We present \emph{RadonBench}, a benchmark for constructing maximum-cardinality Radon-free lattice configurations: finite subsets of $\mathbb{Z}^d$ admitting no integral Radon partition. It remains open whether Radon-free configurations with $11$ points in $\mathbb{Z}^3$ or $21$ points in $\mathbb{Z}^4$ are possible. If they exist, they would improve the corresponding lower bounds on the integer Radon numbers. We compare exhaustive extension, greedy local search, PatternBoost, AlphaZero, and AlphaEvolve. All outputs use one success predicate: a convex target-sized configuration succeeds exactly when its number of integral Radon points is zero. PatternBoost and AlphaZero construct verified Radon-free configurations of sizes $10$ and $20$, one point short of the respective targets; AlphaZero's best convex target terminals have two integral Radon points in both dimensions. Exhaustive extension over fixed seeds and declared finite search boxes likewise reaches a minimum of two integral Radon points. Greedy local search and AlphaEvolve each produce target-sized near misses with one integral Radon point. No audited run reaches zero. These results establish reproducible near-miss baselines over explicitly scoped search domains.