%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{95}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{tikz-cd}
\usepackage{tikz-3dplot}

\usetikzlibrary{3d}

\input{symbol_defns.tex}

\renewcommand{\epsilon}{\varepsilon}
\newcommand{\h}{^\mathrm{hom}}
\DeclareMathOperator{\Int}{Int}

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}[definition]{Example}

\theoremstyle{plain}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem*{corollary*}{Corollary}
\newtheorem{property}[theorem]{Property}
\newtheorem{principle}[theorem]{Principle}
\newtheorem{question}[theorem]{Question}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}

%% define your title in the usual way
\title{Real Stability and Log Concavity are coNP-Hard}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{Tracy Chin\thanks{\href{mailto:tlchin@uw.edu}{tlchin@uw.edu} The author was partially supported by NSF grant No. DMS-2153746.}\addressmark{1}}{Tracy Chin}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Washington}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
  Real-stable, Lorentzian, and log-concave polynomials are well-studied classes of polynomials, and have been powerful tools in resolving several conjectures. We show that the problems of deciding whether polynomials are real stable or log concave are coNP-hard. On the other hand, while all real-stable polynomials are Lorentzian and all Lorentzian polynomials are log concave, the problem of deciding whether a given polynomial is Lorentzian can be solved in polynomial time.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Lorentzian polynomials, stable polynomials, log concavity, computational complexity}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{ref.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}
\maketitle


\section{Introduction}
The theory of stable polynomials has been a key ingredient in seemingly unrelated mathematical advances. In the past few years, they were used to construct infinite families of Ramanujan graphs \cite{Marcus2015ramanujan, Marcus2018ramanujan}, and to resolve the Kadison--Singer problem \cite{Marcus2015kadisonsinger}.

Hyperbolic polynomials are a closely related class. They first arose in PDEs \cite{Garding1951pde}, but have also gained traction in the optimization community as barrier functions for interior point methods \cite{guler1997interiorpoint}.

Beyond hyperbolic polynomials are the classes of Lorentzian and log-concave polynomials. Lorentzian polynomials in particular have close ties to combinatorial Hodge theory \cite{Huh2023hodge} and matroids \cite{anari2018logconcave3,branden2022lorentzian}. Also called completely log-concave polynomials, they provide a bridge between continuous log concavity of a polynomial and discrete log concavity of its coefficients \cite{branden2022lorentzian}. Because of this connection to discrete log concavity, they have been used to prove log concavity of several famous combinatorial sequences, including Kostka numbers \cite{Huh2022Schur} and the coefficients of the Alexander polynomial for certain types of links \cite{Hafner2023Alexander}.

While stable, Lorentzian, and log-concave polynomials are powerful tools, less is known about how to test if a given polynomial has these properties. In \cite{raghavendra2016real}, \citeauthor{raghavendra2016real} give a polynomial time algorithm for checking real stability of bivariate polynomials, but their techniques do not generalize easily to more variables. Instead, the results using stable polynomials in \cite{Marcus2015ramanujan,Marcus2015kadisonsinger,Marcus2018ramanujan} all start with a known construction for stable polynomials, then use a series of stability-preserving operations to reach the desired polynomial, rather than checking stability directly. It is relatively easy to generate particular stable polynomials, and \citeauthor{borcea2009stabilitypreserver} give a full classification of stability-preserving operations \cite{borcea2009stabilitypreserver}, enabling this style of argument for proving particular polynomials are real stable. Similarly, to prove log concavity in \cite{Hafner2023Alexander}, \citeauthor{Hafner2023Alexander} construct a multivariate generalization of the Alexander polynomial in order to show that the single variable specialization has log-concave coefficients.

We study the hierarchy of stable, Lorentzian, and log-concave polynomials through the lens of computational complexity. In previous works, \citeauthor{saunderson2019certifying} showed that it is coNP-hard to decide if a polynomial is hyperbolic with respect to a given direction \cite{saunderson2019certifying}, and \citeauthor{Ahmadi_2011} showed that it is NP-hard to test if a polynomial is convex \cite{Ahmadi_2011}. We extend and refine the techniques and results from these papers to get computational complexity results on testing real stability and log concavity.

