69
$\begingroup$

Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including property testing, pseudorandomness, communication complexity, and quantum computing.

While I got comfortable using Fourier analysis of Boolean functions as a very useful tool when I'm tackling a problem, and even though I have a pretty good hunch for which cases using Fourier analysis would probably yield some nice results; I have to admit that I'm not really sure what it is that makes this change of basis so useful.

Does anyone has an intuition as to why Fourier analysis is so fruitful in the study of TCS? Why so many seemingly hard problems get solved by writing the Fourier expansion and performing some manipulations?

Note: my main intuition thus far, meagre as it may be, is that we have a pretty good understanding of how polynomials behave, and that the Fourier transform is a natural way of looking at a function as a multilinear polynomial. But why specifically this base? what is so unique in the base of parities?

Improve this question
$\endgroup$
2
  • 10
    $\begingroup$ Paging @ryan-odonnell $\endgroup$
    – Suresh Venkat
    Commented Sep 21, 2012 at 17:00
  • 4
    $\begingroup$ One idea which was floating around in the 90s is that maybe other basis of functions will also work, perhaps mimmicking the success of wavelets in classical harmonic analysis. But I did not see this idea being persued. $\endgroup$
    – Gil Kalai
    Commented Sep 25, 2012 at 0:33

3 Answers 3

Reset to default
74
$\begingroup$

Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions of TCS, there is an underlying need to analyze the effects that such operators have on certain functions.

Now, the point is that the Fourier basis is the basis that diagonalizes all those operators at the same time, which makes the analysis of those operators much simpler. More generally, the Fourier basis diagonalizes the convolution operator, which also underlies many of those questions. Thus, Fourier analysis is likely to be effective whenever one needs to analyze those operators.

By the way, Fourier analysis is just a special case of the representation theory of finite groups. This theory considers the more general space of functions $f:G\to \mathbb{C}$ where $G$ is a finite group, and operators of the form $\sigma_h$ (for $h\in G$) that map $f(x)$ to $f(x\cdot h)$, The theory then allows you to find a basis that makes the analysis of such operators easier - even though for general groups you don't get to actually diagonalize the operators.

Improve this answer
$\endgroup$
7
  • 7
    $\begingroup$ this is an excellent answer. $\endgroup$
    – Suresh Venkat
    Commented Sep 21, 2012 at 16:58
  • 3
    $\begingroup$ Nice way to put it. Continuing in the same vein, if you want to look at tuples $(f(x), f(x+w_1), f(x+w_2), f(x+w_1+w_2))$, then standard Fourier analysis is often no longer enough, and it can be helpful to move to higher-order Fourier analysis. $\endgroup$
    – arnab
    Commented Sep 21, 2012 at 20:50
  • 5
    $\begingroup$ What do you mean by "diagonalizing an operator"? $\endgroup$
    – Josephine Moeller
    Commented Sep 22, 2012 at 0:42
  • 12
    $\begingroup$ John - If you view the functions $f$ as vectors in a subspace, then the operator is a linear operation on vectors, and can be viewed as a matrix. Diagonalizing this operator means diagonalizing the matrix. $\endgroup$
    – Or Meir
    Commented Sep 22, 2012 at 3:05
  • 1
    $\begingroup$ it's interesting that even applications to learning juntas can be understood in terms of convolution operators: a junta is equal to its image under the operator that averages over inputs that disagree on irrelevant coordinates. this operator is a convolution operator, and is sparse in the fourier domain. this is a general theme: when a function is "correlated with itself" it begs for a fourier based approach $\endgroup$
    – Sasho Nikolov
    Commented Sep 22, 2012 at 3:45
8
$\begingroup$

Here might be another take on this question.

Assuming the pseudo Boolean function is k-bounded, the Walsh polynomial representation of the function can be decomposed into k subfunctions. All of the linear terms are collected into one subfunction, the all of the pairwise interactions into one subfunction, then the 3-way interactions, etc.

Each one of these subfunctions is an "elementary landscape" and thus each of the subfunctions is an eigenvector of the Laplacian adjacency matrix (i.e., the Hamming distance 1 neighborhood). Each subfunction has a corresponding "Wave Equation" of the type found in all elementary landscapes. Except now there are k Wave Equations that act in combination.

