Stefankovic/M.S. Presentation/Nov. 6, 2000

[Margaret Jaffey]

This is an announcement of Daniel Stefankovic's Master's Presentation.

Date:    Monday, November 6, 2000

Time:   3:45

Place:  Ryerson 277

M.S. Candidate:  Daniel Stefankovic

M.S. Paper Title:  Fourier Transforms in Computer Science

Abstract:

We survey proofs of five Theorems which have applications
in the Theory of Computing. The common theme of the proofs
is the use of various variants of harmonic analysis.
The proofs of following theorems are included:

 * Theorem of Linial, Mansour and Nisan on the
   concentration of the Fourier coefficients of $AC^0$
   functions (harmonic analysis over the finite
   group $\intg_2^n$)

 * Theorem of Kahn, Kalai and Linial on the influence of
   variables on Boolean functions (harmonic analysis
   over the finite group $\intg_2^n$)

 * The analysis of Margulis' expander graph by Gabber and
   Galil  (harmonic analysis over the compact group $\tor{2}$)

 * Transference Theorem of Banaszczyk \cite{M5} (harmonic
   analysis over the locally compact group $\real^n$)

 * Theorem of Th\'erien on the column sums in matrices (mod $m$)
   (generalized harmonic analysis over the finite group $\intg_{p-1}^n$
   with respect to the finite field $\fie_p$)

Mr. Stefankovic's Advisor:  Prof. Laszlo Babai

A draft copy of Mr. Stefankovic's M.S. paper will be available for review
within the next day or two in Ry 161A.

Margaret
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey			margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=