Weighing Matrices and Huang’s graph theoretic proof of the Sensitivity Conjecture

Kalampalikis, Nikolaos

Etd

Weighing Matrices and Huang’s graph theoretic proof of the Sensitivity Conjecture

Público

In 2018, Huang gave a surprising short and algebraic proof of the Sensitivity Conjecture which had been an important problem in theoretical computer science for over 30 years. Though Huang does not mention weighing matrices in his proof, his key construction follows quite easily from techniques in this subject. This thesis gives an exposition of the theory of weighing matrices, including the main result of the subject, Seberry’s Asymptotic Existence of Hadamard Matrices. An introduction to algebraic graph theory, focusing particularly on induced subgraphs of cube graphs and the Chung-Furedi-Graham-Seymour construction of quasi-random graphs gives required background for Huang’s proof. Finally, background results on the sensitivity conjecture and Huang’s result complete the thesis.

Creator