Sharp Integrality Gaps in Calibration Distance
Abstract
We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absolute-change cost. We sharpen the offline comparison C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem 2) to the sharp worst-case order Theta(T^(1/3)). If Delta_T is the supremum of C - L over length-T inputs, then T^(1/3)/1000 <= Delta_T <= 41T^(1/3) for T >= 216. The upper bound holds for every input, while each T >= 216 has a rational lower-bound input. For every input with m distinct forecasts, C <= L + m, and the unrestricted-sample worst-case sparse order is Theta(m). For rational forecasts and accuracy, with binary-encoded multiplicities of separately assignable unit identities, a grid-free polynomial-bit-time procedure returns B <= L <= U, U - B < eta, and an exactly calibrated compact repair of cost at most U + m <= L + m + eta.
Related
- Covariance-Rank Rounding and a Sharp Integrality Gap for a Matroid Edge-Coverage Moment Lift
- The Earth Moves, But So Does the Bias: Systematic Upward Bias of the Wasserstein (Earth Mover's) Distance and Permutation-Based Null Calibration
- Very sharp distance and range transitions for random walk bridges on Ramanujan graphs
- Interpretable intrinsic dimension estimation through componentwise calibration of distance and angle
- Sharp parameter gaps for quantized Mabuchi energies and cscK metrics
BibTeX
@misc{wang2026sharp,
title = {{Sharp Integrality Gaps in Calibration Distance}},
author = {Zinan Wang and Xinhao Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05679},
eprint = {2610.05679},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05679},
}
RIS
TY - UNPB
TI - Sharp Integrality Gaps in Calibration Distance
AU - Zinan Wang
AU - Xinhao Yang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05679
UR - https://arxiv.org/abs/2610.05679
AB - We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absolute-change cost. We sharpen the offline comparison C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem 2) to the sharp worst-case order Theta(T^(1/3)). If Delta_T is the supremum of C - L over length-T inputs, then T^(1/3)/1000 <= Delta_T <= 41T^(1/3) for T >= 216. The upper bound holds for every input, while each T >= 216 has a rational lower-bound input. For every input with m distinct forecasts, C <= L + m, and the unrestricted-sample worst-case sparse order is Theta(m). For rational forecasts and accuracy, with binary-encoded multiplicities of separately assignable unit identities, a grid-free polynomial-bit-time procedure returns B <= L <= U, U - B < eta, and an exactly calibrated compact repair of cost at most U + m <= L + m + eta.
ER -