Fourier Complexity of cirtemmyS Boolean Functions

Symmetries and the complexity of boolean functions

Emmy Noether was a mathematician who helped create the field of algebra with her brilliant work in the early part of the twentieth century. Her work on algebras, fields, and rings forms the foundation of modern algebra. Just as impressively she proved a critical theorem that is central to modern physics. It connects symmetries to physical laws.

Today I would like to talk about a relatively recent result on symmetric boolean functions. It improves tremendously on previous bounds, and sheds interesting light on a basic complexity question.

One of the central ideas of mathematics is the role of symmetries. There are countless situations where understanding a mathematical object can be enhanced by our ability to understand the symmetries that leave the object, or a related one, invariant.

One of the most striking of such connections is due to Noether: the symmetries of a physical system, properly viewed, determine the physical quantities that are conserved by the system. This famous result is called the Noether’s First Theorem. To quote John Baez:

Noether’s theorem is an amazing result which lets physicists get conserved quantities from symmetries of the laws of nature. Time translation symmetry gives conservation of energy; space translation symmetry gives conservation of momentum; rotation symmetry gives conservation of angular momentum, and so on.

I would like to note two additional examples of the power of symmetry:

• The notion that geometry is the study of symmetries of space is due to Felix Klein and is usually called the Erlangen program.
• The structure of a univariate polynomial is strongly determined by its Galois Group: the group of symmetries of its roots that preserve algebraic relationships.

Let’s turn now to study objects closer to computer science theory, namely boolean functions and their symmetries.

Symmetric Boolean Functions

A symmetric boolean function is a function that is invariant under all permutations . That is,

for all permutations . Another way to think about symmetric boolean functions is such a function only depends on the number of ‘s in the input . Or more formally,

where the sum is the usual sum over the integers and is an arbitrary function from to . The advantage of this representation is that it makes it clear that there are exactly different symmetric functions: just count how many maps there are.

Fourier Structure of Symmetric Functions

One of the basic tools in studying boolean functions is their Fourier coefficients, in particular the size of the coefficients. This applies especially to symmetric boolean functions. In a previous paper we proved:

Theorem: For all sufficiently large , and every non-trivial symmetric boolean function , the size of the least non-zero Fourier coefficient of is at most .

The “we” refers to Mihail Kolountzakis, Evangelos Markakis, Aranyak Mehta, Nisheeth Vishnoi, and myself.

Also a symmetric boolean function is non-trivial provided it depends on all its variables and is not equal to

or its negation. Note the restriction to `non-trivial” boolean functions is necessary: the smallest non-zero Fourier coefficient of the above function is .

In my opinion, the need for the non-triviality condition in such a theorem makes the study of symmetric functions more difficult. Generally theorems of the form

Theorem: All objects X of type have property except for the following exceptions

can be difficult to prove. Even if the exceptional cases are very simple—their existence forces many natural ideas to fail. Some areas of mathematics are more prone to this type of behavior. In group theory, for instance, it strikes me that many theorems have “exceptions”—the main theorem on simple group classification has exceptions.

Amir Shpilka and Avishay Tal have proved a vast improvement to our earlier result. They prove:

Theorem: There is a constant such that for all large enough and non-trivial symmetric boolean functions , the size of the least non-zero Fourier coefficient is at most .

I have touched on their work earlier—see this. I guess I wanted to say some more about the whole problem—I hope that is alright.

This is a huge improvement—they have reduced slightly sub-linear to almost a square root bound. While this is a beautiful result, there is no evidence that it is optimal, and so this may be a good problem to work on. When we worked on proving our much weaker theorem, we could see no reason that the correct answer might not be even . That is we could not rule out whether every non-trivial symmetric boolean function has a non-zero Fourier coefficient of size independent of .

Proof Sketch-Sketch

See their paper for a clear exposition of their theorem, and for its connection to the Junta problem. I will just give a very high-level description of what they do.

The key is that the Fourier structure is related directly to the bias of the function. Suppose that is a symmetric boolean function. Define as the value that obtains on inputs of weight : that is inputs with of the inputs ‘s. The bias of is equal to

The main insight is assume that has no small non-zero Fourier coefficient, then one can find linear relationships that satisfies. For example,

for some constant and . Here is a prime—it must be a prime, since the proof depends on properties of binomial coefficients modulo primes.

A contradiction can be found, after a clever argument, by showing that there are too many of such linear relationships. Again see their paper for the full story. One of the reasons I like this problem, and I like their result is that there is a deep connection between this problem and certain interesting number theory questions.

Indeed their bound can be improved from to if a certain number theory conjecture is true. Note if one could prove that was optimal, then one would show that widely believed number theory conjectures are false. This would be an incredible result—probably an impossible result, but you never know.

Open Problems

What is the correct order of magnitude for the least non-zero Fourier coefficient of a non-trivial symmetric boolean function? Are there lower bounds that show that the size at least grows with ?