Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Sciences
A Study Of Sparse Representation Of Boolean Functions, Yekun Xu
A Study Of Sparse Representation Of Boolean Functions, Yekun Xu
FIU Electronic Theses and Dissertations
Boolean function is one of the most fundamental computation models in theoretical computer science. The two most common representations of Boolean functions are Fourier transform and real polynomial form. Applying analytic tools under these representations to the study Boolean functions has led to fruitful research in many areas such as complexity theory, learning theory, inapproximability, pseudorandomness, metric embedding, property testing, threshold phenomena, social choice, etc. In this thesis, we focus on \emph{sparse representations} of Boolean function in both Fourier transform and polynomial form, and obtain the following new results. A classical result of Rothschild and van Lint asserts that if …