Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity
Abstract
Greedy box splitting reads gradient signs at the centre and retains one smaller box. Its summable travel budget makes an incorrect exclusion irreversible. We determine when this geometry is safe. Halving is minimax optimal in the sign-vector oracle model on a coordinatewise sign-consistent class that need not be convex. A dimensionless sign defect yields a sharp scalar envelope, attained by one smooth convex potential; a three-dimensional trajectory ends farther from the target than its initial radius. For quadratics, universal convergence with aspect w and contraction beta holds exactly when the weighted absolute row defect is at most $(2 β- 1)$. Perron weights minimise this defect. Adaptive half-sizes avoid initial enlargement and, under persistent error, converge to an exact capped fixed-point limit. For binary comparisons, an independent probe fraction q permits universal localisation on common-target monotone sections exactly when (q ≤ 2 β− 1); coupled probes give the sharp threshold 2/3. Matching information bounds distinguish comparisons from sign-vector queries. Error bands give finite-time guarantees and sharp residual floors. Extensions and reproducible experiments identify the assumptions and costs of freezing, smoothing, voting, multistart and random-matrix certificates.
Related
- Two-parameter classes of exactly solvable quantum systems
- On the number of conjugacy classes of finite solvable groups of order divisible by p2
- Splitting Brauer classes by genus one curves over number fields
- Splitting torsion classes in higher homological algebra
- Thurston norm, polytopes and splitting complexity
BibTeX
@misc{anikin2026greedy,
title = {{Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity}},
author = {Anton Anikin and Alexander Gornov and Tatiana Zarodnyuk and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37444},
eprint = {2609.37444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37444},
}
RIS
TY - UNPB
TI - Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity
AU - Anton Anikin
AU - Alexander Gornov
AU - Tatiana Zarodnyuk
AU - Alexander Gasnikov
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37444
UR - https://arxiv.org/abs/2609.37444
AB - Greedy box splitting reads gradient signs at the centre and retains one smaller box. Its summable travel budget makes an incorrect exclusion irreversible. We determine when this geometry is safe. Halving is minimax optimal in the sign-vector oracle model on a coordinatewise sign-consistent class that need not be convex. A dimensionless sign defect yields a sharp scalar envelope, attained by one smooth convex potential; a three-dimensional trajectory ends farther from the target than its initial radius. For quadratics, universal convergence with aspect w and contraction beta holds exactly when the weighted absolute row defect is at most $(2 β- 1)$. Perron weights minimise this defect. Adaptive half-sizes avoid initial enlargement and, under persistent error, converge to an exact capped fixed-point limit. For binary comparisons, an independent probe fraction q permits universal localisation on common-target monotone sections exactly when (q ≤ 2 β− 1); coupled probes give the sharp threshold 2/3. Matching information bounds distinguish comparisons from sign-vector queries. Error bands give finite-time guarantees and sharp residual floors. Extensions and reproducible experiments identify the assumptions and costs of freezing, smoothing, voting, multistart and random-matrix certificates.
ER -