In \Cref{sec:stability}, we will see that it is coNP-hard to determine if a homogeneous cubic polynomial is real stable. By contrast, for fixed degree $d$, deciding whether a polynomial is Lorentzian can be done in polynomial time in the number of variables (\Cref{sec:complete-log concavity}), but log concavity is again coNP-hard (\Cref{sec:quartic-log-concavity}). For full proofs of the statements in this abstract, we refer the interested reader to \cite{chin2024realstabilitylogconcavity}.

\section{Background}
We begin with some background and definitions of the classes of polynomials under study.

\subsection{Real Stable and Hyperbolic Polynomials}
In \Cref{sec:stability}, we study real stable polynomials.
\begin{definition}
    A polynomial $f\in \RR[x_1,\dots,x_n]$ is \emph{real stable} if for all $a \in \RR_{>0}^n$ and $b \in \RR^n$, the univariate restriction $f(ta + b) \in \RR[t]$ is real-rooted.
\end{definition}
The real stable polynomials naturally generalize the notion of real-rootedness for univariate polynomials. In particular, a univariate polynomial $f \in \RR[t]$ is real rooted if and only if it is real stable.

The main tool for our real stability results is hyperbolic polynomials.
\begin{definition}
    A homogeneous polynomial $p \in \RR[x_1,\dots,x_n]_d$ is \textit{hyperbolic with respect to $e\in\RR^n$} if $p(e) > 0$ and for all $x \in \RR^n$, the univariate polynomial $p(te - x) \in \RR[t]$ is real-rooted.
\end{definition}

If $p$ is hyperbolic with respect to $e$, then we define the associated \textit{hyperbolicity cone}
\[\Lambda_+(p,e) = \{x\in\RR^n : \text{all roots of } p(te-x) \text{ are positive}\}.\]

The following is a classic result on hyperbolic polynomials, due to \citeauthor{garding1959hyperbolic} \cite{garding1959hyperbolic}.

\begin{theorem}[{\cite[Theorem 2]{garding1959hyperbolic}}]\label{thm:hyperbolicity-cone}
    If $p$ is hyperbolic with respect to $e$, then it is also hyperbolic with respect to $x$ for any $x \in \Lambda_+(p,e)$. Moreover, the closure of the hyperbolicity cone $\overline{\Lambda_+}(p,e)$ can be described explicitly as the closure of the connected component of $\RR^n \setminus V(p)$ containing $e$.
\end{theorem}

Unravelling the definitions, a homogeneous polynomial is real stable if and only if it is hyperbolic with respect to every $e \in \RR^n_{>0}$.

\begin{example}\label{ex:hyperbolic-polynomial}
    Let $p(x_0,x_1,\dots,x_n) = x_0^2 - \sum_{i=1}^n x_i^2.$ Then $p$ is hyperbolic with respect to $e = (1,0,\dots,0).$ Indeed, for any $(x_0, \vec{x}) \in \RR^{n+1},$
    \[p(te - (x_0, \vec{x})) = (t-x_0)^2 - \lVert \vec{x}\rVert^2,\]
    which is real rooted with roots at $t = x_0 \pm \lVert \vec{x}\rVert$.

    Both roots are positive if and only if $x_0 > \lVert\vec{x}\rVert$, so
    \[\Lambda_+(p,e) = \{(x_0,\vec{x}) \in \RR^{n+1} : x_0 > \lVert\vec{x}\rVert\}.\]

    Further, we note that $V_\RR(p) = \{(x_0,\vec{x})\in \RR^{n+1} : |x_0| = \lVert \vec{x}\rVert\}$, so the connected component of $\RR^{n+1} \setminus V_\RR(p)$ containing $e$ is again $\{(x_0, \vec{x}) : x_0 > \lVert \vec{x}\rVert\}$, so by \Cref{thm:hyperbolicity-cone},
    \[\overline{\Lambda_+}(p,e) = \overline{\{(x_0, \vec{x}) : x_0 > \lVert \vec{x}\rVert\}} = \{(x_0,\vec{x}) \in \RR^{n+1} : x_0 \geq \lVert \vec{x}\rVert\}.\]
\end{example}

\begin{figure}[ht]
    \centering
    \include{hyperbolicity_cone_example}
    \caption{The hyperbolicity cone described in \Cref{ex:hyperbolic-polynomial}.}
