Colloquium| Institute of Mathematical Sciences
Time：11:00-12:00, December 23, Monday
Location：Room S408, IMS
Speaker: Lei Yu, National University of Singapore
Abstract: Ahlswede and Katona (1977) posed the following isodiametric problem for the discrete hypercube: For every n and 1≤M≤2^n, determine the minimum average Hamming distance of subsets of {0,1}^n with size M. Fu, Wei, and Yeung (2001) used Fourier analysis, combined with linear programming duality, to derive a lower bound on the minimum average distance. However, this Fourier analysis technique was not completely exploited by them. In this work, we characterize the (asymptotically) optimal bound that can be derived by this proof technique. Furthermore, noting that the average distance of a subset of the hypercube is closely related to weights of Fourier coefficients of a Boolean function, we also apply the Fourier analysis technique to bound Fourier weights of a Boolean function of various degrees. This is a joint work with Vincent Y. F. Tan.