SMART: Today's talk by Massimo Lauria [Harmonic analysis in Theoretical Computer Science]

[Giorgio Zanin]

Title           : Harmonic analysis in Theoretical Computer Science

 

Speaker         : Massimo Lauria

 

Date            : Monday, June 26, 2006

 

Venue & Time    : Aula Alfa, 113 Via Salaria. 3:00 PM

 

Abstract        : Harmonic analysis is a fundamental tool in a broad range

                  of scientific areas. It has been discovered/built by a

                  physicist but it is also used by number theorists. The

                  Harmonic analysis of a function is based on the decomposition

                  a mathematical object in a family of simpler objects, which

                  don't interfere one against the other.

 

                  In computer science harmonic analysis has been used mostly for

                  elaboration, approximation and compression of signals.

                  Nevertheless theoretical computer science has developed a wide

                  range of analytic tools for dealing with general boolean function.

                  Indeed, Harmonic analysis is one of the most important.

 

                  In the lecture we will give an brief review of classical Fourier

                  theory on the class of periodic functions which "behave well". In

                  this setting it is easy to exploit the right intuition from the

                  formal definitions. Then we will generalize the definition to cope

                  with cyclic groups, product groups, and hypercubes, trying to keep

                  in touch with the intuition developed in the classical setting.

 

                  We will introduce the theory of variable's influence in multivariate

                  functions, and will use it to prove that any fucntion has at least a

                  big-influence variable (the KKL theorem).  With this theorem and

                  with some other tools we will see a general results about threshold

                  phenomena in symmetric properties of a random graph.

 

 

http://www.dsi.uniroma1.it/smart/

 

Please feel free to extend this invitation to other interested people.