\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\var}{\mathrm{Var}}

\newcommand{\bpp}{\mathbf{BPP}}
\newcommand{\ap}{\mathbf{Almost\text{-}P}}

\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}


\title{CSE 203A Homework 3}
\date{Spring 2026}

\begin{document}

\maketitle

This homework is due in class Friday May 15th 11:59pm on gradescope. Make sure to justify all of your answers with a mathematical proof. For algorithms you should both prove correctness (with appropriately small probability of error) as well as appropriate bound on runtime.

\begin{ques}[Slow Random Walk for 2-SAT, 20 points]
Show that for the random walk algorithm for 2-SAT discussed in class that there are satisfiable instances of 2-SAT on $n$ variables so that for some initial guesses, the expected time to find a satisfying assignment is $\Omega(n^2)$.
\end{ques}

\begin{ques}[Random Graphs and Expanders, 30 points]
Let $n$ and $d$ be sufficiently large integers with $nd$ even. Let $G$ be a random $d$-regular multigraph selected by finding a random pairing of the $dn$ vertex-edge pairs. Show that:
$$
\Pr(h(G) < d/3) < 1/n.
$$

Hint: you may use the fact that the Chernoff bounds still hold if the $X_i$'s are not independent but instead if $\E[X_i|X_{i-1},X_{i-2},\ldots,X_1]$ is a decreasing function of $X_1+X_2+\ldots+X_{i-1}$ for each $i$.
\end{ques}

\begin{ques}[Expander Cover Times, 30 points]
Let $G$ be a $d$-regular graph on $n$ vertices where all eigenvalues of the adjacency matrix other than the principle one have absolute value at most $d/2$.
\begin{enumerate}[(a)]
\item Let $S$ be a set of vertices, and $v$ a specific vertex. Let $h_{v,S}$ be the expected time for a random walk starting at $v$ to reach some vertex in $S$. Prove that
$$
\E_v[h_{v,S}] = O(n/|S|).
$$
Hint: Look at eigenvalues of $RPR$ where $R$ is the linear transformation that zeroes out the coefficients of vertices in $S$. [20 points]
\item Show that for any $v,S$ that $h_{v,S} = O(n/|S|+\log(n))$. [5 points]
\item Show that the cover time of $G$ is $O(n\log(n))$. [5 points]
\end{enumerate}
\end{ques}

\begin{ques}[Doubling Graph, 20 points]
Let $G$ be the graph with vertex set $\Z/p$ for some prime $p$ and edges connecting $x$ to $x+1,x-1,2x,x/2$ mod $p$. Show that the transition matrix of $G$ has a non-principle eigenvector with eigenvalue $1-O(1/\log(p))$. Hint: Consider the transition matrix in the Fourier basis.
\end{ques}

\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}

\end{document}