Recently, data sets have become so large that even the time for reading the whole dataset is prohibitive. In order to tackle this challenge, the subfield of sublinear time algorithms has been developed. In practice, it often happens that the data can be represented as an input-output relation of a function. Fourier analysis of Boolean functions is an important tool for characterizing various properties of functions. In this project we plan to investigate sublinear time algorithms that allow us to estimate some of these Fourier properties.

Having taken a class with Professor Rubinfeld that covered Fourier analysis of Boolean functions, I am very excited for this chance to apply my knowledge and gain research experience. This project will give me an opportunity to develop my skills in research and, perhaps, to contribute to human knowledge.