On Boolean Functions associated to Bipartite Cayley Graphs
Anna Bernasconi, Bruno Codenotti · 2000
In [1] we showed that any Boolean function can be associated to a Cayley graph whose spectrum coincides with the Walsh spectrum of the function, and used this idea to investigate the spectrum of certain special functions. In this paper we further exploit this idea by studying the class of functions whose associated Cayley graph is bipartite. We derive an algebraic characterization for these functions, analyze their circuit complexity and argue that some of them might be of interest for cryptographic applications.