Systems of polynomial equations can be solved in average time N^O(log log N)

Mathematics of Computation 1 Minute

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 and deterministic algorithms, average running time of an algorithm, big 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.

The Theorem: On 11th September 2009, Peter Buergisser and Felipe Cucker submitted to arxiv a paper in which they described an explicit deterministic algorithm that computes an approximate solution of any given f \in H with any given accuracy, and proved that the average number of arithmetic operations of this algorithm is N^{O(\log\log N)}, where N is the size of the input.

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 (deterministic) algorithm which could solve systems of polynomial equations with polynomial average running time. In an earlier work, Beltrán and Pardo developed a probabilistic algorithm which achieves this. The Theorem provides a deterministic algorithm with nearly polynomials average running time N^{O(\log\log N)}. In later works, Lairez developed deterministic algorithm with polynomial average time, and also a probabilistic algorithm with quasilinear running time N^{1+o(1)}, see here.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

2 thoughts on “Systems of polynomial equations can be solved in average time N^O(log log N)”

  1. Pingback: Systems of polynomial equations can be solved in expected quasilinear time – Theorems of the 21st century
  2. Pingback: Systems of polynomial equations can be solved in expected polynomial time – Theorems of the 21st century

Leave a comment