On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation
Abstract
Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure χ̅A*. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix A through the condition number χ̅A. Monteiro-Tsuchiya (2003) defined the optimal condition number χ̅A* as the maximum χ̅AD achievable over all positive diagonal column rescalings D. Dadush et al.\ (2024) introduced the optimal circuit imbalance measure κW*, which serves as a lower bound for χ̅*A. Instances with artificially large optimal circuit imbalance measures κW* can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure κW* grows exponentially in the number of approximation steps. Since κW* lower bounds χ̅A*, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.
Related
- Harmonic analysis and circuit approximation of Sobolev functions on quantum input spaces
- Quantitative non-Gaussian and Gaussian approximation for exponential random graphs in the single-phase critical regime
- Discontinuous Galerkin Approximation to a Class of Strongly Damped Wave Equations with Uniform Exponential Decay
- Limiting Behavior of a Class of Hermitian Yang--Mills Metrics, II: Exponential Approximation
- Approximation by short exponential sums with geometric error decay based on Gauss quadrature
BibTeX
@misc{bondar2026exponential,
title = {{On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation}},
author = {Jonah Bondar and Stephen Vavasis},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.12550},
eprint = {2608.12550},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.12550},
}
RIS
TY - UNPB
TI - On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation
AU - Jonah Bondar
AU - Stephen Vavasis
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.12550
UR - https://arxiv.org/abs/2608.12550
AB - Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure χ̅_A^*. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix A through the condition number χ̅_A. Monteiro-Tsuchiya (2003) defined the optimal condition number χ̅_A^* as the maximum χ̅_AD achievable over all positive diagonal column rescalings D. Dadush et al.\ (2024) introduced the optimal circuit imbalance measure κ_W^*, which serves as a lower bound for χ̅^*_A. Instances with artificially large optimal circuit imbalance measures κ_W^* can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure κ_W^* grows exponentially in the number of approximation steps. Since κ_W^* lower bounds χ̅_A^*, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.
ER -