  Given a simple polygon $\mathcal{P}$ on $n$ vertices, two points $x,y$ in
$\mathcal{P}$ are said to be visible to each other if the line segment between
$x$ and $y$ is contained in $\mathcal{P}$. The Point Guard Art Gallery problem
asks for a minimum set $S$ such that every point in $\mathcal{P}$ is visible
from a point in $S$. The Vertex Guard Art Gallery problem asks for such a set
$S$ subset of the vertices of $\mathcal{P}$. A point in the set $S$ is referred
to as a guard. For both variants, we rule out any $f(k)n^{o(k / \log k)}$
algorithm, where $k := |S|$ is the number of guards, for any computable
function $f$, unless the Exponential Time Hypothesis fails. These lower bounds
almost match the $n^{O(k)}$ algorithms that exist for both problems.
