SMART: Next 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 armonic 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.
 

[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