Igor E. Shparlinski

Lower bounds are obtained on the degree and the number of monomials of

Boolean functions, considered as a polynomial over $GF(2)$,

which decide if a given $r$-bit integer is square-free.

Similar lower bounds are also obtained for polynomials

over the reals which provide a threshold representation

more >>>

Anna Bernasconi, Igor E. Shparlinski

In this paper we extend the area of applications of

the Abstract Harmonic Analysis to the field of Boolean function complexity.

In particular, we extend the class of functions to which

a spectral technique developed in a series of works of the first author

can be applied.

This extension ...
more >>>