@article{saunderson2019certifying, AUTHOR = {Saunderson, James}, TITLE = {Certifying polynomial nonnegativity via hyperbolic optimization}, JOURNAL = {SIAM J. Appl. Algebra Geom.}, FJOURNAL = {SIAM Journal on Applied Algebra and Geometry}, VOLUME = {3}, YEAR = {2019}, NUMBER = {4}, PAGES = {661--690}, DOI = {10.1137/19M1253551}, } @article{anari2018logconcave, AUTHOR = {Anari, Nima and Gharan, Shayan Oveis and Vinzant, Cynthia}, TITLE = {Log-concave polynomials, {I}: entropy and a deterministic approximation algorithm for counting bases of matroids}, JOURNAL = {Duke Math. J.}, FJOURNAL = {Duke Mathematical Journal}, VOLUME = {170}, YEAR = {2021}, NUMBER = {16}, PAGES = {3459--3504}, MRCLASS = {05B35 (14C25 68W25 90C25)}, MRNUMBER = {4332671}, DOI = {10.1215/00127094-2020-0091}, } @article {anari2018logconcave3, AUTHOR = {Anari, Nima and Liu, Kuikui and Oveis Gharan, Shayan and Vinzant, Cynthia}, TITLE = {Log-concave polynomials {III}: {M}ason's ultra-log-concavity conjecture for independent sets of matroids}, JOURNAL = {Proc. Amer. Math. Soc.}, FJOURNAL = {Proceedings of the American Mathematical Society}, VOLUME = {152}, YEAR = {2024}, NUMBER = {5}, PAGES = {1969--1981}, MRCLASS = {05B35 (05A20 52A41)}, MRNUMBER = {4728467}, DOI = {10.1090/proc/16724}, } @TechReport{RePEc:cor:louvco:2003071, author={Nesterov, Yu}, title={{Random walk in a simplex and quadratic optimization over convex polytopes}}, year=2003, month=Oct, institution={Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)}, type={LIDAM Discussion Papers CORE}, url={https://ideas.repec.org/p/cor/louvco/2003071.html}, number={2003071}, keywords={global optimization; quadratic optimization; polynomial optimization; simplex structure; random walk}, doi={}, } @article{garding1959hyperbolic, AUTHOR = {G\.arding, Lars}, TITLE = {An inequality for hyperbolic polynomials}, JOURNAL = {J. Math. Mech.}, FJOURNAL = {J. Math. Mech.}, VOLUME = {8}, YEAR = {1959}, PAGES = {957--965}, DOI = {10.1512/iumj.1959.8.58061}, } @inproceedings{alimohammadi2023fractionally, author = {Alimohammadi, Yeganeh and Anari, Nima and Shiragur, Kirankumar and Vuong, Thuy-Duong}, title = {Fractionally log-concave and sector-stable polynomials: counting planar matchings and more}, year = {2021}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3406325.3451123}, doi = {10.1145/3406325.3451123}, booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing}, pages = {433–446}, numpages = {14}, keywords = {Spectral Independence, Random Walk, Geometry of Polynomials, Counting and Sampling}, location = {Virtual, Italy}, series = {STOC 2021} } @article{Ahmadi_2011, title={{NP}-hardness of deciding convexity of quartic polynomials and related problems}, volume={137}, ISSN={1436-4646}, url={http://dx.doi.org/10.1007/s10107-011-0499-2}, DOI={10.1007/s10107-011-0499-2}, number={1–2, Ser. A}, journal={Math. Program.}, publisher={Springer Science and Business Media LLC}, author={Ahmadi, Amir Ali and Olshevsky, Alex and Parrilo, Pablo A. and Tsitsiklis, John N.}, year={2011}, pages={453-476} } @inproceedings{Moffatt2019DeltamatroidsFG, title={Delta-matroids for graph theorists}, author={Iain Moffatt}, booktitle={BCC}, year={2019}, url={https://api.semanticscholar.org/CorpusID:201715671} } @inproceedings{bouchet_repdeltamatroids, address = {Amsterdam}, author = {André Bouchet}, editor = {Hajnal, A. and Lov{\'a}sz, L{\'a}szl{\'o} and S{\'o}s, Vera T.}, keywords = {Combinatorial analysis -- Congresses}, language = {eng}, lccn = {89137039}, publisher = {North-Holland Pub. Co.}, series = {Colloquia mathematica Societatis J{\'a}nos Bolyai, 52}, title = {Representability of {$\Delta$}-matroids}, booktitle = {Combinatorics}, year = {1988}} @article{branden2022lorentzian, author = {Petter Br{\"a}nd{\'e}n and June Huh}, doi = {10.4007/annals.2020.192.3.4}, journal = {Ann. of Math.}, keywords = {Log-concavity, Lorentzian polynomials, matroids, m-convexity, stable polynomials, tropicalization}, number = {3}, pages = {821 -- 891}, publisher = {Department of Mathematics of Princeton University}, title = {{Lorentzian polynomials}}, url = {https://doi.org/10.4007/annals.2020.192.3.4}, volume = {192}, year = {2020}, bdsk-url-1 = {https://doi.org/10.4007/annals.2020.192.3.4}} @article {anari2019logconcave, AUTHOR = {Anari, Nima and Liu, Kuikui and Oveis Gharan, Shayan and Vinzant, Cynthia}, TITLE = {Log-concave polynomials {II}: {H}igh-dimensional walks and an {FPRAS} for counting bases of a matroid}, JOURNAL = {Ann. of Math. (2)}, FJOURNAL = {Annals of Mathematics. Second Series}, VOLUME = {199}, YEAR = {2024}, NUMBER = {1}, PAGES = {259--299}, MRCLASS = {68Q87 (60J10 68W20 68W25)}, MRNUMBER = {4681146}, DOI = {10.4007/annals.2024.199.1.4}, URL = {https://doi.org/10.4007/annals.2024.199.1.4}, } @incollection {raghavendra2016real, AUTHOR = {Raghavendra, Prasad and Ryder, Nick and Srivastava, Nikhil}, TITLE = {Real stability testing}, BOOKTITLE = {8th {I}nnovations in {T}heoretical {C}omputer {S}cience {C}onference}, SERIES = {LIPIcs. Leibniz Int. Proc. Inform.}, VOLUME = {67}, PAGES = {Art. No. 5, 15 pp.}, PUBLISHER = {Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern}, YEAR = {2017}, MRCLASS = {65D99 (26C10 68W30)}, MRNUMBER = {3754929}, } @article{branden2010halfplane, author = {Br\"{a}nd\'{e}n, Petter}, doi = {10.1137/090758738}, eprint = {https://doi.org/10.1137/090758738}, journal = {SIAM Journal on Discrete Mathematics}, number = {3}, pages = {921-933}, title = {Discrete Concavity and the Half-Plane Property}, url = {https://doi.org/10.1137/090758738}, volume = {24}, year = {2010}, bdsk-url-1 = {https://doi.org/10.1137/090758738}} @article{bouchet1989matching, author = {Andr{\'e} Bouchet}, date-modified = {2024-02-08 15:08:55 -0800}, doi = {https://doi.org/10.1016/0166-218X(92)90272-C}, journal = {Discrete Applied Mathematics}, number = {1}, pages = {55-62}, title = {Matchings and {$\Delta$}-matroids}, url = {https://www.sciencedirect.com/science/article/pii/0166218X9290272C}, volume = {24}, year = {1989}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/0166218X9290272C}, bdsk-url-2 = {https://doi.org/10.1016/0166-218X(92)90272-C}} @article{Marcus2015ramanujan, title = {Interlacing families {I}: Bipartite {R}amanujan graphs of all degrees}, url = {http://dx.doi.org/10.4007/annals.2015.182.1.7}, DOI = {10.4007/annals.2015.182.1.7}, journal = {Ann. of Math.}, publisher = {Annals of Mathematics}, author = {Marcus, Adam and Spielman, Daniel and Srivastava, Nikhil}, year = {2015}, pages = {307–325} } @article{Marcus2015kadisonsinger, title = {Interlacing families {II}: Mixed characteristic polynomials and the {K}adison--{S}inger problem}, url = {http://dx.doi.org/10.4007/annals.2015.182.1.8}, DOI = {10.4007/annals.2015.182.1.8}, journal = {Ann. of Math.}, publisher = {Annals of Mathematics}, author = {Marcus, Adam and Spielman, Daniel and Srivastava, Nikhil}, year = {2015}, pages = {327-350} } @article{Marcus2018ramanujan, AUTHOR = {Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil}, TITLE = {Interlacing families {IV}: {B}ipartite {R}amanujan graphs of all sizes}, JOURNAL = {SIAM J. Comput.}, FJOURNAL = {SIAM Journal on Computing}, VOLUME = {47}, YEAR = {2018}, NUMBER = {6}, PAGES = {2488--2509}, DOI = {10.1137/16M106176X}, } @article{Garding1951pde, title = {Linear hyperbolic partial differential equations with constant coefficients}, volume = {85}, url = {http://dx.doi.org/10.1007/BF02395740}, DOI = {10.1007/bf02395740}, number = {0}, journal = {Acta Math.}, publisher = {International Press of Boston}, author = {Gårding, Lars}, year = {1951}, pages = {1–62} } @article{guler1997interiorpoint, AUTHOR = {G\"uler, Osman}, TITLE = {Hyperbolic polynomials and interior point methods for convex programming}, JOURNAL = {Math. Oper. Res.}, FJOURNAL = {Mathematics of Operations Research}, VOLUME = {22}, YEAR = {1997}, NUMBER = {2}, PAGES = {350--377}, DOI = {10.1287/moor.22.2.350}, } @incollection{Huh2023hodge, AUTHOR = {Huh, June}, TITLE = {Combinatorics and {H}odge theory}, BOOKTITLE = {I{CM}---{I}nternational {C}ongress of {M}athematicians. {V}ol. 1. {P}rize lectures}, PAGES = {212--239}, PUBLISHER = {EMS Press, Berlin}, YEAR = {[2023] \copyright 2023}, } @article{Murota2006Mconvex, title = {M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem}, volume = {20}, url = {http://dx.doi.org/10.1137/040618710}, DOI = {10.1137/040618710}, number = {1}, journal = {SIAM Journal on Discrete Mathematics}, publisher = {Society for Industrial & Applied Mathematics (SIAM)}, author = {Murota, Kazuo}, year = {2006}, month = jan, pages = {213–226} } @article{ling-biquadratic, AUTHOR = {Ling, Chen and Nie, Jiawang and Qi, Liqun and Ye, Yinyu}, TITLE = {Biquadratic optimization over unit spheres and semidefinite programming relaxations}, JOURNAL = {SIAM J. Optim.}, FJOURNAL = {SIAM Journal on Optimization}, VOLUME = {20}, YEAR = {2009}, NUMBER = {3}, PAGES = {1286--1310}, DOI = {10.1137/080729104}, } @article{Motzkin_Straus_1965, title={Maxima for Graphs and a New Proof of a Theorem of {Turán}}, volume={17}, DOI={10.4153/CJM-1965-053-6}, journal={Canadian Journal of Mathematics}, author={Motzkin, T. S. and Straus, E. G.}, year={1965}, pages={533–540}} @article{Huh2022Schur, AUTHOR = {Huh, June and Matherne, Jacob P. and M\'esz\'aros, Karola and St. Dizier, Avery}, TITLE = {Logarithmic concavity of {S}chur and related polynomials}, JOURNAL = {Trans. Amer. Math. Soc.}, FJOURNAL = {Transactions of the American Mathematical Society}, VOLUME = {375}, YEAR = {2022}, NUMBER = {6}, PAGES = {4411--4427}, DOI = {10.1090/tran/8606}, } @misc{Hafner2023Alexander, AUTHOR = {Hafner, Elena S. and M\'esz\'aros, Karola and Vidinas, Alexander}, TITLE = {Log-concavity of the {A}lexander polynomial}, JOURNAL = {Int. Math. Res. Not. IMRN}, FJOURNAL = {International Mathematics Research Notices. IMRN}, YEAR = {2024}, VOLUME = {2024}, NUMBER = {13}, PAGES = {10273--10284}, DOI = {10.1093/imrn/rnae058}, } @misc{chin2024realstabilitylogconcavity, title={Real Stability and Log Concavity are coNP-Hard}, author={Tracy Chin}, year={2024}, eprint={2405.00162}, eprinttype={arxiv}, primaryClass={math.OC} } @inbook{Karp1972, title = {Reducibility among Combinatorial Problems}, url = {http://dx.doi.org/10.1007/978-1-4684-2001-2_9}, DOI = {10.1007/978-1-4684-2001-2_9}, booktitle = {Complexity of Computer Computations}, publisher = {Springer US}, author = {Karp, Richard M.}, year = {1972}, pages = {85–103} } @article {borcea2009stabilitypreserver, AUTHOR = {Borcea, Julius and Br\"{a}nd\'{e}n, Petter}, TITLE = {P\'{o}lya-{S}chur master theorems for circular domains and their boundaries}, JOURNAL = {Ann. of Math. (2)}, FJOURNAL = {Annals of Mathematics. Second Series}, VOLUME = {170}, YEAR = {2009}, NUMBER = {1}, PAGES = {465--492}, MRCLASS = {30C10 (65H05 65J05)}, MRNUMBER = {2521123}, MRREVIEWER = {Vania\ D.\ Mascioni}, DOI = {10.4007/annals.2009.170.465}, URL = {https://doi.org/10.4007/annals.2009.170.465}, } @incollection {gurvitz2009newtonlikeinequalities, AUTHOR = {Gurvits, Leonid}, TITLE = {On multivariate {N}ewton-like inequalities}, BOOKTITLE = {Advances in combinatorial mathematics}, PAGES = {61--78}, PUBLISHER = {Springer, Berlin}, YEAR = {2009}, MRCLASS = {26D07 (05A20 26B25)}, MRNUMBER = {2683227}, DOI = {10.1007/978-3-642-03562-3\_4}, }