清水伸高 Shimizu Nobutaka

研究者番号	10910127
その他のID
所属 (現在)	2025年度: 東京科学大学, 工学院, 助教
所属 (過去の研究課題情報に基づく) *注記	2021年度 – 2024年度: 東京工業大学, 工学院, 助教
審査区分/研究分野	研究代表者小区分60010:情報学基礎論関連 / 1001:情報科学、情報工学およびその関連分野研究代表者以外中区分60:情報科学、情報工学およびその関連分野
キーワード	研究代表者平均時計算量 / 計算量下界 / エクスパンダー / 埋め込みクリーク問題 / 困難性の増幅 / コミュニティ検出 / 分散アルゴリズム / 合意モデル / ランダムグラフ / 確率過程 … もっと見る研究代表者以外 … もっと見る平均時計算量 / 埋め込みクリーク予想 / メタ計算量 / 量子計算の基礎 / SAT問題 / 質問計算量 / 回路計算量 / 最小回路サイズ問題 / 情報セキュリティ技術 / 情報セキュリティ / 学習可能性 / Ｐ≠ＮＰ予想 / 機械学習 / PAC学習困難性 / 計算論的暗号 / 平均時計算困難性 / 多項式時間階層 / 最小記述量計算 / 一方向関数 / 学習計算困難さ / 平均時計算複雑度 / 最小記述量 / 計算論的暗号理論 / 計算論的学習理論 / 平均時時間計算量 / 最悪時時間計算量 / メタ計算 / P≠NP予想 / 最小記述量計算問題 / 計算複雑度理論隠す

メタ計算量に基づく平均時NP完全性理論の開拓
- 研究代表者
  
  平原秀一
- 研究期間 (年度)
  2024 – 2029
- 研究種目
  
  挑戦的研究(開拓)
- 審査区分
  
  中区分60:情報科学、情報工学およびその関連分野
- 研究機関
  国立情報学研究所
エクスパンダーに基づく計算量下界の枠組み研究代表者
- 研究代表者
  
  清水伸高
- 研究期間 (年度)
  2023 – 2027
- 研究種目
  
  若手研究
- 審査区分
  
  小区分60010:情報学基礎論関連
- 研究機関
  東京工業大学
合意モデルに基づく分散コミュニティ検出アルゴリズムの開発と理論的解析研究代表者
- 研究代表者
  
  清水伸高
- 研究期間 (年度)
  2021 – 2022
- 研究種目
  
  研究活動スタート支援
- 審査区分
  
  1001:情報科学、情報工学およびその関連分野
- 研究機関
  東京工業大学
最小記述量の計算困難さの解析
- 研究代表者
  
  渡辺治
- 研究期間 (年度)
  2018 – 2021
- 研究種目
  
  基盤研究(A)
- 審査区分
  
  中区分60:情報科学、情報工学およびその関連分野
- 研究機関
  東京工業大学

すべて 2023 2022 2021 2019

すべて雑誌論文学会発表

[雑誌論文] Hardness Self-Amplification: Simplified, Optimized, and Unified2023
- 著者名/発表者名
  Hirahara Shuichi、Shimizu Nobutaka
- 雑誌名
  
  Symposium on Theory of Computing
  
  巻: 1 ページ: 70-83
- DOI
  10.1145/3564246.3585189
- 査読あり / オープンアクセス / 国際共著/国際学会である
- データソース
  KAKENHI-PROJECT-23K16837, KAKENHI-PROJECT-20H04139
[雑誌論文] Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH2021
- 著者名/発表者名
  Hirahara Shuichi、Shimizu Nobutaka
- 雑誌名
  
  Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms
  
  巻: SODA21 ページ: 2346-2365
- DOI
  10.1137/1.9781611976465.140
- ISBN
  9781611976465
- 査読あり
- データソース
  KAKENHI-PROJECT-18H04090
[雑誌論文] How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?2021
- 著者名/発表者名
  Kijima Shuji、Shimizu Nobutaka、Shiraga Takeharu
- 雑誌名
  
  Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
  
  巻: 1 ページ: 106-122
- DOI
  10.1137/1.9781611976465.8
- ISBN
  9781611976465
- 査読あり
- データソース
  KAKENHI-PROJECT-19K20214, KAKENHI-PROJECT-17K19982, KAKENHI-PROJECT-18H04090
