%% HOW TO USE THIS TEMPLATE:
%%
%% Ensure that you replace "YOUR NAME HERE" with your own name, in the
%% \studentname command below. Also ensure that the "answers" option
%% appears within the square brackets of the \documentclass command,
%% otherwise latex will suppress your solutions when compiling.
%%
%% Type your solution to each problem part within
%% the \begin{solution} \end{solution} environment immediately
%% following it. Use any of the macros or notation from the
%% head.tex that you need, or use your own (but try to stay
%% consistent with the notation used in the problem).
%%
%% If you have problems compiling this file, you may lack the
%% head.tex file (available on the course web page), or your system
%% may lack some LaTeX packages. The "exam" package (required) is
%% available at:
%%
%% http://mirror.ctan.org/macros/latex/contrib/exam/exam.cls
%%
%% Other packages can be found at ctan.org, or you may just comment
%% them out (only the exam and ams* packages are absolutely required).
% the "answers" option causes the solutions to be printed
\documentclass[11pt,addpoints]{exam}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{mathtools}
% any of the following packages may be safely omitted if they are not
% available on your system (but they should be)
\usepackage{fullpage}
\usepackage{times}
\usepackage{hyperref}
\usepackage{microtype}
\usepackage[svgnames]{xcolor}
\usepackage{tikz}
\hypersetup{%
colorlinks=true,% hyperlinks will be colored
}
% required macros -- get head.tex file from course web page
\input{head}
% VARIABLES
\newcommand{\hwnum}{3}
\newcommand{\duedate}{November 4} % changing this does not change the
% actual due date :)
\newcommand{\studentname}{YOUR NAME HERE}
% END OF SUPPLIED VARIABLES
\hwheader % execute homework commands
\begin{document}
\pagestyle{head} % put header on every page
\noindent This homework is due by the \textbf{start of class on
\duedate} via the
\href{}{course
Canvas page}. Start early!
\medskip
\noindent \textbf{Instructions.} Solutions must be typeset in \LaTeX\
(a template for this homework is available on the course web page).
Your work will be graded on \emph{correctness}, \emph{clarity}, and
\emph{conciseness}. You should only submit work that you believe to
be correct; if you cannot solve a problem completely, you will get
significantly more partial credit if you clearly identify the gap(s)
in your solution. It is good practice to start any long solution with
an informal (but accurate) ``proof summary'' that describes the main
idea.
\medskip
\noindent You may collaborate with others on this problem set and
consult external sources. However, you must \textbf{\emph{write your
own solutions}} and \textbf{\emph{list your
collaborators/sources}} for each problem.
% QUESTIONS START HERE. PROVIDE SOLUTIONS WITHIN THE "solution"
% ENVIRONMENTS FOLLOWING EACH QUESTION.
\bigskip
\begin{questions}
\question Using an oracle for $\svp_{\gamma}$ for some
$\gamma \geq 1$, show that one can efficiently solve ``almost all''
subset-sum instances of density as large as $C/\log \gamma$, where
$C > 0$ is some universal constant. \emph{Hint:} describe how to
adapt Frieze's attack and analysis. To handle the case
$\gamma = o(\sqrt{n})$, you will need a tighter analysis of the
number of integer vectors of length at most $\gamma\sqrt{n}$.
Consider centering unit cubes at all such points, and use a volume
argument.
\begin{solution}
\end{solution}
\question Let $\matB = (\vecb_{1}, \ldots, \vecb_{n})$ be a set of
linearly independent vectors and let $\matD = (\vecd_{1}, \ldots,
\vecd_{n}) = \matB^{-t}$ be its dual set. Let $(\gs{\vecb}_{1},
\ldots, \gs{\vecb}_{n})$ be the Gram-Schmidt orthogonalization of
$\matB$, and $(\gs{\vecd}_{1}, \ldots, \gs{\vecd}_{n})$ be the GS
orthogonalization of $\matD$ \emph{in reverse order}, i.e.,
$\gs{\vecd}_{n} = \vecd_{n}$, $\gs{\vecd}_{n-1}$ is the component of
$\vecd_{n-1}$ orthogonal to~$\vecd_{n}$, etc.
Prove that $\gs{\vecd}_{i} = \gs{\vecb}_{i} /
\length{\gs{\vecb}_{i}}^{2}$.
\begin{solution}
\end{solution}
\question Define the lattice parameter
$\gs{bl}(\lat) := \min_{\matB} \max_{i} \length{\gs{\vecb}_{i}}$,
where the minimum is taken over all bases $\matB$ of~$\lat$, and
$\set{\gs{\vecb}_{i}}$ denotes the Gram-Schmidt orthogonalization of
$\matB$.
\begin{parts}
\item Prove that
$\smootheps(\lat) \leq \gs{bl}(\lat) \cdot
\sqrt{\ln(2n(1+1/\epsilon))/\pi}$. (\emph{Hint:} use question 2.)
\item In class we proved the above bound with $\lambda_{n}$ in place
of $\gs{bl}$; one can show that
$\gs{bl}(\lat) \leq \lambda_{n}(\lat)$, so the bound here is at
least as good. Show that there exist $n$-dimensional lattices for
which \[ \lambda_{n}(\lat)/\gs{bl}(\lat) \geq \Omega(\sqrt{n}). \]
\emph{Hint:} consider the lattice generated by the standard basis
vectors $\vece_{1}, \ldots, \vece_{n-1}$, and a ``random'' $\vecr$
such that $r_{n}=1$, and show that this works with good
probability.
\end{parts}
\begin{solution}
\end{solution}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: