\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage[ngerman]{babel}
\usepackage{fullpage}
\usepackage{graphicx}

\newcommand{\ZETTELNUMMER}{9}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[1]{\vspace{0.3cm}\item[Problem \arabic{AUFGNR}]\stepcounter{AUFGNR} #1}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}

\DeclareMathOperator{\CH}{\text{CH}}
\DeclareMathOperator{\R}{\mathbb{R}}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER th Problem Set for the MDS Block Course on

\medskip
\noindent
\large
\textbf{High-Dimensional Computational Geometry} 

\medskip
\noindent
\normalsize
Helmut Alt, Wolfgang Mulzer\hfill Summer 2013

\medskip\hrule

\bigskip
\noindent
The problems will be discussed in the afternoon session.\\


%\vskip 0.5cm

\begin{description}
\AUFGABE{Metric spaces} 

Which of the following pairs $(X,\rho)$ are metric spaces:

\begin{enumerate}
 \item $X=\mathbb{R}^d, \rho(x,y)= \|x-y\|_2$
 \item $X=\mathbb{R}^d, \rho(x,y)= \|x-y\|^2_2$
 \item $X$ is the set of continuous parameterized curves $f:[0,1] \rightarrow \mathbb{R}^d$, $\rho$ is the Fr\'{e}chet distance.
 \item $X= \Sigma^*$, i.e., the set of all strings over a finite alphabet $\Sigma$, $\rho(x,y)$ is the edit distance between strings $x$ and $y$, i.e., 
 the minimum number of insertions, deletions, or replacements of characters necessary to transform $x$ into $y$.
\end{enumerate}


\AUFGABE{Embeddings}

\begin{enumerate}
 \item Can every metric space of three elements be isometrically embedded into $\ell ^2_2$?
 \item Show that the two examples of 4-point metric spaces (square and star) shown in the course cannot be isometrically embedded into $\ell ^d_2$ for any $d \in \mathbb{N}$.
 \item What is their minimum distortion when embedded into $\ell ^2_2$? 
\end{enumerate}



\AUFGABE{Johnson-Lindenstrauss}

In the proof of the Johnson-Lindenstrauss Theorem we chose $k= 200  \varepsilon^{-2} \ln(n)$. 
\begin{enumerate}
 \item Replace $200$ by the smallest constant that is possible if $n \ge 10$, say.
 \item Find a constant such that the probability, that the projection into a randomly chosen $k$-dimensional subspace is a $(1+ \varepsilon)$-embedding is greater than $1-1/n$.
 Which constant is necessary for the bound $1-1/n^r$?
\end{enumerate}
 

\end{description}
\end{document}
