8 lines
1.2 KiB
TeX
8 lines
1.2 KiB
TeX
%!TEX root=./main.tex
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
\section{Parameterized Complexity}\label{sec:param-compl}
|
|
|
|
In \Cref{sec:hard}, we utilized common conjectures from fine-grained complexity theory. The notion of $\sharpwonehard$ is a standard notion in {\em parameterized complexity}, which by now is a standard complexity tool in providing data complexity bounds on query processing results~\cite{param-comp}. E.g. the fact that $k$-matching is $\sharpwonehard$ implies that we cannot have an $n^{\Omega(1)}$ runtime. However, these results do not carefully track the exponent in the hardness result. E.g. $\sharpwonehard$ for the general $k$-matching problem does not imply anything specific for the $3$-matching problem. Similar questions have led to intense research into the new sub-field of {\em fine-grained complexity} (see~\cite{virgi-survey}), where we care about the exponent in our hardness assumptions as well-- e.g. \Cref{conj:graph} is based on the popular {\em Triangle detection hypothesis} in this area (cf.~\cite{triang-hard}).
|