\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{\matB}{\mathbf{B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% MACROS specific to this PSET %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% Vectors and Matrices
\newcommand{\vecbt}{\widetilde{\vecb}}
\newcommand{\vecs}{\mathbf{s}}
\newcommand{\vect}{\mathbf{t}}
\newcommand{\vecy}{\mathbf{y}}
\newcommand{\poly}{\mathsf{poly}}
\newcommand{\Span}{\mathsf{Span}}
\newcommand{\dist}{\mathsf{dist}}
\def\rot{\mathsf{Rot}}
\def\bydef{\stackrel{\Delta}{=}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\input{pset-preamble.tex}
\lecture{1}{Vinod Vaikuntanathan}{October 3, 2017}{October 24, 2017}
\subsection*{Notes}
\begin{itemize}
\item This problem set is worth $90$ 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 {\em Notation:} $\N$ denotes the natural numbers, $\Z$ denotes the integers, $\Q$ denotes rational numbers and $\R$ the set of real numbers.
\end{itemize}
\subsection*{Problem $1$: Bases (10 points)}
Describe a procedure that given any set of vectors $\vecb_1, \ldots, \vecb_n \in \mathbb{Z}^m$,
find a basis for the lattice $\lat(\vecb_1, \ldots, \vecb_n)$ (notice that these vectors are not necessarily linearly independent
and that in particular, $n$ might be greater than $m$). There is no need to analyze the
running time. A corollary is that any set of vectors in $\mathbb{Z}^m$ spans a lattice.
\subsection*{Problem $2$: Minkowski's First Theorem (20 points)}
Despite lattices with much shorter vectors than predicted, Minkowski's theorem is tight for general lattices. In particular, there is a family of lattices $\{\lat_n\}_{n\in \mathbb{N}}$ where $\lat_n$ lives in $n$ dimensions, and
\[ \sh(\lat_n) \geq c\cdot \sqrt{n}\cdot \det(\lat_n)^{1/n}\]
where $c$ is a universal constant independent of $n$.
Show that such a family of lattices exists (your proof doesn't have to construct this family, you merely have to show existence).
\subsection*{Problem $3$: Properties of LLL-Reduced Bases (15 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(\lat(\matB))^{1/n}$.
\item For any $1\leq i\leq n$, $||\lambda_i(\lat(\matB)) \leq 2^{(i-1)/2} \cdot ||\vecbt_i||$.
\item For any $1\leq i\leq n$, $||\lambda_i(\lat(\matB)) \geq 2^{-(n-1)/2}\cdot ||\vecb_i||$.
\end{enumerate}
\subsection*{Problem $4$: Running Time of LLL (15 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$.
\subsection*{Problem $5$: LLL Weirdness (15 points)}
Find a basis $\matB$ such that after we apply one reduction step of the LLL algorithm to it, the maximum length of a vector in it {\em increases} by $\Omega(\sqrt{n})$.
\subsection*{Problem $6$: SIVP and CVP (15 points)}
Show a reduction from the closest vector problem (CVP) to the shortest independent vectors problem (SIVP). Recall that in SIVP, you are given a basis $\matB$ of a full-rank lattice $\lat \subseteq \mathbb{Z}^n$ and you are asked to produce $n$ linearly independent vectors $\mathbf{v}_1,\ldots,\mathbf{v}_n \in \lat$ such that $||\vecv_i|| \leq \lambda_i$.
For extra credit, show an approximation-preserving reduction. That is, given an oracle to solve $\gamma$-approximate SIVP, can you solve $\gamma$-CVP for some $\gamma > 1$? Here, in $\gamma$-approximate SIVP, you are only required to produce vectors $\vecv_i$ as above where $||\vecv_i|| \leq \gamma \cdot \lambda_i(\lat)$.
\end{document}