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