Yekun Xu
Knight Foundation School of Computing and Information Sciences
Lecture Information:
- March 12, 2021
- 3:00 PM
- Zoom
Speaker Bio
Yekun Xu is a Ph.D. candidate at the Knight Foundation School of Computing and Information Sciences (KFSCIS). His research interests include randomized algorithms, polynomial methods, and function analysis. He is currently working under Dr. Ning Xie’s supervision, focusing on Fourier Analysis of Boolean functions.
Description
A classical result of Rothschild and van Lint asserts that if every non-zero Fourier coefficient of a Boolean function f over 
has the same absolute value, namely |f^(α)| = 1/2^k for every α in the Fourier support of f, then f must be the indicator function of some affine subspace of dimension n – k. In this paper, we slightly generalize their result and show that Boolean functions whose Fourier coefficients take values in the set {-2/2^k, -1/2^k, 0, 1/2^k, 2/2^k} are indicator functions of two disjoint affine subspaces of dimension n – k or four disjoint affine subspace of dimension n – k – 1. Our main technical tools are results from additive combinatorics which offer tight bounds on the affine span size of a subset of when the doubling constant of the subset is small.