%%% Document Class

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


%%% Packages

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


%%% Variables

\newcommand{\courseName}{Math 480A2}
\newcommand{\hwNumber}{9}
\newcommand{\hwDueDate}{October 27, 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

\DeclareMathOperator{\AND}{AND}
\DeclareMathOperator{\OR}{OR}

\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{2mm}

\textbf{Problem 1.} (2 points) Let $\phi$ be the boolean formula associated with the expression
\[
	\big((x_1 \wedge x_2) \vee (\bar{x}_1 \wedge \bar{x}_2)\big) \wedge (x_1 \vee x_3)
\]
In the above, recall that ``$\wedge$'' represents an AND gate, and ``$\vee$'' represents an OR gate.  Compute the polynomial described by the arithmetic circuit $\psi$ associated with $\phi$.

\vspace{1mm}

\textbf{Problem 2.} (3 points) Consider the following bivariate polynomials over a field $K$:
\begin{align*}
	\chi_{0,0}(x, y) &= (1-x)(1-y) & \chi_{0,1}(x, y) &= (1-x)y \\
	\chi_{1,0}(x, y) &= x(1-y) & \chi_{1,1}(x, y) &= xy
\end{align*}
Notice that $\chi_{1, 0}(1, 0) = 1$, but $\chi_{1,0}(a, b) = 0$ for every other pair $(a, b)$ of binary inputs, and that the values behave similarly for the other subscripts.  Let $f : \{0, 1\}^2 \to K$ be the function on binary inputs described by the following table:

\begin{center}
	\begin{tabular}{ccc}
		\toprule
		$x$ & $y$ & $f(x, y)$ \\
		\midrule
		0 & 0 & 3 \\
		0 & 1 & 5 \\
		1 & 0 & -1 \\
		1 & 1 & 1 \\
		\bottomrule
	\end{tabular}
\end{center}

Using the polynomials $\chi_{a,b}$ defined above, find a polynomial $\tilde{f}$ such that $\deg_x( \tilde{f} ), \deg_y( \tilde{f} ) \leq 1$, and such that $\tilde{f}(x, y) = f(x, y)$ for all binary inputs.  The function $\tilde{f}$ is called the \emph{multilinear extension} of $f$.  This gives one approach for transforming an arbitrary function on binary inputs into a polynomial, for instance, for use with the sum-check protocol.

\vspace{1mm}

\textbf{Problem 3.} (1 point) Following the pattern of the functions $\chi_{a, b}$ from Problem 2, give a polynomial in $K[x_1, x_2, x_3, x_4, x_5]$ which has degree 1 in each variable, and which is equal to 1 on the input $(1, 0, 1, 1, 0)$ and 0 on every other binary input.

\vspace{1mm}

\textbf{Problem 4.} (3 points) Consider the following univariate polynomials over $\QQ$: % 2 4 5
\begin{align*}
	\ell_2(x) &= \frac{(x - 4)(x - 5)}{(2 - 4)(2 - 5)} &
	\ell_4(x) &= \frac{(x - 2)(x - 5)}{(4 - 2)(4 - 5)} &
	\ell_5(x) &= \frac{(x - 2)(x - 4)}{(5 - 2)(5 - 4)}
\end{align*}
Notice that for $i \in \{2, 4, 5\}$, the polynomial $\ell_i(x)$ is equal to 1 when $x = i$, and is equal to 0 when $x$ is one of the other numbers in $\{2, 4, 5\}$.  (For instance, $\ell_2(2) = 1$, and $\ell_2(4) = \ell_2(5) = 0$.)  Using these polynomials, find a polynomial $f \in \QQ[x]$ of degree at most 2 such that $f(2) = 1$, $f(4) = -1$, and $f(5) = 2$.  The polynomials $\ell_i$ are called the \emph{Lagrange basis polynomials} for the base set $\{2, 4, 5\}$, and give a way to represent a polynomial in terms of its evaluations at a collection of points.

\vspace{1mm}

\textbf{Problem 5.} (1 point) Following the pattern of the functions $\ell_i$ from Problem 4, give a polynomial in $\QQ[x]$ which has degree 3, and is equal to 1 on the point $x = 1$, and 0 on the points $x = 0, 2, 3$.

\end{document}