Algorithmic Fourier Inversion
Speaker: Assaf Naor , Courant Inst of Math. Sciences, NYU
Date: May 8 2007
Time: 4:15PM to 5:30PM
Location: *NOTE: rm changed to 3-270 *
Host: Michel Goemans, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: http://theory.csail.mit.edu/theory-seminars/[Note unusual LOCATION: 3-270]
In this talk we will survey recent results on the following "meta-problem": Assume that we are given a function f on the discrete hypercube {-1,1}^n. Any such f can be decomposed into Fourier-Walsh coefficients, where each coefficient corresponds to a subset of {1,..,n}. But, assume that f actually has a succinct representation in phase space, i.e. only polynomially many of its Fourier coefficients are non-zero. Can we then compute (approximately) the maximum of f in polynomial time? This problem seems very difficult, and at present only a few partial results are known. Nevertheless, whenever non-trivial algorithms are discovered in this setting they have interesting applications to a wide range of problems in combinatorial optimization, including problems in graph partitioning, orientation, and clustering, and approximate solutions of over-determined systems of linear equations. Such problems also have deep connections with physics (computing ground states of spin glasses), mathematics (convex geometry, Grothedieck's inequality), and complexity theory.
See other events that are part of Theory Colloquium Spring 2007
See other events happening in May 2007