\end{figure}

\subsection{Log-Concave and Lorentzian Polynomials}
In \Cref{sec:complete-log concavity,sec:quartic-log-concavity}, we study Lorentzian and log-concave polynomials.

\begin{definition}
    A polynomial $f \in \RR_{\geq 0}[x_1,\dots,x_n]$ is \textit{log concave} if $\log(f)$ is a concave function over $\RR^n_{> 0}$. Equivalently, $f$ is log concave if and only if $\nabla^2\log(f) \preceq 0$ at all points of $\RR^n_{\geq 0}$ where it is defined.
\end{definition}

For homogeneous polynomials of degree $d \geq 2$, we can also characterize log concavity using $\nabla^2 f$.
\begin{theorem}[{\cite[Proposition 2.33]{branden2022lorentzian}}]\label{thm:log concave-hessian}
    If $f$ is a homogeneous polynomial in $n \geq 2$ variables of degree $d\geq 2$, then the following are equivalent for any $w\in\RR^n$ satisfying $f(w) > 0$.
    \begin{enumerate}
        \item[(1)] The Hessian of $f^{1/d}$ is negative semidefinite at $w$.
        \item[(2)] The Hessian of $\log f$ is negative semidefinite at $w$.
        \item[(3)] The Hessian of $f$ has exactly one positive eigenvalue at $w$.
    \end{enumerate}
\end{theorem}

Lorentzianity is a stronger condition that requires $f$ and and its partial derivatives to all be log concave. The term was coined by \citeauthor{branden2022lorentzian} in \cite{branden2022lorentzian}. In that paper, they also show that for homogeneous polynomials, Lorentzianity is equivalent to the notions of strong log-concavity and complete log-concavity, which were defined in \cite{gurvitz2009newtonlikeinequalities} and \cite{anari2018logconcave}, respectively.
\begin{definition}
    A homogeneous polynomial $f \in \RR_{\geq 0}[x_1,\dots,x_n]$ is \emph{Lorentzian} if for all $\alpha \in \NN^n$, $\dl^\alpha f$ is either identically zero or log concave, where we use the shorthand $\dl^\alpha f := \frac{\dl^{\alpha_1}}{\dl x_1^{\alpha_1}}\dots \frac{\dl^{\alpha_n}}{\dl x_n^{\alpha_n}} f$.
\end{definition}
By taking $\alpha = (0,\dots,0)$, we immediately see that all Lorentzian polynomials are log concave. However, as we will see in \Cref{sec:quartic-log-concavity}, for all degrees $\geq 4$, there exist log-concave polynomials that are not Lorentzian.

Lorentzian polynomials are a useful tool in combinatorics because their coefficients form an ultra-log-concave sequence \cite{gurvitz2009newtonlikeinequalities}. They have been used, for example, to prove log-concavity of Kostka numbers \cite{Huh2022Schur} and of the coefficients of the Alexander polynomial for special alternating links \cite{Hafner2023Alexander}.

\section{Computational Complexity of Stability}\label{sec:stability}
In \cite{raghavendra2016real}, \citeauthor{raghavendra2016real} show that given a bivariate polynomial $p\in\RR[x,y]$ of degree $d$, there is a deterministic algorithm that determines whether $p$ is real stable in $O(d^5)$ operations. They also ask whether their algorithm can be generalized to three or more variables.

In this section, we will see that it is coNP-hard to test whether a homogeneous cubic with rational coefficients is real stable. To do this, we will leverage the following result from \cite{saunderson2019certifying}:
\begin{theorem}[{\cite[Proposition 5.1]{saunderson2019certifying}}]\label{thm:hyp-iff-max-le-1}
    Let 
    	\[p(x_0,x) = x_0^3 - 3x_0\lVert x\rVert^2 + 2q(x),\]
	where $q \in \RR[x_1,\dots,x_n]$ is homogeneous of degree three. Then $p$ is hyperbolic with respect to $e_0$ if and only if $\max_{\lVert x\rVert^2 = 1} |q(x)| \leq 1$.
