Before revision: We design a probabilistic algorithm that , given \epsilon>0 and a polynomial system F given by black-box evaluation functions, outputs an approximate zero of F, in the sense of Smale, with probability at least 1-\epsilon.
After revision: This work studies the average complexity of solving structured polynomial systems that are characterized by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system F given by black-box evaluation functions, outputs an approximate zero of F, in the sense of Smale, with probability at least 1-\epsilon.