A Note on the Finite Variance of the Averaging Function for Polynomial System Solving

摘要

In the forthcoming paper of Beltran and Pardo, the average complexity of linear homotopy methods to solve polynomial equations with random initial input (in a sense to be described below) was proven to be finite, and even polynomial in the size of the input. In this paper, we prove that some other higher moments are also finite. In particular, we show that the variance is polynomial in the size of the input.