First Advisor

John S. Caughman

Date of Award

Spring 6-2026

Document Type

Thesis

Degree Name

Bachelor of Science (B.S.) in Mathematics and University Honors

Department

Mathematics and Statistics

Language

English

Subjects

sensitivity graph, boolean function, hypercube, spectral sensitivity, polynomial degree, maximum sensitivity

DOI

10.15760/honors.1832

Abstract

This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal.

The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.

Persistent Identifier

https://archives.pdx.edu/ds/psu/44765

Download

Share

COinS