[学会発表] 理論計算機科学における高次元エクスパンダーとその応用2023
- 著者名/発表者名
  清水伸高
- 学会等名
  エクスパンダーグラフの新しい構成手法の確立とその応用2
- 招待講演
- データソース
  KAKENHI-PROJECT-23K16837
[学会発表] 左右ケイリー複体に基づく局所検査符号2023
- 著者名/発表者名
  清水伸高
- 学会等名
  第19回組合せ論若手研究集会
- 招待講演
- データソース
  KAKENHI-PROJECT-23K16837
[学会発表] Hardness Self-Amplification: Simplified, Optimized, and Unified2023
- 著者名/発表者名
  清水伸高
- 学会等名
  Online Complexity Seminar
- 招待講演
- データソース
  KAKENHI-PROJECT-23K16837
[学会発表] Hardness Self-Amplification: Simplified, Optimized, and Unified2023
- 著者名/発表者名
  Nobutaka Shimizu
- 学会等名
  ACM Symposium on Theory of Computing
- 国際共著/国際学会である
- データソース
  KAKENHI-PROJECT-21K21282
[学会発表] エクスパンダー性と符号の局所検査性2023
- 著者名/発表者名
  清水伸高
- 学会等名
  夏のLAシンポジウム
- データソース
  KAKENHI-PROJECT-23K16837
[学会発表] Hardness Self-Amplification from Feasible Hard-Core Sets2022
- 著者名/発表者名
  Nobutaka Shimizu
- 学会等名
  IEEE Symposium on Foundations of Computer Science
- 国際共著/国際学会である
- データソース
  KAKENHI-PROJECT-21K21282
[学会発表] グラフ彩色問題の指数時間量子アルゴリズム2019
- 著者名/発表者名
  清水一矢，森立平
- 学会等名
  量子情報技術研究会
- データソース
  KAKENHI-PROJECT-18H04090

1. 平原秀一 (80848440)

共同の研究課題数: 2件

共同の研究成果数: 1件
2. 渡辺治 (80158617)

共同の研究課題数: 1件

共同の研究成果数: 0件
3. 伊東利哉 (20184674)

共同の研究課題数: 1件

共同の研究成果数: 0件
4. 天野一幸 (30282031)

共同の研究課題数: 1件

共同の研究成果数: 0件
5. 玉置卓 (40432413)

共同の研究課題数: 1件

共同の研究成果数: 0件
6. 森立平 (60732857)

共同の研究課題数: 1件

共同の研究成果数: 1件
7. 七島幹人 (90855222)

共同の研究課題数: 1件

共同の研究成果数: 0件
8. 白髪丈晴

共同の研究課題数: 0件

共同の研究成果数: 1件

清水 伸高 Shimizu Nobutaka

研究課題

研究成果

共同研究者

メタ計算量に基づく平均時NP完全性理論の開拓

研究代表者

研究期間 (年度)

研究種目

審査区分

研究機関

エクスパンダーに基づく計算量下界の枠組み研究代表者

研究代表者

研究期間 (年度)

研究種目

審査区分

研究機関

合意モデルに基づく分散コミュニティ検出アルゴリズムの開発と理論的解析研究代表者

研究代表者

研究期間 (年度)

研究種目

審査区分

研究機関

最小記述量の計算困難さの解析

研究代表者

研究期間 (年度)

研究種目

審査区分

研究機関

[雑誌論文] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

著者名/発表者名

雑誌名

DOI

データソース

[雑誌論文] Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH2021

著者名/発表者名

雑誌名

DOI

ISBN

データソース

[雑誌論文] How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?2021

著者名/発表者名

雑誌名

DOI

ISBN

データソース

[学会発表] 理論計算機科学における高次元エクスパンダーとその応用2023

著者名/発表者名

学会等名

データソース

[学会発表] 左右ケイリー複体に基づく局所検査符号2023

著者名/発表者名

学会等名

データソース

[学会発表] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

著者名/発表者名

学会等名

データソース

[学会発表] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

著者名/発表者名

学会等名

データソース

[学会発表] エクスパンダー性と符号の局所検査性2023

著者名/発表者名

学会等名

データソース

[学会発表] Hardness Self-Amplification from Feasible Hard-Core Sets2022

著者名/発表者名

学会等名

データソース

[学会発表] グラフ彩色問題の指数時間量子アルゴリズム2019

著者名/発表者名

学会等名

データソース

清水伸高 Shimizu Nobutaka