\end{theorem}
In \cite{saunderson2019certifying}, \citeauthor{saunderson2019certifying} proves this result and uses it to show that it coNP-hard to decide if a homogeneous cubic polynomial is hyperbolic in a given direction. In this section, we use similar techniques to show that testing real stability is also coNP-hard.

To apply this result, we will construct a polyhedral cone $K$ such that $p$ is hyperbolic with respect to $e_0$ if and only if it is hyperbolic with respect to $K$. After an appropriate change of variables, this is equivalent to being stable. 

For $\epsilon > 0$, let $L_\epsilon \subseteq\RR^{n+1}$ denote the Lorentz cone
\[
    L_\epsilon = \{(x_0,\vec{x}) \in \RR^{n+1} : x_0 \geq \frac{1}{\epsilon}\lVert x\rVert\}.
\]

\begin{proposition}\label{prop:hyp-wrt-Lorentz}
    Let $p(x_0,x) = x_0^3 - 3x_0 \lVert x\rVert^2 + 2q(x)$, where $q(x)$ is a homogeneous polynomial of degree three in $n$ variables. Let $N$ be the largest coefficient (in absolute value) of $q$, and let $0 < \epsilon < \min(\frac{1}{2|N|n^3}, \frac{1}{2})$. Then $p$ is hyperbolic with respect to $e_0$ if and only if it is hyperbolic with respect to every $e \in L_{\epsilon}$.
\end{proposition}

\begin{figure}
\centering
\include{lorentz_cone}
\caption{Cones $L_\epsilon \supseteq K$, both containing $e_0$. These cones are constructed so that $p > 0$ on $L_\epsilon$ and $K$, so $p$ is hyperbolic with respect to $e_0$ if and only if it is hyperbolic with respect to $K$.}
\end{figure}

\begin{corollary}\label{cor:hyp-wrt-simplicial}
    Let $p$ and $\epsilon$ be as above, and let $K = \cone\{e_0 \pm \epsilon e_i : i = 1,\dots, n\}$. Then $p$ is hyperbolic with respect to $e_0$ if and only if $p$ is hyperbolic with respect to every $e\in K$.
\end{corollary}

\begin{theorem}\label{thm:hyp-iff-stable}
    Let $p(x_0,x) = x_0^3 -3x_0\lVert x\rVert^2 + 2q(x)$, where $q$ is homogeneous of degree $3$ with rational coefficients. Let $N$ be the largest coefficient of $q$ (in absolute value), let $0<\epsilon < \min(\frac{1}{2|N|n^3}, \frac{1}{2})$, and let $M$ be the $(n+1)\times 2n$ matrix whose columns are $e_0 \pm \epsilon e_i$ for $i = 1,\dots, n$. Define
    \[\til{p}(x_1,\dots,x_{2n}) = p(Mx) \in \RR[x_1,\dots,x_{2n}]_3.\]
    Then $p$ is hyperbolic with respect to $e_0$ if and only if $\til{p}$ is stable.
\end{theorem}

We have now reduced the problem of testing stability to the problem of maximizing a homogeneous cubic over the unit sphere. To show that maximizing cubics is hard, we require the following result of Nesterov:
\begin{theorem}[{\cite[Theorem 4]{RePEc:cor:louvco:2003071}}, {\cite[Theorem 5.2]{saunderson2019certifying}}]\label{thm:cubic-poly-max-clique}
    Let $G=(V,E)$ be a simple graph and let $\omega(G)$ be the size of a largest clique in $G$. Define
    \[q_G(x,y) = \sum_{(i,j)\in E} x_ix_jy_{ij}.\]
    Then
    \[\max_{\lVert x\rVert^2 +\lVert y\rVert^2 = 1} q_G(x,y) = \sqrt{\frac{2}{27}}\sqrt{1-\frac{1}{\omega(G)}}.\]
\end{theorem}

Since deciding whether $\omega(G) \leq k$ is coNP-hard, testing if a cubic polynomial is real stable must also be coNP-hard.
\begin{theorem}\label{thm:cubic-stable-hard}
    Given a homogeneous cubic polynomial $p$ with rational coefficients, it is coNP-hard to decide if $p$ is stable.
\end{theorem}

