\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{color}
%%%%%%%%%%%%%%% MACROS specific to this PSET %%%%%%%%%%%%%%%%%%%%%%
\newcommand{\lat}{\mathcal{L}}
\newcommand{\basis}{\mathbf{B}}
\newcommand{\vol}{\mathsf{vol}}
\newcommand{\sh}{\lambda_1}
%\newcommand{\det}{\mathsf{det}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
%%%%%%%%% Vectors and Matrices
\newcommand{\vecv}{\mathbf{v}}
\newcommand{\vecb}{\mathbf{b}}
\newcommand{\vecbt}{\widetilde{\vecb}}
\newcommand{\vecs}{\mathbf{s}}
\newcommand{\vect}{\mathbf{t}}
\newcommand{\vecy}{\mathbf{y}}
\newcommand{\matB}{\mathbf{B}}
\newcommand{\poly}{\mathsf{poly}}
\newcommand{\Span}{\mathsf{Span}}
\newcommand{\dist}{\mathsf{dist}}
\def\rot{\mathsf{Rot}}
\def\bydef{\stackrel{\Delta}{=}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{CSC 2414 Problem Set 2\\{\large Due: October 31, 2011}}
\author{}
\date{}
\begin{document}
\maketitle
%\input{pset-preamble.tex}
%\lecture{1}{Vinod Vaikuntanathan}{September 13, 2011}{October 3, 2011}
\subsection*{Notes}
\begin{itemize}
\item This problem set is worth $100$ points.
\item Collaboration is allowed, {\em but you must write up the solutions by yourself without consulting to notes from the discussions}. You must also reference your sources.
\item Grading is based on correctness as well as the clarity of the solutions. When writing proofs, it is generally a good idea to first explain the intuition behind your solution in words (wherever appropriate), before jumping in to the formalisms.
\item There is no deadline for the extra credit problem. You can turn in a solution any time until the last class.
\end{itemize}
\subsection*{Problem $1$: Properties of LLL-Reduced Bases (25 points)}
Show that a $\delta$-LLL reduced basis $\vecb_1,\ldots,\vecb_n$ of a lattice $L$ with $\delta = 3/4$
satisfies the following properties.
\begin{enumerate}
\item $\| \vecb_1 \| \leq 2^{(n-1)/4}\cdot \det(L)^{1/n}$.
\item For any $1 \leq i \leq n$, $\| \vecb_i \| \leq 2^{(i-1)/2}\cdot \| \vecbt_i \|$.
\item $\prod_{i=1}^n \| \vecb_i \| \leq 2^{n(n-1)/4}\cdot \det(L)$.
\item For $1 \leq i \leq n$, consider the hyperplane $H = \Span(\vecb_1,\ldots,\vecb_{i-1},\vecb_{i+1},\ldots,\vecb_n)$. Show that \[ \textcolor{red}{2^{-n(n-1)/4} \| \vecb_i \| \leq \dist(H, \vecb_i) \leq \| \vecb_i \|} \]
Hint: use (3).
\end{enumerate}
\subsection*{Problem $2$: Exponential-time Algorithm to find the Shortest Vector (25 points)}
Show an algorithm that solves SVP exactly in time $2^{O(n^2)} \cdot \poly(D)$, where $n$ is the rank of the lattice
and $D$ is the input size. (Hint: show that if we represent the shortest vector in an LLL-reduced basis,
none of the coefficients can be larger than $2^{cn}$ for some constant $c$.)
\subsection*{Problem $3$: Rounding to find an Approximately Close Lattice Vector (25 points)}
Show that there is a constant $c > 0$ such that the
following algorithm, given a basis $\matB \in \Z^{m\times n}$ and a target vector $\vect \in \Z^m$,
finds a lattice point $\vecy \in \lat(\matB)$ where
\[ \| \vecy - \vect \| \leq 2^{cn} \cdot \dist(\vect, \lat(\matB)) \]
\newpage
\textbf{Algorithm Round($\matB, \vect$):}
\begin{enumerate}
\item \textcolor{red}{Run the LLL-reduction algorithm on $\matB$ to get an LLL-reduced basis $\matB'$}.
\item Find $\vecs = (s_1,\ldots,s_n) \in \R^n$ such that $\matB' \vecs = \vect$, say, by Gaussian Elimination.
\item Let $\hat{\vecs} \bydef (\lfloor s_1 \rceil, \ldots, \lfloor s_n \rceil)$ be the vector consisting of the entries of
$\vecs$ rounded to the nearest integer. (e.g., $\lfloor 0.5 \rceil = 1$ and $\lfloor 0.49 \rceil = 0$).
Output $\vecy = \matB' \hat{\vecs}$.
\end{enumerate}
\subsection*{Problem $4$: Running Time of LLL (25 points)}
Show that our analysis of the LLL algorithm using LLL-reduced bases is tight (up to some constant). More specifically,
find a $\delta$-LLL reduced basis $\vecb_1,\ldots,\vecb_n$ for $\delta = 3/4$ such that $\vecb_1$ is longer than the shortest vector
by a factor or $c\cdot 2^{n/2}$, for some constant $c$.
\\
(Note that this does not mean that $\vecb_1,\ldots,\vecb_n$ is the output of the LLL algorithm when run on some input
basis. You do not have to demonstrate that.).
\vspace{0.4in}
\subsection*{Extra Credit**}
\def\gapcvp{\mathsf{gapCVP}}
For any vector $\vecv = (v_1,v_2,\ldots,v_n) \in \Z^n$, let $\rot(\vecv) \bydef (v_2,v_3,\ldots,v_n,v_1)$
denote the cyclic rotation of $\vecv$. A cyclic lattice is one that is closed under the $\rot(\cdot)$ operation. That is,
a lattice $L$ is cyclic if for every $\vecv \in L$, $\rot(\vecv) \in L$ too. Show any of the following:
\begin{itemize}
\item CVP on cyclic lattices is NP-hard (Recall, we saw in class that CVP for general lattices is NP-hard).
\item An interactive proof for $\gapcvp_{\gamma}$ on cyclic lattices, for any $\gamma = o(\sqrt{n/\log n})$, improving on
the Goldreich-Goldwasser interactive proof we saw in class.
\item A polynomial-time algorithm that finds $2^{o(n)}$-approximate shortest vectors on cyclic lattices, improving on
the LLL algorithm.
\end{itemize}
\end{document}