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

\newcommand{\dist}{\operatorname{dist}}
\newcommand{\diam}{\operatorname{diam}}
\newcommand{\bc}{\operatorname{BC}}

\begin{document}

\sheet{5}{Sunday, January 15, 2018} % Number, Deadline

\textit{Total points : 40}

\vspace{1ex}

\textit{Prove all your claims!}

%\vspace{2ex}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\exercise{1}{10}

In the $\mathbf{X+Y}$ problem, we are given two sets of integers $ X $ and $ Y $ of size $ |X| + |Y| = n $ and are asked to decide if the set $ X + Y := \{ a + b \mid a \in X, b \in Y \} $ has size $ |X + Y| = n^2 $, i.e., if the pairwise addition created no duplicates.

Show that if $\mathbf{X+Y}$ can be solved in them $ O (n^{2 - \epsilon}) $ for some $ \epsilon > 0 $, then \textbf{3SUM} can be solved in time $ O (n^{2 - \delta}) $ for some $ \delta > 0 $.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\exercise{2}{10}

The problem \textbf{3SUM} can be generalized to \textbf{$k$-SUM} as follows: Given $ k $ sets $ A_1, A_2, \dots, A_k $ of $ n $ integers each, are there $a_1 \in A_1, a_2 \in A_2, \dots, a_k \in A_k $ such that $ a_1 + a_2 + \dots + a_k = 0 $?

Give a \textbf{$k$-SUM} algorithm with running time $ O (n^{\lceil \frac{k}{2} \rceil} \log n) $ for constant $ k $.

\textit{Hint:} Which operations could introduce a factor of $ \log{n} $ in the running time? 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\exercise{3}{10}

Show that if \textbf{$k$-SUM} can be solved in time $ n^{o(k)} $, then \textbf{3SAT} can be solved in time $ 2^{o(n)} $.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\exercise{4}{10}

Design your own exercise problem and write down a solution.
The collected problems will be distributed as a preparation for the final exam.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
