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

\newcommand{\ZETTELNUMMER}{5}

\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{\#P} 

Show that the following problem (a) is in FP and  (b) and (c) are in \#P and, thus, \#P-complete.

\begin{enumerate}
\item Computing the permanent of a matrix with entries from $\{0,1\}$ in $\mathbb{Z}_2$.
 \item Computing the permanent of a matrix with entries from $\{0,1\}$ in $\mathbb{Q}$.
 \item \#LEXT
\end{enumerate}


\AUFGABE{FPRAS}

Show that to any FPRAS there exists an equivalent $(\varepsilon, \delta)$-FPRAS.

\AUFGABE{stationary distribution}

Determine (by calculation or experimentally) the stationary distribution for the 2-state Markov chain example in the course.

\AUFGABE{irreducible}

Show that the Markov chain corresponding to the random walk in the algorithm of Dyer/Frieze/Kannan is irreducible

\AUFGABE{lollipop graph}

The {\em lollipop graph} on $n$ vertices is a clique on $n/2$ vertices with  a path on $n/2$ vertices attached to some vertex $u$ of the clique, Let $v$ be the other end of the path. 
The graph is undirected and the transition probabilities from a node $w$ to its neighbors are all $1/d(w)$ where $d(w)$ is the degree of $w$. Show that $h_{uv}= \Theta(n^3)$ whereas $h_{vu}= \Theta(n^2)$.


\end{description}
\end{document}
