Studies in Boolean Function Analysis

Abstract

Boolean functions are important in both theoretical computer science and cryptography. Over the past few decades, significant advancements have been made in this area. The Walsh transform, a variant of the Fourier transform applied to the function $(-1)^g$, where $g$ is a Boolean function, is a vital tool for studying Boolean functions in both fields. The Walsh/Fourier coefficients of a Boolean function offer insights into its properties, and many concepts in both areas can be interpreted in terms of these coefficients. Hence, it is reasonable to assume that analyzing Boolean functions from both perspectives is interconnected, and results from one area can be applied to the other to obtain new outcomes or improve established proof techniques. However, surprisingly, the theory of Boolean functions developed almost parallel in these two fields. The objective of this thesis is to investigate and establish connections between various concepts of Boolean functions used in theoretical computer science and cryptography. Through our research, we have solved several existing problems, introduced new ones, and obtained results related to these problems. Furthermore, we have developed new concepts in Boolean function analysis and their applications that are pertinent in both theoretical computer science and cryptography. In the course of our research, we have shown a general counterexample to the ``Majority is Least Stable'' conjecture, which was previously shown only for $n=5$. We have also proposed the first-ever lower bound for the ``Fourier min-entropy/influence conjecture'' in this thesis. Additionally, we utilized programming techniques to explore and unveil some intriguing counting results associated with unate functions and Dedekind numbers.