Knowing the wave equations makes it possible to statistically characterize the corresponding search space in rather precise ways. You can compute mean and variance and skew over arbitrary (exponentially large) Hamming balls and over arbitrary hyperplanes of the search space.

See Peter Stadler's work on Elementary Landscapes.

Andrew Sutton and I (Darrell Whitley) have worked on using these methods to understand and improve local search algorithms for pseudo-Boolean optimization. You can use the Walsh polynomials to automatically identify improving moves for local search algorithms. There is never any need to randomly enumerate neighborhoods of the search space. The Walsh analysis can directly tell you where the improving moves are located.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Could you provide some pointers to the work you cite? $\endgroup$
    – András Salamon
    Commented Oct 22, 2015 at 17:16
4
$\begingroup$

a great answer to this question probably does not yet exist because its a relatively young and very active area of research. for example Ingo Wegeners comprehensive book on boolean functions from 1987 has nothing on the subject (except for analyzing the circuit complexity of the DFT).

a simple intuition or conjecture is that it appears that large Fourier coefficients of higher order indicate the presence of subfunctions that must take into account many input variables and therefore require many gates. ie the Fourier expansion is apparently a natural way to quantitatively measure the hardness of a boolean function. have not seen this directly proven but think its hinted in many results. eg Khrapchenkos lower bound can be related to Fourier coefficients.[1]

another rough analogy can be borrowed from EE or other engineering fields to some degree where Fourier analysis is used extensively. it is often used for EE filters/signal processing. the Fourier coefficients represent a particular "band" of the filter. the story there is also that "noise" seems to manifest in particular ranges of frequencies, eg low or high. in CS an analogy to "noise" is "randomness" but also its clear from much research (reaching a milestone in eg [4]) that randomness is basically the same as complexity. (in some cases "entropy" also shows up in the same context.) Fourier analysis seems to be suited to study "noise" even in CS settings.[2]

another intuition or picture comes from voting/choice theory.[2,3] it is helpful to analyze boolean functions as having subcomponents that "vote" and influence the outcome. ie analysis of voting is a sort of decomposition system for functions. this also leverages some voting theory which reached heights of mathematical analysis and which apparently predates the use of much Fourier analysis of boolean functions.

also, the concept of symmetry appears to be paramount in Fourier analysis. the more "symmetric" the function, the more that Fourier coefficient cancel out, and also the more "simple" the function is to compute. but also the more "random" and therefore more complex the function, the less the coefficients cancel out. in other words symmetry and simplicity, and conversely asymmetry and complexity in the function seem to be coordinated in a way that Fourier analysis can measure.

[1] On the Fourier analysis of boolean functions by Bernasconi, Codenotti, Simon

[2] A brief introduction to Fourier analysis on the Boolean cube (2008) by De Wolf

[3] Some topics on the analysis of boolean functions by O'Donnell

[4] Natural proofs by Razborov & Rudich

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ see also online book Analysis of boolean functions by O'Donnell $\endgroup$
    – vzn
    Commented Sep 22, 2012 at 18:55
  • 1
    $\begingroup$ re the conjecture about complexity of the boolean fn reflected in the "power spectrum" over Fourier coefficients— a natural extension of the famous results in the Linial Mansour Nisan paper, Constant depth circuits, Fourier transform & learnability. abstract: "the main result is that an AC^0 boolean fn has most of its 'power spectrum' on the low-order coefficients" $\endgroup$
    – vzn
    Commented Sep 25, 2012 at 20:39
  • 2
    $\begingroup$ there is a nice survey of fourier analysis in ch2 of juknas book, boolean function complexity, advances & frontiers, which points out the fourier coefficients correlate to parity functions computed over subsets of input variables. $\endgroup$
    – vzn
    Commented Oct 14, 2012 at 16:22
  • 2
    $\begingroup$ Why is this answer so heavily downvoted? $\endgroup$
    – user834
    Commented Feb 25, 2014 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.