% refs.bib -- bibliography for "Deciding D-stability is coNP-hard" (BibTeX style plainurl).

@article{arrow1958,
  author  = {Arrow, Kenneth J. and McManus, Maurice},
  title   = {A Note on Dynamic Stability},
  journal = {Econometrica},
  volume  = {26},
  number  = {3},
  pages   = {448--454},
  year    = {1958},
  doi     = {10.2307/1907624}
}

@article{enthoven1956,
  author  = {Enthoven, Alain C. and Arrow, Kenneth J.},
  title   = {A Theorem on Expectations and the Stability of Equilibrium},
  journal = {Econometrica},
  volume  = {24},
  number  = {3},
  pages   = {288--293},
  year    = {1956},
  doi     = {10.2307/1911633}
}

@article{johnson1974,
  author  = {Johnson, Charles R.},
  title   = {Sufficient conditions for {D}-stability},
  journal = {Journal of Economic Theory},
  volume  = {9},
  number  = {1},
  pages   = {53--62},
  year    = {1974},
  doi     = {10.1016/0022-0531(74)90074-X}
}

@article{cain1976,
  author  = {Cain, Bryan E.},
  title   = {Real, $3\times 3$, {D}-stable matrices},
  journal = {Journal of Research of the National Bureau of Standards, Section B: Mathematical Sciences},
  volume  = {80B},
  number  = {1},
  pages   = {75--77},
  year    = {1976},
  doi     = {10.6028/jres.080B.013}
}

@article{cross1978,
  author  = {Cross, G. W.},
  title   = {Three types of matrix stability},
  journal = {Linear Algebra and its Applications},
  volume  = {20},
  number  = {3},
  pages   = {253--263},
  year    = {1978},
  doi     = {10.1016/0024-3795(78)90021-6}
}

@article{hershkowitz1992,
  author  = {Hershkowitz, Daniel},
  title   = {Recent directions in matrix stability},
  journal = {Linear Algebra and its Applications},
  volume  = {171},
  pages   = {161--186},
  year    = {1992},
  doi     = {10.1016/0024-3795(92)90257-B}
}

@article{kanovei1998,
  author  = {Kanovei, G. V. and Logofet, D. O.},
  title   = {{D}-stability of 4-by-4 matrices},
  journal = {Computational Mathematics and Mathematical Physics},
  volume  = {38},
  number  = {9},
  pages   = {1369--1374},
  year    = {1998},
  note    = {Translated from Zh. Vychisl. Mat. Mat. Fiz. 38(9) (1998) 1429--1435}
}

@article{impram2005,
  author  = {Impram, Serkan T. and Johnson, Russell and Pavani, Raffaella},
  title   = {The {D}-stability problem for $4\times 4$ real matrices},
  journal = {Archivum Mathematicum (Brno)},
  volume  = {41},
  number  = {4},
  pages   = {439--450},
  year    = {2005},
  note    = {MR 2195496, Zbl 1122.15003}
}

@article{kushel2019,
  author  = {Kushel, Olga Y.},
  title   = {Unifying Matrix Stability Concepts with a View to Applications},
  journal = {SIAM Review},
  volume  = {61},
  number  = {4},
  pages   = {643--729},
  year    = {2019},
  doi     = {10.1137/18M119241X},
  eprint  = {1907.07089},
  archivePrefix = {arXiv}
}

@misc{kushel2026,
  author  = {Kushel, Olga Y.},
  title   = {Recursive determinantal framework for testing {D}-stability. {I}},
  year    = {2026},
  eprint  = {2604.16526},
  archivePrefix = {arXiv},
  primaryClass  = {math.SP},
  doi     = {10.48550/arXiv.2604.16526}
}

@book{hornjohnson1991,
  author    = {Horn, Roger A. and Johnson, Charles R.},
  title     = {Topics in Matrix Analysis},
  publisher = {Cambridge University Press},
  address   = {Cambridge},
  year      = {1991},
  doi       = {10.1017/CBO9780511840371}
}

