Sequences with high nonlinear complexity

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.