\documentclass[12pt,a4paper]{article}
\usepackage{iftex}
\ifPDFTeX
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\fi
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\ifPDFTeX
\usepackage{libertine}
\usepackage[libertine]{newtxmath} % must load after ams packages
\usepackage{MnSymbol}
\else
\usepackage{unicode-math}
\setmainfont{Libertinus Serif}
\setmathfont{Libertinus Math}
\fi
\usepackage[DIV=12]{typearea} % large value = less margin, recommended values: 10pt: 8, 11pt: 10, 12pt: 12
\usepackage{microtype}
\usepackage{url}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}
\pagestyle{empty}
\newcommand{\exercise}[2]{
\vspace{3ex}
\textbf{Exercise #1 }(\emph{#2 points)}
\vspace{-0.5ex}
}
\newcommand{\solution}{
\vspace{2ex}
\textbf{Solution:}
\vspace{0.5ex}
}
\newcommand{\course}{PS Complexity of Polynomial-Time Problems}
\newcommand{\website}{\url{https://www.cosy.sbg.ac.at/~sk/courses/polycomp/}}
\newcommand{\sheet}[2]{%
\begin{center}
{\Large \textbf{\course}}
\vspace{0.5ex}
{\footnotesize \website}
\vspace{2ex}
{\large
Exercise sheet #1
\hfill
Due: #2
}
\end{center}
\vspace*{2ex}
}
\newcommand{\lecturer}{Sebastian Krinninger}
\newcommand{\term}{Winter 2017/18}
\DeclareMathOperator{\poly}{poly}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{conjecture}[theorem]{Conjecture}
\begin{document}
\sheet{2}{Sunday, November 19, 2017} % Number, Deadline
\textit{Total points : 40}
\vspace{1ex}
\textit{Prove all your claims!}
%\vspace{2ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{1}{10}
Prove the following: If there is a decision algorithm to check whether for a given pair of sets $ A, B \in \{ 0, 1 \}^d $ there exists a pair of vectors $ a \in A, b\in B $ such that $ a \perp b $ with running time $ O (n^{2-\epsilon} \poly(d)) $ (for some constant $ \epsilon > 0 $), then there also is an algorithm with running time $ O (n^{2-\delta} \poly(d)) $ (for some constant $ \delta > 0 $) that, given pair of sets $ A, B \in \{ 0, 1 \}^d $, ouputs a pair $ a \in A, b\in B $ such that $ a \perp b $ if such a pair exists.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{2}{10}
Consider the \textbf{Longest Palindromic Subsequence} problem: Given a sequence~$S$ of length~$n$, find the longest common subsequence which is a palindrome (i.e., a sequence of characters which reads the same forward and backward).
Prove that, assuming \textbf{OVH}, there is no algorithm for \textbf{Longest Palindromic Subsequence} with running time $ O(n^{2-\epsilon}) $ (for any constant $ \epsilon > 0 $).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{3}{10}
Consider the \textbf{Hitting Set} problem: Given two lists of $ n $ subsets over a universe $ U $ of size $ d = |U| $, determine if there is a set in the first list that intersects every set in the second list, i.e. a ``hitting set''.
The \textbf{HSH} (Hitting Set Hypothesis) states that \textbf{Hitting Set} admits no algorithm with running time $ O (n^{2-\epsilon} \cdot \poly(d)) $ (for any constant $ \epsilon > 0 $).
Prove that \textbf{HSH} implies \textbf{OVH}.
\vspace{2ex}
\textit{\textbf{Hint}: Be careful about the direction this reduction has to go.
In the lecture, we gave a reduction from \textbf{All-Pairs Negative Triangle} to \textbf{Negative Triangle}.
The same type of reduction will work here.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{4}{10}
Recall the following formal definition of \emph{subcubic reductions}:
Let $\mathbf{P}$ and $\mathbf{Q}$ be computational problems with a common size measure $n$ on the inputs.
We say that there is a subcubic reduction from $\mathbf{P}$ to $\mathbf{Q}$ if there is an algorithm $\mathcal{A}$ with oracle access to $\mathbf{Q}$ satisfying three properties:
\begin{itemize}
\item For every instance $x$ of $\mathbf{P}$, $\mathcal{A}(x)$ solves the problem
$\mathbf{P}$ on $x$.
\item Excluding oracle calls, $\mathcal{A}$ runs in time $O(n^{3-\gamma})$ (for some constant $\gamma > 0$) on instances of size $n$.
\item For every constant $\varepsilon>0$ there is a constant $\delta>0$ such that for every instance $x$ of $\mathbf{P}$ of size $n$ we have $\sum_{i}n_{i}^{3-\varepsilon}\leq n^{3-\delta}$, where $n_{i}$ is the
size of the $i$th oracle call to $\mathbf{Q}$ in $\mathcal{A}(x)$.
\end{itemize}
We use the notation $\mathbf{P} \leq \mathbf{Q}$ to denote the existence of a subcubic
reduction from $\mathbf{P}$ to $\mathbf{Q}$.
Prove that subcubic reductions are transitive.
In other words, prove that if $\mathbf{P} \leq \mathbf{Q}$ and $\mathbf{Q} \leq \mathbf{R}$ then $\mathbf{P} \leq \mathbf{R}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}