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

• Kalampalikis, Nikolaos

Mitwirkende

• Keane, Patrick Gerard

Degree

• MS

Unit

• Mathematical Sciences

Publisher

• Worcester Polytechnic Institute

Identifier

• etd-50941

Advisor

• Keane, Patrick Gerard

Defense date

• 2022-03-14

Year

• 2022

Date created

• 2022-03-14

Resource type

• Thesis

Rights statement

• In Copyright