60 lines
3.9 KiB
TeX
60 lines
3.9 KiB
TeX
%root: main.tex
|
|
%!TEX root=./main.tex
|
|
|
|
\subsection{Single $\prob$ value}
|
|
\label{sec:single-p}
|
|
|
|
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:
|
|
|
|
\begin{Theorem}\label{th:single-p-hard}
|
|
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}.
|
|
\end{Theorem}
|
|
|
|
Note that \Cref{lem:tdet-om} and \Cref{th:single-p-hard} above imply the hardness result in the first row of \Cref{tab:lbs}.
|
|
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)$:
|
|
\begin{Lemma}\label{lem:qE3-exp}
|
|
For any $\prob$, we have:
|
|
{\small
|
|
\begin{align}
|
|
&\rpoly_{G}^3(\prob,\ldots, \prob) = \numocc{G}{\ed}\prob^2 + 6\numocc{G}{\twopath}\prob^3 + 6\numocc{G}{\twodis}\prob^4 + 6\numocc{G}{\tri}\prob^3\nonumber\\
|
|
&+ 6\numocc{G}{\oneint}\prob^4 + 6\numocc{G}{\threepath}\prob^4 + 6\numocc{G}{\twopathdis}\prob^5 + 6\numocc{G}{\threedis}\prob^6.\label{claim:four-one}
|
|
\end{align}}
|
|
\end{Lemma}
|
|
%\subsubsection{Proof for \Cref{lem:qE3-exp}}
|
|
%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}$.}
|
|
%\end{Definition}
|
|
|
|
\begin{Lemma}\label{lem:lin-sys}
|
|
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
|
|
\begin{equation}
|
|
\label{eq:lin-eqs-single-p}
|
|
\begin{pmatrix}
|
|
1 - 3p & -(3\prob^2 - \prob^3)\\
|
|
10(3\prob^2 - \prob^3) & 10(3\prob^2 - \prob^3)
|
|
\end{pmatrix}
|
|
\cdot
|
|
\begin{pmatrix}
|
|
\numocc{G}{\tri}]\\
|
|
\numocc{G}{\threedis}
|
|
\end{pmatrix}
|
|
=\vct{b},
|
|
\end{equation}
|
|
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}.
|
|
|
|
%%% Local Variables:
|
|
%%% mode: latex
|
|
%%% TeX-master: "main"
|
|
%%% End:
|