Example Page 2
In this section we will thoroughly discuss the Polynomial Identity Testing problem, its connections to other problems in computer science and mathematics, and some of its applications.
Polynomial Identity Testing
PIT for Sparse Polynomials
Sparse Polynomials
Klivans-Spielman Hitting Set
Note: I learned the following from Robert Andrews.
We can encode the (homogeneous) Klivans-Spielman curves $\gamma_1, \dots, \gamma_m$ as a polynomial map $G: \mathbb{F}^4 \to \mathbb{F}^N$ as follows:
$$ G(s_1, s_2, t_1, t_2) = \sum_{i=1}^m L_i(s_1, s_2) \cdot \gamma_i(t_1, t_2) $$
where $L_1, \cdots, L_m$ are the Lagrange polynomials for the points $[1 : 1], [1 : 2], \dots, [1 : m]$. That is, we have $$ L_i(s_1, s_2) = \prod_{j \neq i} \frac{s_2 - j \cdot s_1}{i - j} $$
Remark the above procedure is quite general, and allows us to encode any collection of curves as a polynomial map in constantly many variables.