Weighing Matrices and Huang’s graph theoretic proof of the Sensitivity Conjecture
公开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
- 贡献者
- Degree
- Unit
- Publisher
- Identifier
- etd-50941
- Advisor
- Defense date
- Year
- 2022
- Date created
- 2022-03-14
- Resource type
- Rights statement
关系
- 属于 Collection:
项目
Permanent link to this page: https://digital.wpi.edu/show/sj1395239