Mathematical sciences and applications of expander graphs
Reference No. | 2025a037 |
---|---|
Type/Category | Grant for Young Researchers and Students-Short-term Joint Research |
Title of Research Project | Mathematical sciences and applications of expander graphs |
Principal Investigator | Shohei Satake(Kumamoto University・Associate Professor) |
Research Period |
August 25,2025. -
August 29,2025. |
Keyword(s) of Research Fields | Expander Graphs, Information Science, Mathematical Science, Industry-Academia Research |
Abstract for Research Report |
Expander graphs are unique structures that balance sparse connectivity with high local connectivity, enabling efficient information transmission and rapid mixing. These properties make them crucial in fields like post-quantum cryptography, quantum error correction codes, and other areas of information science. Companies such as Google are actively researching expander graphs, recognizing their potential applications in cryptography, machine learning, and broader industrial sectors. Consequently, expander graphs play a vital role in advancing modern information science. The study of expander graphs revolves around two major challenges: (1) Developing and Refining Construction Methods Algebraic constructions offer explicitness but involve complex mathematical problems from group theory and number theory, making it difficult to analyze their structural properties. Combinatorial and algorithmic methods provide alternative approaches but often sacrifice transparency and control over properties. A hybrid approach integrating both methods is needed to balance explicitness, efficiency, and structural clarity. (2) Expanding and Understanding Applications Expander graphs play a critical role in cryptography, coding theory, and machine learning, where their second-largest eigenvalue heavily influences their usability. They have potential applications in cryptographic hash functions, quantum LDPC codes, and graph neural networks, but these remain underexplored. Industry-academia collaboration, especially in Japan, is still limited, necessitating stronger research frameworks and industrial partnerships. This study aims to: 1. Develop Hybrid Construction Methods By integrating algebraic and combinatorial techniques, we propose new construction approaches that optimize expander graph properties, facilitating efficient structural analysis. 2. Expand Application Potential in Academia and Industry We seek to advance applications in cryptographic technologies and machine learning while fostering collaborations with domestic and international industries. Joint research with companies and demonstration of practical use cases will drive real-world implementation. |
Organizing Committee Members (Workshop) Participants (Short-term Joint Usage) |
Yusuke Aikawa(University of Tokyo・Assistant professor) Yasuhiko Ikematsu(Kyushu University・Associate Professor) Cid Reyes Bustos(NTT Institute for Fundamental Mathematics・Research Scientist) Nobutaka Shimizu(Institute of Science Tokyo・Assistant Professor) Hyungrok Jo(Yokohama National University・Assistant Professor) Masato Mimura(Tohoku University・Associate Professor) Shohei Satake(Kumamoto University・Associate Professor) |