Systems of polynomial equations can be solved in expected quasilinear time

You need to know: Complex numbers, polynomials in complex variable, notation ${\mathbb C}^n$ for set of vectors $z=(z_1, \dots, z_n)$ with complex $z_i$ , algorithm, probabilistic algorithm, average running time of an algorithm, big O notation, small o notation.

Background: Let $n>0$ be a positive integer. Let H be the space of all systems $f = [f_1,\dots ,f_n]:{\mathbb C}^n \to {\mathbb C}^n$ on n polynomial equations in n unknowns. For $f \in H$ , denote $V_{\mathbb C}(f) = \{x \in {\mathbb C}^n : f_i(x) = 0, \, 1 \leq i \leq n\} \subset {\mathbb C}^n$ the set of solutions of $f$ . Also, denote $D$ the maximal degree of a polynomial in f, and $N$ the number of bits needed to write down the system f (that is, write down all coefficients of all polynomials in f).

The Theorem: On 9th November 2017, Pierre Lairez submitted to arxiv and the Journal of the AMS a paper in which he described an explicit probabilistic algorithm that computes an approximate solution of any given $f \in H$ with any given accuracy (with probability 1), and proved that the average number of arithmetic operations of this algorithm is $O(n^6D^4N)$ .

Short context: Solving polynomial equations and systems of such equations is one of the fundamental problems in the whole mathematics. In 1998, Smale presented a list of problems he considered as the most important ones for the 21st century. Smales 17th problem asks for the algorithm which could solve systems of polynomial equations with polynomial average running time. In 2009, Beltrán and Pardo presented a probabilistic algorithm that achieves this (see here for deterministic version). The Theorem provides a much faster algorithm. In fact, $N\geq 2^{\min(n,D)}$ , hence the running time $O(n^6D^4N)$ in the Theorem is $N^{1+o(1)}$ when $\min(n,D) \to \infty$ .