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 nk. 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 nk – 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.