As an easy corollary, it is also coNP-hard to test for stability in higher degrees.
\begin{corollary}\label{cor:stability-conp-hard}
    Fix a degree $d \geq 3$. Given a homogeneous polynomial $p$ with rational coefficients of degree $d$, it is coNP-hard to decide if $p$ is stable.
\end{corollary}

\section{Lorentzian Polynomials}\label{sec:complete-log concavity}
While all homogeneous stable polynomials are Lorentzian, the converse is not true. In fact, while deciding if a polynomial is stable is coNP-hard, deciding Lorentzianity for polynomials of fixed degree $d$ can be done in polynomial time in the number of variables $n$.

The key is the following result from \cite{anari2018logconcave3}. We say a polynomial $f\in\RR[z_1,\dots,z_n]$ is \emph{indecomposable} if it cannot be written as $f = f_1 + f_2$, where $f_1,f_2$ are nonzero polynomials in disjoint sets of variables.

\begin{theorem}[{\cite[Theorem 3.2]{anari2018logconcave3}}]
    Let $f\in\RR[z_1,\dots,z_n]$ be a homogeneous polynomial of degree $d \geq 2$ with nonnegative coefficients. Then $f$ is Lorentzian if and only if the following two conditions hold:
    \begin{enumerate}
        \item[(i)] For all $\alpha\in\ZZ^n_{\geq 0}$ with $|\alpha|\leq d-2$, the polynomial $\partial^\alpha f$ is indecomposable.
        \item[(ii)] For all $\alpha\in\ZZ^n_{\geq 0}$ with $|\alpha| = d-2$, the quadratic polynomial $\partial^\alpha f$ is log concave over $\RR^n_{\geq 0}$.
    \end{enumerate}
\end{theorem}

This means that, if we consider the degree $d$ as a fixed parameter, Lorentzianity can be decided in polynomial time in the number of variables.
\begin{proposition}\label{prop:clc-poly-time}
    For fixed degree $d$, there is an algorithm, which runs in time polynomial in $n$, that decides if a homogeneous polynomial $f\in\RR_{\geq 0}[z_1,\dots,z_n]_d$ is Lorentzian.
\end{proposition}
\begin{proof}
    Since $d$ is fixed, there are $O(n^d)$ partial derivatives to check. Checking indecomposability can be done by checking connectivity of a graph on $n$ vertices, which takes polynomial time in $n$. Moreover, if $|\alpha| = d-2$, then $\partial^\alpha f$ is quadratic, so the entries of $\nabla^2 \partial^\alpha f(z)$ do not depend on $z$. Since $\partial^\alpha f$ is log concave if and only if $\nabla^2 \partial^\alpha f$ has exactly one positive eigenvalue, and since we can compute the signs of the eigenvalues of an $n\times n$ matrix in polynomial time, it follows that checking whether $\partial^\alpha f$ is log concave can also be accomplished in polynomial time.
\end{proof}

\section{Computational Complexity of Log Concavity}\label{sec:quartic-log-concavity}


In \Cref{sec:complete-log concavity}, we showed that for any fixed degree $d$, we can decide if a homogeneous polynomial is Lorentzian in polynomial time in the number of variables. However, while all Lorentzian polynomials are log concave, the converse is not true, and we cannot reduce checking log concavity to checking quadratic derivatives. In fact, deciding whether a homogoeneous polynomial is log concave is coNP-hard for all degrees $d \geq 4$.

\begin{theorem}\label{thm:quartic-lc-hard}
    It is coNP-hard to decide if a homogeneous polynomial of degree four with nonnegative coefficients is log concave.
\end{theorem}

To prove this, we first give a reduction from checking if a homogeneous quartic is convex on $\RR^n_{\geq 0}$.

\begin{lemma}\label{lem:lc-iff-cvx-on-nonneg}
    Let $f\in\RR[x_1,\dots,x_n]_4$ be a homogeneous quartic polynomial, and let $N > 0$ be at least as large as the largest coefficient of $f$. Let
    \[g(x_1,\dots,x_n,z) = N\left(z + \sum_{i=1}^n x_i\right)^4 - f(x_1,\dots x_n) \in \RR[x_1,\dots,x_n,z].\]
    Then $g$ is a homogeneous quartic with nonnegative coefficients, and $f$ is convex on $\RR^n_{\geq 0}$ if and only if $g$ is log concave.
