boolean-analysis   29

soft question - Why does Fourier analysis of Boolean functions "work"? - Theoretical Computer Science Stack Exchange
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 -> R and consider a linear operator of the form σ_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.
q-n-a  math  tcs  synthesis  boolean-analysis  fourier  👳  tidbits  motivation  intuition  linear-algebra  overflow  hi-order-bits  insight  curiosity  ground-up  arrows  nibble  s:*  elegance 
december 2016 by nhaliday

related tags

2016-election  aaronson  accretion  acm  advanced  advice  algebra  algorithms  approximation  arrows  bare-hands  boaz-barak  bonferroni  books  calculation  certificates-recognition  cmu  coding-theory  coloring  complexity  concentration-of-measure  concept  conceptual-vocab  conference  convexity-curvature  cool  counting  course  critique  crypto  curiosity  current-events  curvature  dependence-independence  dimensionality  discrete  discussion  elections  elegance  encyclopedic  entropy-like  estimate  expanders  expectancy  expert-experience  expert  explanation  exposition  fields  focs  fourier  geometry  gowers  graph-theory  graphs  ground-up  hamming  hi-order-bits  hierarchy  high-dimension  homepage  iidness  information-theory  insight  interdisciplinary  intersection-connectedness  intersection  intuition  ising  israel  knowledge  lattice  learning-theory  lecture-notes  lectures  lens  levers  limits  linear-algebra  liner-notes  links  list  lower-bounds  luca-trevisan  magnitude  markov  math.fa  math.nt  math.rt  math  mathtariat  measure  metabuch  metric-space  mit  motivation  nibble  ocw  oly  online-learning  open-problems  optimization  org:bleg  org:mat  overflow  p:**  p:*  p:someday  p:whenever  papers  pcp  pdf  people  percolation  phase-transition  physics  politics  polynomials  preprint  princeton  probabilistic-method  probability  problem-solving  prof  proof-systems  proofs  pseudorandomness  q-n-a  quantum-info  quantum  questions  quixotic  rand-approx  rand-complexity  random-matrices  random-networks  random  reading  rec-math  recommendations  reduction  reference  reflection  relativization  research  rigorous-crypto  rounding  ryan-odonnell  s:*  sampling  sdp  sensitivity  similarity  slides  social-choice  soft-question  space-complexity  stat-mech  stoc  sum-of-squares  summary  survey  synthesis  talks  tcs  tcstariat  thesis  thinking  tidbits  todo  topics  topology  ugc  unit  washington  wigderson  wiki  yoga  👳  🔬 

Copy this bookmark: