# Lagrange Interpolation
Lagrange interpolation is a technique to construct a single polynomial that exactly passes through a given set of points $(x_1, y_1),(x_2,y_2)...(x_n, y_n)$.
## Use cases
Lagrange interpolation is widely used in
* probabilistically checkable proof
* interactive proof systems
* error-correcting codes, a

In this post, I explain Lagrange intepolation applied on unvariate (e.g $f(x) =4x^2 + 3x +2$) and multilinear (e.g f(x, y) = 4xy +5x +2) polynomials.

## Univariate Lagrange Interpolation

Let $P$ be a Lagrange polynomial
$(y_0...y_n)$ are evaluations of P in points $(x_0..x_n)$
$P(x) \;=\; \sum_{i=0}^{n} y_i \,\ell_i(x) (1.0),
\qquad
\ell_i(x) \;=\; \prod_{\substack{0 \le j \le n \\ j \neq i}}
\frac{x - x_j}{x_i - x_j}. (1.1)$

Example:
points $(x_i, y_i)$ = (0,1),(1,3),(2,2)
Goal: Compute P
1. compute $l_0...l_2$ using 1.1
$l_0(x) = (x-1)(x-2) / ((0-1)(0-2)) = (x-1)(x-2)/2$
$l_1(x) = (x-0)(x-2) / (1-0)(1-2) = -x(x-2)$
$l_2(x) = (x-0)(x-1) / ((2-0)(2-1)) = x(x-1)/2$
2. compute P using 1.0
$P(x) = 1 * (x-1)(x-2)/2 - 3x(x-2) + x(x-1)$
$P(x) = -x^2 + 3x + 1$

## Multilinear extensions and Multilinear lagrange interpolation

Multilinear extensions (MLE) and multilinear lagrange interpolation are keys to prover's performance.

* Multilinear extension builds a polynomial of degree at most 1 in each variable to match a function on the $2^n$ Boolean points.

Example: n = 3, $p(x_1...x_3) = x_1*x_2 +x_3 +x_1*x_3$ is multilinear if a degree on each term is at most one.

Let f be a function : {0,1}ⁿ - > $F^n$ that maps a bit string to a field element of field F.

A bit-string of length n is an element of {0,1}ⁿ.
Example: n = 3: “000”, “001”, “010”, “011”, “100”, “101”, “110”, “111”

Fact: for any function f: {0,1}ⁿ - > $F^n$ there exists a one multilinear polynomial $\tilde{f}$, $\tilde{f}$ is multilinear extension(MLE) of f
$\tilde{f}$ called an extension cause it has larger domain $F^n$

$f(x_1, x_2, x_3)$
$\tilde{f(x_1, x_2, x_3)}$ = $f(x_1, x_2, x_3)$ + $x_1(1-x_1)$
$x_1(1-x_1)$ = 0 for all x $\in$ {0,1}

### Examples of MLE
$AND(x_1, x_2)$
* (0, 1), (0,0), (1, 0) -> 0
* (1, 1) -> 1

$\tilde{AND(x_1, x_2)}$ = $x_1*x_2$ is MLE
Similarly,
$\tilde{OR(x_1, x_2)}$ = $x_1$ + $x_2$ - $x_1*x_2$

### Equality function
Let x = $(x_1...x_n)$, y = $(y_1...y_n)$
$EQ(x,y)$ = 1 if $x_i = y_i$ for i = 1..n else 0

$\tilde{EQ(x, y)}$ = $\prod_{i=0}^{n} x_iy_i + (1-x_i)(1-y_i)$

## Multilinear Lagrange interpolation

Let $f$: {0,1}ⁿ -> F, $\widetilde{f}$ is MLE of $f$, $r \in$ {0,1}ⁿ
$\widetilde f(r)
\;=\;
\sum_{y\in\{0,1\}^n}
f(y)\tilde{EQ(r, y)}$ is Multilinear lagrange intepolation

**Multilinear lagrange intepolation** is a fast algorithm, given an input f(y) quickly computes the sum $\sum_{y\in\{0,1\}^n}
f(y)\tilde{EQ(r, y)}$