DEVIATION THEOREMS FOR PFAFFIAN SIGMOIDS
Dima Grigoriev · 1994
. By a Pfaffian sigmoid with a depth d we mean a circuit with d layers in which rational operations are admitted at each layer, and to jump to the next layer one solves an ordinary differential equation of the type v 0 = p(v) where p is a polynomial with the coefficients being the functions computed at the previous layers of the sigmoid. Thus, Pfaffian sigmoid computes Pfaffian functions (in the sense of A. Khovanskii). The deviation theorem is proved which states that for a real function 0 6j f computed by a Pfaffian sigmoid with a depth (or parallel complexity) d there exists an integer n such that the inequalities (exp (\\Delta \\Delta \\Delta ( exp (jxj n ) \\Delta \\Delta \\Delta ) \\Gamma1 jf(x)j exp (\\Delta \\Delta \\Delta ( exp (jxj n ) \\Delta \\Delta \\Delta ) hold for all jxj x 0 for a certain x 0 , where the iteration of the exponential function is taken d times. One can treat the deviation theorem as an analogue of the Liouvillean theorem (on algebraic numbers) for Pfaffian...