Separation Results for Boolean Function Classes
This work addresses foundational questions in theoretical computer science by providing separation results that clarify relationships between Boolean function classes, though it appears incremental as it builds on known techniques.
The paper tackles the problem of separating important classes of Boolean functions by demonstrating that the total influence of functions in one class is less than in another, achieving (almost) separation between classes studied in coding theory and cryptography versus those in combinatorics and complexity theory.
We show (almost) separation between certain important classes of Boolean functions. The technique that we use is to show that the total influence of functions in one class is less than the total influence of functions in the other class. In particular, we show (almost) separation of several classes of Boolean functions which have been studied in the coding theory and cryptography from classes which have been studied in combinatorics and complexity theory.