\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 1}
\date{Spring 2026}

\begin{document}

\maketitle

This homework is due in class Friday April 17th 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}[$\bpp = \ap$, 30 points]
Let $A:\{0,1\}^\ast \rightarrow \{0,1\}$ be a function from the set of binary strings of any length to $\{0,1\}$. The class $P^A$ is then the class of languages computable in polynomial time with oracle access to $A$. That is a function that can be computed in polynomial time by a program that can evaluate $A$ on any given string in constant time. The class $\ap$ is the class of languages $L$ so that for a random $A$ we have that $L\in P^A$ with probability $1$. Prove that $\bpp = \ap$.
\begin{enumerate}[(a)]
\item Show that $\bpp \subset \ap$. Hint: Use the oracle to produce random inputs. You might need an argument along the lines of the one we say in the proof of Adelman's Theorem to ensure that you get the correct answer on \emph{all} inputs. [15 points]
\item Show that $\ap \subset \bpp$. Hint: If $L\in \ap$ there must be some algorithm $B(x,A)$ that with positive probability over $A$ correctly determines whether $x\in L$ for all $x$. A basic fact about measure theory implies that there is some finite set of strings $s_i$ and values $v_i \in \{0,1\}$ so that if we condition on $A(s_i)=v_i$ for all $i$, then this probability is at least $2/3$. Given this, build a $\bpp$ algorithm by simulating this program on a random $A$ with this conditioning. [15 points]
\end{enumerate}
\end{ques}

\begin{ques}[Local Maximum Concentration, 45 points]
For $n\geq 2$ let $X_n$ be the number of local maxima of a random permutation of $\{1,2,\ldots,n\}$. Recall that we showed in class that $\mu_n := \E[X_n] = (n+1)/3.$
\begin{enumerate}[(a)]
\item Compute $\var(X_n).$ [20 points]
\item Using Chebyshev's Inequality, find a number $T_n$ so that $X_n - \mu_n < T_n$ with probability at least $99.99\%$. [5 points]
\item While we cannot use Chernoff bounds directly, we can write $X_n$ as the sum of three random variables each of which is a sum of bounded, independent random variables. Applying Chernoff bounds to this, find a $T_n'$ so that $X_n - \mu_n < T_n'$ with probability at least $99.99\%$. [20 points]
\end{enumerate}
\end{ques}

\begin{ques}[Yao's Minimax Principle for $\bpp$, 25 points]
We've discussed Yao's Minimax Principle for the runtime of an algorithm, but there is also a version for the probability of success. Consider a query problem where one is trying to find the best possible randomized algorithm that makes at most a bounded number ($N$) queries. We say that such an algorithm $A$ succeeds with probability $p$ in the worst case if for all inputs $x$, $A$ makes at most $N$ queries and with probability at least $p$ returns the correct answer for that input. On the other hand, if we fix a distribution $D$ over inputs, the average case probability of success of such an algorithm $A$ with respect to this distribution is the probability that if an input $x$ is selected according to $D$ and $A$ is run on this input that $A$ computes the correct answer for that input.

Prove that for any such problem, the maximum possible worst case probability of success of a randomized algorithm $A$ is the same as the minimum over distributions $D$ over inputs of the maximum possible average case probability of success of a deterministic algorithm $A$.
\end{ques}

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

\end{document}