%%% Document Class

\documentclass[11pt]{letter}
\usepackage[margin=1in]{geometry}


%%% Packages

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathtools}


%%% Variables

\newcommand{\courseName}{Math 480A2}
\newcommand{\hwNumber}{8}
\newcommand{\hwDueDate}{October 20, 2022}


%%% Definitions

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\iff}{\leftrightarrow}

\renewcommand{\vec}[1]{\mathbf{#1}}

\DeclareMathOperator{\Prob}{Pr}               % probability
\newcommand{\Exp}{\mathbb{E}}                 % expected value
\newcommand{\C}{{\rm c}}                      % complement
\newcommand{\card}[1]{\left|#1\right|}        % cardinality
\newcommand{\Pv}{\mathcal{P}}                 % prover
\newcommand{\Vf}{\mathcal{V}}                 % verifier


\renewcommand{\theenumi}{\Alph{enumi}}
\newcounter{saveenum}

%%% Document

\begin{document}

\begin{center}
	{\large \courseName, Homework \hwNumber}\\
	Due \hwDueDate\\
\end{center}

{\small \textit{Homework is graded out of a total of 10 points.  Collaboration is permitted, but you must list all coauthors on a problem's solution at the top of the page, and your writing must be your own.}}

\vspace{5mm}

\textbf{Problem 1.} (3 points) Consider the following variant of Freivalds' algorithm for checking the product of two matrices.  Let $A, B, C$ be $n \times n$ matrices with entries in a finite field $K$.  To check whether $AB = C$, let $x = (r_1, r_2, \ldots, r_n)$ be a vector with entries chosen uniformly at random from $K$, and check if $A (B x) = Cx$.  If this equality holds, conclude that $AB = C$, and otherwise, conclude that $AB \neq C$.

(Recall that in our original formulation of Freivalds' algorithm, we used a vector of the form $(1, r, r^2, \ldots, r^{n-1})$ for a single random value $r$ in $K$.  Now we instead choose all random entries.)

If $AB = C$, then it will always be the case that $A (Bx) = Cx$ because $A (Bx) = (AB) x$ for any matrices $A$ and $B$.  In the case that $AB \neq C$, use the Schwartz-Zippel lemma to prove that this algorithm will fail to successfully detect this fact with probability at most $1 / \card{K}$.

\vspace{3mm}

\textbf{Problem 2.} (4 points) Give a possible transcript of the execution of the sum-check protocol in which a prover demonstrates to a verifier that, over $\ZZ / 11 \ZZ$,
\[
	\sum_{x, y, z \in \{0, 1\}} 2x + y^2 z = 10
\]

\vspace{3mm}

\textbf{Problem 3.} (3 points) Considering the sum from Problem 2 again, suppose a malicious prover $\Pv'$ knows ahead of time that the first random value chosen by $\Vf$ in the sum-check protocol will be $r_1 = 2$.  What polynomial $g_1(y)$ can $\Pv'$ send to $\Vf$ as the first message of the first round so that $\Pv'$ can convince the verifier that the sum in Problem 2 is actually 3?  How should $\Pv'$ proceed after this to cause $\Vf$ to accept the claim?

\end{document}