@book{logofet1993,
  author    = {Logofet, Dmitrii O.},
  title     = {Matrices and Graphs: Stability Problems in Mathematical Ecology},
  publisher = {CRC Press},
  address   = {Boca Raton, FL},
  year      = {1993}
}

@book{gantmacher1959,
  author    = {Gantmacher, F. R.},
  title     = {The Theory of Matrices},
  volume    = {2},
  publisher = {Chelsea Publishing Co.},
  address   = {New York},
  year      = {1959},
  note      = {Translated by K. A. Hirsch}
}

@inproceedings{demoura2021,
  author    = {de Moura, Leonardo and Ullrich, Sebastian},
  title     = {The {L}ean 4 Theorem Prover and Programming Language},
  booktitle = {Automated Deduction -- {CADE} 28},
  series    = {Lecture Notes in Computer Science},
  volume    = {12699},
  pages     = {625--635},
  publisher = {Springer},
  address   = {Cham},
  year      = {2021},
  doi       = {10.1007/978-3-030-79876-5_37}
}

@inproceedings{mathlib2020,
  author    = {{The mathlib Community}},
  title     = {The {L}ean Mathematical Library},
  booktitle = {Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020)},
  pages     = {367--381},
  publisher = {ACM},
  address   = {New York},
  year      = {2020},
  doi       = {10.1145/3372885.3373824}
}

@article{chen1995,
  author    = {Chen, Jie and Fan, Michael K. H. and Yu, Cheng-Ching},
  title     = {On {$D$}-stability and structured singular values},
  journal   = {Systems \& Control Letters},
  volume    = {24},
  number    = {1},
  pages     = {19--24},
  year      = {1995},
  doi       = {10.1016/0167-6911(94)00036-U}
}

@article{coxson1994,
  author    = {Coxson, Gregory E.},
  title     = {The {$P$}-matrix problem is co-{NP}-complete},
  journal   = {Mathematical Programming},
  volume    = {64},
  number    = {1--3},
  pages     = {173--178},
  year      = {1994},
  doi       = {10.1007/BF01582570}
}

@article{nemirovskii1993,
  author    = {Nemirovskii, Arkadi},
  title     = {Several {NP}-hard problems arising in robust stability analysis},
  journal   = {Mathematics of Control, Signals, and Systems},
  volume    = {6},
  number    = {2},
  pages     = {99--105},
  year      = {1993},
  doi       = {10.1007/BF01211741}
}

