While \Cref{thm:mult-p-hard-result} shows that computing $\rpoly(\prob,\dots,\prob)$ for multiple values of $\prob$ in general is hard it does not rule out the possibility that one can compute this value exactly for a {\em fixed} value of $\prob$. %Indeed, it is easy to check that
One can compute $\rpoly(\prob,\dots,\prob)$ exactly in linear time for $\prob\in\inset{0,1}$. Next, we show that these are the only two possibilities:
Fix $\prob\in(0,1)$. Then assuming \Cref{conj:graph}, any algorithm that computes $\rpoly_{G}^3(\prob,\dots,\prob)$ for arbitrary $G =(\vset, \edgeSet)$ exactly has to run in time $\Omega\inparen{\abs{\edgeSet}^{1+\eps_0}}$, where $\eps_0$ is as in \Cref{conj:graph}.
We note that \Cref{thm:k-match-hard} and \Cref{conj:known-algo-kmatch} (and the lower bounds in the second and third rows) need $k$ to be large enough (in particular, we need a family of hard queries). But the above \Cref{th:single-p-hard} (and the lower bound in first row of Table~\ref{tab:lbs}) holds for $k=3$ (and hence for a fixed query).
%\textcolor{red}{Need to put in a proof overview here-- Atri}
Unlike the proof of \Cref{thm:mult-p-hard-result}, in this case we have to pay close attention to all the coefficients of $\rpoly_{G}^3(\prob,\ldots, \prob)$:
%Unlike \Cref{thm:mult-p-hard-result}, we do not have access to evaluations of $\rpoly_{G}^3(\prob,\ldots, \prob)$ for multiple values of $p$ and hence,
Since $p$ is fixed, the earlier polynomial interpolation based argument does not work anymore. Next, we use the fact that the algorithm still has to compute $\rpoly_{G}^3(\prob,\ldots, \prob)$ for {\em all} graphs $G$. We focus on the graphs $\graph{\ell}$ obtained from $G$ by replacing each edge by path of length $\ell$ (\Cref{def:Gk}). We then show
%\begin{Definition}\label{def:Gk}
%For $\ell \geq 1$, let graph $\graph{\ell}$ be a graph generated from an arbitrary graph $G$, by replacing every edge $e$ of $G$ with an $\ell$-path, such that all inner vertices of an $\ell$-path replacement edge have degree $2$.\footnote{Note that $G\equiv \graph{1}$.}
Fix $\prob\in(0,1)$. Given $\rpoly_{\graph{\ell}}^3(\prob,\dots,\prob)$ for $\ell\in[2]$, we can compute in $O(m)$ time a vector $\vct{b}\in\mathbb{R}^2$ such that
allowing us to compute $\numocc{G}{\tri}$ and $\numocc{G}{\threedis}$ in $O(1)$ time.
\end{Lemma}
Note that \cref{eq:lin-eqs-single-p} only depends on sub-graph counts on $G=\graph{1}$.
%(it is a bit technically tedious to relate the sub-graph counts of $\graph{2}$ to the corresponding ones in $G$).
It can be verified that the coefficient matrix in \cref{eq:lin-eqs-single-p} is full rank for all $p\in(0,1)$. Then by solving the linear equations in \cref{eq:lin-eqs-single-p} we can compute $\numocc{G}{\tri}$, from where \Cref{conj:graph} implies \Cref{th:single-p-hard}.