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