Smoothed Analysis of Interior-Point Algorithms: Condition Number
<|reference_start|>Smoothed Analysis of Interior-Point Algorithms: Condition Number: We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).<|reference_end|>
@article{dunagan2003smoothed,
    title={Smoothed Analysis of Interior-Point Algorithms: Condition Number},
    author={John Dunagan, Daniel A. Spielman, and Shang-Hua Teng},
    journal={arXiv preprint arXiv:cs/0302011},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0302011},
    primaryClass={cs.DS cs.NA}
}