\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}{0.5ex}
\pagestyle{empty}
\newcommand{\exercise}[2]{
\vspace{3ex}
\textbf{Exercise #1 }(\emph{#2 points)}
}
\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{1}{Sunday, October 29, 2017} % Number, Deadline
\textit{Total points : 40}
\vspace{1ex}
\textit{Prove all your claims!}
\vspace{2ex}
\textbf{Reminder:} In the lecture we have introduced the \emph{Orthogonal Vectors Hypothesis}:
\textbf{OVH}: Given two sets $A,B\subseteq\{0,1\}^{d}$ such that $ |A| = |B| = n $, there is no algorithm running in time $ O (n^{2-\epsilon} \cdot \poly(d))$ (for any constant $\epsilon > 0$) which decides whether there exist $ a \in A$ and $ b\in B $ such that $ a $ and $ b $ are orthogonal.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{1}{10}
Consider the following variant $\textbf{OVH'}$ of \textbf{OVH}:
$\textbf{OVH'}$: Given a set $ A \subseteq \{0,1\}^d $ such that $|A|=n$, there is no algorithm running in time $ O (n^{2-\epsilon} \cdot \poly(d))$ (for any constant $\epsilon > 0$) which decides whether there exist $ a, a' \in A $ such that $ a $ and $ a' $ are orthogonal.
Show that $\textbf{OVH'}$ and $\mathbf{OVH}$ are equivalent.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{2}{10}
Design an algorithm for the orthogonal vectors problem with running time $ O (2^d n d) $.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{3}{10}
Given two sets $A,B\subseteq\{0,1\}^{d}$ such that $ |A| = |B| = n $, construct a Boolean formula $ \varphi $ of size $ O (n d) $ such that $ \varphi $ is satisfiable if and only if there exist $ a \in A$ and $ b\in B $ such that $ a $ and $ b $ are orthogonal.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{4}{10}
Consider the \textbf{Max Inner Product} problem: Given two sets $ A, B \subseteq \mathbb{Z}^{d} $ such that $ |A| = |B| =n $, find the value of the maximum inner product between any vector $a$ from $A$ and $b$ from $B$, i.e, compute the quantity $ \max_{a \in A, b \in B} \langle a, b \rangle $.
Show that, assuming \textbf{OVH}, there is no algorithm for \textbf{Max Inner Product} with running time $ O(n^{2-\epsilon} \cdot \poly(d))$ for any constant $ \epsilon > 0 $.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}