Reciprocal research on graph asymmetry and expander graphs

图不对称性与扩展图的互逆研究

• 批准号: 20J00469
• 负责人: 佐竹 翔平
• 金额: $ 2.58万
• 依托单位: Kumamoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-24 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20J00469/
• 关键词: エクスパンダーグラフ; 拡大定数; 弧推移的グラフ; 内周; ハッシュ関数; エクスパンダ―グラフ; RIP行列; Paleyグラフ予想; 漸近最良性定理

前年度には, Ganguly-Srivastava (2019)によって示された内周の上界式を漸近的に達成する正則なエクスパンダーグラフをほとんどすべての次数に対して明示的に構成することに成功していた. その成果をまとめた論文が,国際一般誌Journal of the Ramanujan Mathematical Societyに本年度に採択された.次に, Ramanujanグラフの構成問題と暗号理論の専門家であるHyungrok Jo氏 (横浜国立大学, IAS 特任助教)と共同で, 弧推移的グラフのエクスパンダーとしての性質に着目し, グラフ上のウォークとして定義される新しい暗号学的ハッシュ関数を提案した. そのハッシュ関数としての性質は, グラフの内周や拡大定数に影響するため, 一般的に調べることが難しいエクスパンダーとしての性質を調べる上で重要となることがわかった. 特に, 弧推移的グラフであり内周の高いtripletグラフに着目し, その非2部性を証明したが, これによって, スペクトラルグラフ理論の結果とランダムウォークの混合性の議論を合わせることで, tripletグラフの拡大定数の評価が可能になると期待される. また, 小さな直径を持つというエクスパンダーとしての典型的な性質も観察できた. (2022年度のその後の研究で, 特定の頂点数の系列に対して, tripletグラフがエクスパンダーとなることも証明することができた.) 一方で, 内周の高さが予想されるsextetグラフにも着目し, 計算機実験をもとに内周の評価を継続中である. 以上の一部成果をまとめた論文は, 暗号理論の国内シンポジウムSCIS2022の論文集に掲載されている.

In the previous year, Ganguly-Srivastava (2019) showed that the upper bound of the inner circle was gradually achieved. This year's edition of the International Journal of the Ramanujan Mathematical Society. In addition, Ramanujan Hyungrok Jo (Assistant Professor, IAS, Yokohama National University) proposed a new method for defining the structure of the class and the number of code relations in the class. The nature of the relationship between the number and the relationship between the number and the In particular, the arc transition of the triplets in the inner circle of the triplets is not two-dimensional, and the results of the triplets theory are expected to be possible. The diameter of the small diameter is small, and the typical property of the small diameter is small. (2022 After the study of the year, the number of specific vertices in the series is determined. On the one hand, the inner circumference is high enough to be thought of as sextet, and on the other hand, the computer is capable of evaluating the inner circumference. The above results are published in the Proceedings of SCIS2022.

项目成果

大きな内周とlocalizedな固有ベクトルをもつnear-Ramanujan graphの明示的構成に関して

关于具有大内周和局部特征向量的近拉马努金图的显式构造

• 发表时间: 2021
• 作者: 佐竹 翔平

Localized な固有ベクトルをもつ内周の大きな正則エクスパンダーグラフ

具有局部特征向量的大型内部全纯扩展图

• 发表时间: 2021
• 作者: Kagawa Kotaro;Takimoto Gaku;Seehausen Ole;Sefan Asamitsu;Miyu Suzuki;佐竹 翔平
• 通讯作者: 佐竹 翔平

On the restricted isometry property of the Paley matrix and related results

关于Paley矩阵的受限等距性质及相关结果

• 发表时间: 2020
• 作者: Arakawa Sota;Krijt Sebastiaan;Shohei Satake
• 通讯作者: Shohei Satake

On non-bipartiteness of triplet graphs and its application to cryptographic hash functions

三元组图的非二分性及其在密码哈希函数中的应用

• 发表时间: 2022
• 作者: 佐竹 翔平; Hyungrok Jo
• 通讯作者: Hyungrok Jo

Erdo"s-Falconer 距離問題と制限等長性

Erdo"s-Falconer 距离问题和受限等距性

• 发表时间: 2021
• 作者: 藏滿司夢;戒能洋一;今野浩太郎;佐竹 翔平
• 通讯作者: 佐竹 翔平