A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems.
We study bent functions in the framework of property testing. In particular, we ... more >>>

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>

Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n \to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable with a constant number of queries, then one can estimate the distance of a function $f$ from $\cal{P}$ with a constant number of queries. This ... more >>>