Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
Paging @ryan-odonnell –  Suresh Venkat Sep 21 '12 at 17:00
3  
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. –  Gil Kalai Sep 25 '12 at 0:33

2 Answers 2

up vote 43 down vote accepted

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.

share|improve this answer
5  
this is an excellent answer. –  Suresh Venkat Sep 21 '12 at 16:58
1  
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. –  arnab Sep 21 '12 at 20:50
2  
What do you mean by "diagonalizing an operator"? –  John Moeller Sep 22 '12 at 0:42
6  
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. –  Or Meir Sep 22 '12 at 3:05
1  
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 –  Sasho Nikolov Sep 22 '12 at 3:45

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

share|improve this answer
3  
see also online book Analysis of boolean functions by O'Donnell –  vzn Sep 22 '12 at 18:55
    
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" –  vzn Sep 25 '12 at 20:39
2  
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. –  vzn Oct 14 '12 at 16:22
1  
Why is this answer so heavily downvoted? –  user834 Feb 25 at 20:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.