We are honored to announce that Professor Craig Gotsman from the New Jersey Institute of Technology has officially joined NAAI. His main research areas include computational geometry, computer graphics, and digital geometry processing. Professor Craig Gotsman is a renowned scholar in the field of theoretical computer science, particularly known for his research on measuring the complexity of Boolean functions. He and Nati Linial jointly proposed the Boolean Sensitivity Conjecture in 1992, which has long been regarded as one of the core open problems in combinatorics and theoretical computer science. Its solution is of great significance for understanding computational complexity.
Core Contributions and Academic Background
1.The proposal of the sensitivity conjecture by Gotsman and Linial aims to explore the mathematical relationship between the "sensitivity" of Boolean functions and other complexity measures such as block sensitivity and decision tree complexity. This conjecture proposes that the sensitivity of Boolean functions can also be incorporated into a unified framework for complexity measurement, thereby deepening the understanding of computational infrastructure. This conjecture has attracted much attention due to its theoretical depth and practical value, such as circuit design optimization, but has not been proven for nearly 30 years, and has been referred to as "one of the most frustrating open problems" by scholar Scott Aaronson.
2. The significance and sensitivity of conjecture involve the connectivity properties of midpoints in hypercubes, and its proof will directly affect fields such as computational theory and algorithm design. In 2019, mathematician Huang Hao proved the conjecture in a concise way by introducing Cauchy's interleaving theorem and matrix symbol transformation. The related paper was published in the Annals of Mathematics. Gotsman's work laid a crucial foundation for this breakthrough.
Research Direction and Academic Collaboration - Research Field: Gotsman's research focuses on combinatorial mathematics, theoretical computer science, particularly Boolean function analysis, high-dimensional geometry, and computational complexity theory.
-Collaborative Network: Long term collaboration with Nati Linial from Hebrew University to jointly promote the construction of a theoretical framework for complexity measurement.
Academic Status and Evaluation
His contribution to the sensitivity conjecture has established his position in the field of theoretical computer science. After the conjecture was solved, Huang Hao's research further verified the profound significance of Gotsman and Linial's original problems, and the related achievements were selected as one of the top ten mathematical breakthroughs in Popular Mechanics in 2019.
About NAAI
The National Academy of Artificial Intelligence (NAAI) is an institution dedicated to promoting the development of the field of artificial intelligence, strengthening academic exchanges and cooperation, and enhancing public understanding and cognition of artificial intelligence. The Academy of Sciences brings together numerous scientists and engineers who have made outstanding achievements in the field of artificial intelligence, aiming to promote innovation and application of artificial intelligence technology through various means such as research, education, policy recommendations, and public services.