Maseeh Summer Undergraduate Research Experience
Funding Source
Undergraduate Research and Mentoring Program (URMP)
Advisor
Shravas Rao
Document Type
Poster
Publication Date
2024
Abstract
This research explores the relationships between various complexity measures of Boolean functions—specifically Query Complexity, Sensitivity, Spectral Sensitivity, and Degree—modeled via hypercube sensitivity graphs and adjacency matrices. While the theoretical bounds for total functions are generalized, it remains unknown whether a function exists where these measures are perfectly equal. Focusing on the tight bounds demonstrated by the OR and PARITY functions, this work outlines a future research framework utilizing a contradiction proof style. By assuming and reverse-engineering established proofs, the study aims to uncover mathematical contradictions that could definitively determine the existence of such a total function.
Citation Details
Rupp, Annie, "Comparing the Sensitivity and Degree of Boolean Functions via the Hypercube" (2024). Maseeh Summer Undergraduate Research Experience. 67.