\def\draft{0} \documentclass[11pt]{article} \usepackage{amsfonts,amssymb,fullpage,amsmath} \usepackage{enumitem} \usepackage{xcolor} \usepackage{hyperref} \newcommand{\psnum}{4} %\newcommand{\assdate}{. Jan. 31, 2011} \newcommand{\duedate}{TUE Nov. 17, 2020 (5pm)} \def\inclsolns{0} \input{macros} \newcounter{problem} \newenvironment{problem}[1]{\refstepcounter{problem} \paragraph{Problem \theproblem.#1}} \newcommand{\Cnote}[1]{{\color{red} [CN: #1]}} %\ifnum\inclsolns=1 %\newenvironment{solution}{\paragraph{Solution.}}{} %\else %\newenvironment{solution}{\begin{remove}}{\end{remove}} %\fi \pagestyle{plain} %------------------------------------------------------------------------------$ \usepackage{amsmath} \begin{document} \input{psheader} \begin{problem}{(Final Project Proposal, due Sun. 11/8)} Submit a couple of pages giving a detailed description of what your final project will look like. You should be able to clearly state your research questions, briefly articulate how your project relates to what has been done in the past, describe the approach you are taking, give your timeline for completing various aspects of the project, and discuss your fallback plan in case the project doesn't go as you hope. \end{problem} \begin{problem}{(Limits on Spectral Expansion)} \label{prob:SpectralExpansion-UpperBound} Let $G$ be a $d$-regular unweighted, undirected graph on $n$ vertices and let $T_d$ be the infinite $d$-regular tree with root $r$ (so the root has $d$ children and every other vertex has $d-1$ children and 1 parent). For a graph $H$, vertex $a$ and $\ell\in \N$, let $p_\ell(H;a)$ denote the probability that if we do a random walk of length $2\ell$ started at $a$, we end back at vertex $a$. \begin{enumerate} \item Show that for every vertex $a$ of $G$, we have $p_\ell(G;a) \geq p_\ell(T_d;r) \geq C_\ell\cdot (d-1)^\ell/d^{2\ell}$, where $C_\ell$ is the $\ell$'th Catalan number, which equals the number of properly parenthesized strings in $\{(,)\}^{2\ell}$ --- strings where no prefix has more $)$'s than $($'s. \item Show that $\sum_a p_{\ell}(G;a) \leq 1+(n-1)\cdot \omega(G)^{2\ell}$. \item Using the fact that $C_\ell = {2\ell \choose \ell}/(\ell+1)$, prove that $$\omega(G) \geq \frac{2\sqrt{d-1}}{d}-o(1),$$ where the $o(1)$ term vanishes as $n\rightarrow \infty$ (and $d$ is held constant). \item Extra credit: figure out a generalization of this theorem and proof to directed graphs. (This is intentionally open-ended; we don't know what the best answer is and it could turn into an interesting research problem!) \end{enumerate} \end{problem} \begin{problem}{(The Derandomized Square)} In this problem, you'll see another deterministic (nearly) logpsace algorithm for Undirected S-T Connectivity, which is a closer parallel to the $O(\log^2 n)$ space repeated squaring algorithm we saw. and uses an operation that will come up again later in the course. Let $G$ be a $d$-regular digraph on $n$ vertices, and $H$ a $c$-regular digraph on $d$ vertices. We construct the {\em derandomized square} of $G$ with respect to $H$ to be the following $dc$-regular digraph $\widetilde{G^2}$ on $n$ vertices: For a vertex $u\in [n]$ and edge label $(i,j)\in [d]\times [c]$, we obtain the $(i,j)$-th neighbor of $u$ in $G$ through the steps: \begin{description} \item[I.] Let $v$ be the $i$-th neighbor of $u$ in $G$, and let $i'$ be such that the $i$-th edge leaving $u$ is the $i'$-th edge entering $v$. \item[II.] Let $i''$ be the $j$-th neighbor of $i'$ in the $H$. \item[III.] Let $w$ be the $i''$-th neighbor of $v$ in $G$. \end{description} \begin{enumerate} \item Prove that if $G$ has spectral expansion at least $\gamma=1-\omega$ and $H$ has spectral expansion at least $\theta$, then $\widetilde{G^2}$ has spectral expansion at least $\theta\cdot (1- \omega^2)$. (Hint: write the random-walk matrix for $\tilde{G^2}$ in the form $P (I_n\otimes W_H) L$, where $W_H$ is the random-walk matrix for $H$, and apply matrix decomposition to $W_H$.) \item Suppose we define a sequence of graphs $G_0, G_1,\ldots$, where $G_0$ is obtained by adding self-loops to $G$ to make it regular and aperiodic, and $G_{t+1}$ is a derandomized square of $G_t$ with respect to graphs $H$ taken from an infinite family of $c$-regular expanders with spectral expansion at least $\theta$. (Note that we use a different $H$ at each step as the degrees of the $G_t$'s are growing.) Show that for some constant $\theta<1$ and some $t=O(\log n)$, it is ensured that every connected component of $G_t$ has spectral expansion $\Omega(1)$. \label{part:repeated} \item Let $G_0, G_1,\ldots$ be as in Part~\ref{part:repeated}. Using a sufficiently explicit family of constant-degree expanders $H$, it can be shown that neighbors in $G_t$ can be computed in space $O(\log n + t)=O(\log n)$. Argue that $S$-$T$ connectivity in $G_t$ and hence $G$ can be decided in space $O(\log n\cdot \log\log n)$. (Hint: use the space-efficient repeated squaring algorithm discussed in class.) \item Extra credit: come up with a way to reduce the space complexity to $O(\log n)$ by carrying out a few more derandomized squares with graphs that are powers of graphs in our expander family to reduce the diameter to 1. \end{enumerate} \end{problem} \begin{problem}{(Monotonicity of Current)} Consider an (undirected, as always) resistor network $G=(V,E)$ with resistances $r : E\rightarrow \R^+$. \begin{enumerate} \item Suppose that we send one unit of external current from $a$ to $b$. Let $v$ be the vector of voltages we obtain, and let $\hat{v}$ be the vector of voltages if we remove the edge $(a,b)$. (Assume that this does not disconnect the network.) Show that $$v^\perp = \frac{\hat{v}^\perp}{1+R/r_{a,b}}.$$ where $R$ is the effective resistance between $a$ and $b$ when the edge $(a,b)$ is removed, and $x^\perp$ denotes the component of vector $x$ orthogonal to $\vec{1}$. (Notice that the resistor network is a parallel composition of the edge $(a,b)$ with the rest of the network. Here you are characterizing what happens to the entire vector of voltages under parallel composition, rather than only the effective resistance.) \label{part:voltages} \item Suppose we apply an arbitrary vector $\iext\perp \vec{1}$ of external currents to the network. Show that if we decrease the resistance $r_{a,b}$ on edge $(a,b)$, then the magnitude of current flowing on edge $(a,b)$ cannot decrease. (Hint: express both the $(a,b)$ current here and the voltages from Part~\ref{part:voltages} in terms of $L^+$.) \end{enumerate} \end{problem} \end{document}