\end{lemma}

Next, we claim that it is coNP-hard to decide if a quartic polynomial is convex on $\RR^n_{\geq 0}$. In \cite{Ahmadi_2011}, \citeauthor{Ahmadi_2011} show that it is coNP-hard to test if a quartic polynomial is convex. Given a graph $G$ and integer $k$, they construct a quartic polynomial that is convex if and only if $\omega(G) \leq k$, which implies that deciding convexity of quartics is coNP-hard.
\begin{theorem}[\cite{Ahmadi_2011,ling-biquadratic}]\label{thm:convex_iff_clique}
    Let $G = ([n],E)$ be a graph and let $1 \leq k \leq n$. Define the biquadratic form
    \begin{equation*}\label{eqn:graph-biquadratic}
        b_G(x;y) = -2k \sum_{ij\in E} x_ix_jy_iy_j - (1-k)\left(\sum_{i=1}^n x_i^2\right)\left(\sum_{i=1}^n y_i^2\right),
    \end{equation*}
    and let
    \begin{equation*}\label{eqn:quartic-convex}
        f(x,y) = b_G(x;y) + \frac{n^2 \gamma}{2}\left(\sum_{i=1}^n x_i^4 + \sum_{i=1}^n y_i^4 + \sum_{\substack{i,j=1,\dots,n \\ i < j}} x_i^2 x_j^2 + \sum_{\substack{i,j=1,\dots,n \\ i < j}} y_i^2 y_j^2\right).
    \end{equation*}
    Then $f$ is convex if and only if $\omega(G) \leq k$.
\end{theorem}

We refine this result to show that the polynomial from \Cref{thm:convex_iff_clique} is convex on nonnegative orthant if and only if $\omega(G) \leq k$, and thus that it is coNP-hard to decide if a polynomial is convex on the nonnegative orthant. By \Cref{lem:lc-iff-cvx-on-nonneg}, it is then also hard to decide if a homogeneous quartic polynomial is log concave.

An easy corollary also shows that deciding if a polynomial is log concave is coNP-hard in all higher degrees, as well.

\begin{corollary}\label{cor:lc-hard-higher-deg}
    For fixed degree $d \geq 4$, it is coNP-hard to decide if a homogeneous polynomial of degree $d$ with nonnegative coefficients is log concave.
\end{corollary}

\begin{remark}
    We can decide log-concavity in polynomial time for all degrees three and below, so this result is minimal. Indeed, all linear polynomials are log concave, and in degrees two and three, a homogeneous polynomial is log concave if and only if it is Lorentzian.
\end{remark}

\section{Conclusion and Future Work}
This work discusses stable, Lorentzian, and log-concave polynomials. In particular, we show that it is coNP-hard to test if polynomials are stable or log concave. While stable and log-concave polynomials are useful tools, this implies that (assuming P $\neq$ NP), it is intractible to test if a given polynomial is stable or log concave, unless additional structure is present.

Unfortunately, while all stable polynomials are Lorentzian and all Lorentzian polynomials are log concave, testing Lorentzianity doesn't give any meaningful approximation for the max clique problem. Indeed, if we want to check if $\omega(G) \leq k$ for any $k \geq 2$, then the polynomial from \Cref{sec:stability} is always Lorentzian. On the other hand, the polynomial from \Cref{sec:quartic-log-concavity} is never Lorentzian. Thus, the most that testing Lorentzianity can tell us is that the clique number of any graph is at least one.

Throughout this paper, we used reductions from the max clique problem to show that testing our desired properties is coNP-hard. However, our reductions did not use the full strength of max clique: the max clique problem is not only NP-hard, but also NP-hard to approximate. This hardness of approximation should allow us to strengthen our results, but the exact form of this conjectured stronger result remains open.

Moreover, while we have given lower bounds on the complexity of deciding stability and log concavity, we do not have upper bounds on their complexity. While there are obvious certificates that a given polynomial is not real stable or not log concave, we cannot guarantee that these certificates are polynomial size, so we cannot conclude that these problems are in coNP. Instead, we would need to broaden our scope to other complexity classes, such as the universal theory of the reals.

\printbibliography
\end{document}
