Abstract
We study Boolean functions derived from Fermat quotients modulo p using the Legendre symbol. We prove bounds on several complexity measures for these Boolean functions: the nonlinearity, sparsity, average sensitivity, and combinatorial complexity. Our main tools are bounds on character sums of Fermat quotients modulo p.