Skip to content

Fourier Complexity of cirtemmyS Boolean Functions

January 5, 2011


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 {f:\{0,1\}^n \rightarrow \{0,1\}} that is invariant under all permutations {\pi}. That is,

\displaystyle  f(x_1,\dots,x_n) = f(x_{\pi(1)},\dots,x_{\pi(n)}),

for all permutations {\pi}. Another way to think about symmetric boolean functions is such a function {f(x)} only depends on the number of {1}‘s in the input {x=x_1,\dots,x_n}. Or more formally,

\displaystyle  f(x) = g(x_1 + x_2 + \cdots + x_n),

where the sum is the usual sum over the integers and {g(w)} is an arbitrary function from {\{0,1,2,\dots,n\}} to {\{0,1\}}. The advantage of this representation is that it makes it clear that there are exactly {2^{n+1}} different symmetric functions: just count how many maps {g} 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 {n}, and every non-trivial symmetric boolean function {f(x_1,\dots,x_n)}, the size of the least non-zero Fourier coefficient of {f} is at most {4n/\log_2 n}.

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

\displaystyle  x_1 \oplus \dots \oplus x_n,

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

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 {\dots} have property {\dots} except for the following exceptions {\dots}

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 {26} exceptions.

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

Theorem: There is a constant {c > 0} such that for all large enough {n} and non-trivial symmetric boolean functions {f(x_1,\dots,x_n)}, the size of the least non-zero Fourier coefficient is at most {cn^{0.525}}.

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 {O(1)}. That is we could not rule out whether every non-trivial symmetric boolean function has a non-zero Fourier coefficient of size independent of {n}.

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 {f(x_1,\dots,x_n)} is a symmetric boolean function. Define {F(k)} as the value that {f} obtains on inputs of weight {k}: that is inputs with {k} of the inputs {1}‘s. The bias of {f} is equal to

\displaystyle  \frac{1}{2^n} \sum_{i=0}^{n} \binom {n}{i} \cdot F(i).

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

\displaystyle  F(k) + 2F(p+k) + F(2p+k) \equiv_p c,

for some constant {c} and {k \le n-2p}. Here {p} 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 {n^{0.525}} to {n^{0.5}} if a certain number theory conjecture is true. Note if one could prove that {n^{0.50001}} 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 {n}?

7 Comments leave one →
  1. January 5, 2011 11:52 pm

    Forgive me, but I have no idea why the Fourier structure of symmetric Boolean functions is of interest/consequence. If there’s a short answer, it would be very useful. Maybe some other readers are in the same boat.

    • P.A.S. permalink
      January 20, 2011 5:12 pm

      I think the answer is in the end of the article: proving some results about the Fourier structure of such functions helps (dis)proving results about numbers!

  2. Ali Sinop permalink
    January 6, 2011 1:28 am

    I wonder one thing, is there any relationship between the bounds for symmetric functions and invariance principle? Or is the influence notion too weak to be useful in this setting?

  3. Petter permalink
    January 6, 2011 7:13 am

    Both papers contain some background.

Trackbacks

  1. Tweets that mention Fourier Complexity of cirtemmyS Boolean Functions « Gödel’s Lost Letter and P=NP -- Topsy.com
  2. Fourier Transforms of Boolean Functions : 1 | Inquiry Into Inquiry
  3. Fourier Transforms of Boolean Functions : 2 | Inquiry Into Inquiry

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s