  We improve lower bounds on the $k$th-order nonlinear complexity of
pseudorandom sequences over finite fields and we establish a probabilistic
result on the behavior of the $k$th-order nonlinear complexity of random
sequences over finite fields.
