\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}