@article{poljak1993,
  author    = {Poljak, Svatopluk and Rohn, Ji{\v{r}}{\'\i}},
  title     = {Checking robust nonsingularity is {NP}-hard},
  journal   = {Mathematics of Control, Signals, and Systems},
  volume    = {6},
  number    = {1},
  pages     = {1--9},
  year      = {1993},
  doi       = {10.1007/BF01213466}
}

@article{braatz1994,
  author    = {Braatz, Richard P. and Young, Peter M. and Doyle, John C. and Morari, Manfred},
  title     = {Computational complexity of {$\mu$} calculation},
  journal   = {IEEE Transactions on Automatic Control},
  volume    = {39},
  number    = {5},
  pages     = {1000--1002},
  year      = {1994},
  doi       = {10.1109/9.284879}
}

@book{garey1979,
  author    = {Garey, Michael R. and Johnson, David S.},
  title     = {Computers and Intractability: A Guide to the Theory of {NP}-Completeness},
  publisher = {W. H. Freeman},
  address   = {San Francisco},
  year      = {1979}
}

@incollection{karp1972,
  author    = {Karp, Richard M.},
  title     = {Reducibility among combinatorial problems},
  booktitle = {Complexity of Computer Computations},
  editor    = {Miller, Raymond E. and Thatcher, James W. and Bohlinger, Jean D.},
  series    = {The IBM Research Symposia Series},
  publisher = {Plenum Press},
  address   = {New York},
  pages     = {85--103},
  year      = {1972},
  doi       = {10.1007/978-1-4684-2001-2_9}
}

@article{renegar1992a,
  author    = {Renegar, James},
  title     = {On the computational complexity and geometry of the first-order theory of the reals. {Part I}: {Introduction}. {Preliminaries}. {The} geometry of semi-algebraic sets. {The} decision problem for the existential theory of the reals},
  journal   = {Journal of Symbolic Computation},
  volume    = {13},
  number    = {3},
  pages     = {255--299},
  year      = {1992},
  doi       = {10.1016/S0747-7171(10)80003-3}
}

@article{renegar1992b,
  author    = {Renegar, James},
  title     = {On the computational complexity and geometry of the first-order theory of the reals. {Part II}: {The} general decision problem. {Preliminaries} for quantifier elimination},
  journal   = {Journal of Symbolic Computation},
  volume    = {13},
  number    = {3},
  pages     = {301--327},
  year      = {1992},
  doi       = {10.1016/S0747-7171(10)80004-5}
}

@article{renegar1992c,
  author    = {Renegar, James},
  title     = {On the computational complexity and geometry of the first-order theory of the reals. {Part III}: {Quantifier} elimination},
  journal   = {Journal of Symbolic Computation},
  volume    = {13},
  number    = {3},
  pages     = {329--352},
  year      = {1992},
  doi       = {10.1016/S0747-7171(10)80005-7}
}

@article{lee2001,
  author    = {Lee, Jietae and Edgar, Thomas F.},
  title     = {Real structured singular value conditions for the strong {$D$}-stability},
  journal   = {Systems \& Control Letters},
  volume    = {44},
  number    = {4},
  pages     = {273--277},
  year      = {2001},
  doi       = {10.1016/S0167-6911(01)00147-5}
}

@techreport{giorgi2015,
  author      = {Giorgi, Giorgio and Zuccotti, Cesare},
  title       = {An Overview on {$D$}-stable Matrices},
  type        = {DEM Working Paper Series},
  number      = {97 (02-15)},
  institution = {Department of Economics and Management, University of Pavia},
  address     = {Pavia},
  month       = feb,
  year        = {2015},
  url         = {http://dem-web.unipv.it/web/docs/dipeco/quad/ps/RePEc/pav/demwpp/DEMWP0097.pdf}
}

@article{lenstra2002,
  author    = {Lenstra, Jr., Hendrik W.},
  title     = {Solving the {Pell} equation},
  journal   = {Notices of the American Mathematical Society},
  volume    = {49},
  number    = {2},
  pages     = {182--192},
  year      = {2002},
  url       = {https://www.ams.org/notices/200202/fea-lenstra.pdf}
}

@book{basu2006,
  author    = {Basu, Saugata and Pollack, Richard and Roy, Marie-Fran{\c{c}}oise},
  title     = {Algorithms in Real Algebraic Geometry},
  edition   = {Second},
  series    = {Algorithms and Computation in Mathematics},
  volume    = {10},
  publisher = {Springer},
  address   = {Berlin},
  year      = {2006},
  doi       = {10.1007/3-540-33099-2}
}

@article{blondel2000,
  author    = {Blondel, Vincent D. and Tsitsiklis, John N.},
  title     = {A survey of computational complexity results in systems and control},
  journal   = {Automatica},
  volume    = {36},
  number    = {9},
  pages     = {1249--1274},
  year      = {2000},
  doi       = {10.1016/S0005-1098(00)00050-9}
}

@inproceedings{canny1988,
  author    = {Canny, John},
  title     = {Some algebraic and geometric computations in {PSPACE}},
  booktitle = {Proceedings of the Twentieth Annual {ACM} Symposium on Theory of Computing ({STOC} '88)},
  publisher = {ACM},
  address   = {New York},
  pages     = {460--469},
  year      = {1988},
  doi       = {10.1145/62212.62257}
}

@article{yu1990,
  author    = {Yu, Cheng-Ching and Fan, Michael K. H.},
  title     = {Decentralized integral controllability and {$D$}-stability},
  journal   = {Chemical Engineering Science},
  volume    = {45},
  number    = {11},
  pages     = {3299--3309},
  year      = {1990},
  doi       = {10.1016/0009-2509(90)80221-Y}
}

@article{blondel1997,
  author    = {Blondel, Vincent and Tsitsiklis, John N.},
  title     = {{NP}-hardness of some linear control design problems},
  journal   = {SIAM Journal on Control and Optimization},
  volume    = {35},
  number    = {6},
  pages     = {2118--2127},
  year      = {1997},
  doi       = {10.1137/S0363012994272630}
}

@article{gurvits2009,
  author    = {Gurvits, Leonid and Olshevsky, Alexander},
  title     = {On the {NP}-hardness of checking matrix polytope stability and continuous-time switching stability},
  journal   = {IEEE Transactions on Automatic Control},
  volume    = {54},
  number    = {2},
  pages     = {337--341},
  year      = {2009},
  doi       = {10.1109/TAC.2008.2007177}
}

@article{kariwala2005,
  author    = {Kariwala, Vinay and Forbes, J. Fraser and Meadows, Edward S.},
  title     = {Integrity of systems under decentralized integral control},
  journal   = {Automatica},
  volume    = {41},
  number    = {9},
  pages     = {1575--1581},
  year      = {2005},
  doi       = {10.1016/j.automatica.2005.03.024}
}

@article{kushelpavani2022,
  author    = {Kushel, Olga Y. and Pavani, Raffaella},
  title     = {The problem of generalized {$D$}-stability in unbounded {LMI} regions and its computational aspects},
  journal   = {Journal of Dynamics and Differential Equations},
  volume    = {34},
  number    = {1},
  pages     = {651--669},
  year      = {2022},
  doi       = {10.1007/s10884-020-09891-y}
}

@article{casasanta2026,
  author    = {Casasanta, John-Paolo and Simpson-Porco, John W.},
  title     = {A {Lyapunov} characterization of robust {$D$}-stability with application to decentralized integral control of {LTI} systems},
  journal   = {IEEE Control Systems Letters},
  volume    = {10},
  pages     = {1375--1380},
  year      = {2026},
  doi       = {10.1109/LCSYS.2026.3703779}
}

@misc{lofberg2026,
  author       = {L{\"o}fberg, Johan},
  title        = {Static output-feedback stabilization is {NP}-hard},
  howpublished = {Preprint},
  year         = {2026},
  eprint       = {2609.16886}
}

@incollection{horacek2017,
  author    = {Hor{\'a}{\v{c}}ek, Jaroslav and Hlad{\'\i}k, Milan and {\v{C}}ern{\'y}, Michal},
  title     = {Interval Linear Algebra and Computational Complexity},
  booktitle = {Applied and Computational Matrix Analysis ({MAT-TRIAD} 2015)},
  editor    = {Bebiano, Nat{\'a}lia},
  series    = {Springer Proceedings in Mathematics \& Statistics},
  volume    = {192},
  pages     = {37--66},
  publisher = {Springer},
  address   = {Cham},
  year      = {2017},
  doi       = {10.1007/978-3-319-49984-0_3},
  eprint    = {1602.00349},
  archivePrefix = {arXiv}
}

@inproceedings{forster2020,
  author    = {Forster, Yannick and Kunze, Fabian and Wuttke, Maximilian},
  title     = {Verified Programming of {T}uring Machines in {C}oq},
  booktitle = {Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020)},
  pages     = {114--128},
  publisher = {ACM},
  address   = {New York},
  year      = {2020},
  doi       = {10.1145/3372885.3373816}
}

@inproceedings{gaher2021,
  author    = {G{\"a}her, Lennard and Kunze, Fabian},
  title     = {Mechanising Complexity Theory: The {C}ook--{L}evin Theorem in {C}oq},
  booktitle = {12th International Conference on Interactive Theorem Proving (ITP 2021)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {193},
  pages     = {20:1--20:18},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address   = {Dagstuhl},
  year      = {2021},
  doi       = {10.4230/LIPIcs.ITP.2021.20}
}

@article{balbach2023,
  author    = {Balbach, Frank J.},
  title     = {The {C}ook--{L}evin theorem},
  journal   = {Archive of Formal Proofs},
  month     = jan,
  year      = {2023},
  note      = {Formal proof development},
  url       = {https://isa-afp.org/entries/Cook_Levin.html}
}