Skip navigation
Please use this identifier to cite or link to this item:
Title: Techniques for Analysis of Boolean Functions
Authors: Reeves, Thomas Rowan
Advisors: Marcus, Adam
Contributors: Naor, Asaf
Department: Mathematics
Class Year: 2016
Abstract: We discuss techniques for Fourier analysis of Boolean functions. After an introduction to Boolean functions and their Fourier expansions, we discuss perhaps the simplest complexity measures of Boolean functions { sensitivity and influence. We turn to the question of nding restrictions on the Fourier coe cients of a Boolean function and derive an identity. Finally, we discuss the entropy-influence conjecture with a focus on useful generalizations of the problem, including generalizations of entropy and probability distribution. We propose a generalization of the Fourier basis using rotation matrices and derive an analogue of the Margulis-Russo Formula.
Extent: 26 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File SizeFormat 
REEVES_Thomas_thesis.pdf277.74 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.