Shimizu Nobutaka 清水伸高

Researcher Number	10910127
Other IDs
Affiliation (Current)	2025: 東京科学大学, 工学院, 助教
Affiliation (based on the past Project Information) *help	2021 – 2024: 東京工業大学, 工学院, 助教
Review Section/Research Field	Principal Investigator Basic Section 60010:Theory of informatics-related / 1001:Information science, computer engineering, and related fields Except Principal Investigator Medium-sized Section 60:Information science, computer engineering, and related fields
Keywords	Principal Investigator 平均時計算量 / 計算量下界 / エクスパンダー / 埋め込みクリーク問題 / 困難性の増幅 / コミュニティ検出 / 分散アルゴリズム / 合意モデル / ランダムグラフ / 確率過程 … More Except Principal Investigator … More 平均時計算量 / 埋め込みクリーク予想 / メタ計算量 / 量子計算の基礎 / SAT問題 / 質問計算量 / 回路計算量 / 最小回路サイズ問題 / 情報セキュリティ技術 / 情報セキュリティ / 学習可能性 / Ｐ≠ＮＰ予想 / 機械学習 / PAC学習困難性 / 計算論的暗号 / 平均時計算困難性 / 多項式時間階層 / 最小記述量計算 / 一方向関数 / 学習計算困難さ / 平均時計算複雑度 / 最小記述量 / 計算論的暗号理論 / 計算論的学習理論 / 平均時時間計算量 / 最悪時時間計算量 / メタ計算 / P≠NP予想 / 最小記述量計算問題 / 計算複雑度理論 Less

メタ計算量に基づく平均時NP完全性理論の開拓
- Principal Investigator
  
  平原秀一
- Project Period (FY)
  2024 – 2029
- Research Category
  
  Grant-in-Aid for Challenging Research (Pioneering)
- Review Section
  
  Medium-sized Section 60:Information science, computer engineering, and related fields
- Research Institution
  National Institute of Informatics
Complexity Lower Bounds from ExpansionPrincipal Investigator
- Principal Investigator
  
  清水伸高
- Project Period (FY)
  2023 – 2027
- Research Category
  
  Grant-in-Aid for Early-Career Scientists
- Review Section
  
  Basic Section 60010:Theory of informatics-related
- Research Institution
  Tokyo Institute of Technology
Community Detection Algorithm from Voting ProcessPrincipal Investigator
- Principal Investigator
  
  Shimizu Nobutaka
- Project Period (FY)
  2021 – 2022
- Research Category
  
  Grant-in-Aid for Research Activity Start-up
- Review Section
  
  1001:Information science, computer engineering, and related fields
- Research Institution
  Tokyo Institute of Technology
Computational Complexity of Minimum Description Size Problems
- Principal Investigator
  
  Watanabe Osamu
- Project Period (FY)
  2018 – 2021
- Research Category
  
  Grant-in-Aid for Scientific Research (A)
- Review Section
  
  Medium-sized Section 60:Information science, computer engineering, and related fields
- Research Institution
  Tokyo Institute of Technology

All 2023 2022 2021 2019

All Journal Article Presentation

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

1. 平原秀一 (80848440)

# of Collaborated Projects: 2 results

# of Collaborated Products: 1 results
2. Watanabe Osamu (80158617)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
3. 伊東利哉 (20184674)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
4. 天野一幸 (30282031)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
5. 玉置卓 (40432413)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
6. 森立平 (60732857)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
7. 七島幹人 (90855222)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
8. 白髪丈晴

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results

Shimizu Nobutaka 清水 伸高

Research Projects

Research Products

Co-Researchers

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

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Complexity Lower Bounds from ExpansionPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Community Detection Algorithm from Voting ProcessPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Computational Complexity of Minimum Description Size Problems

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

[Journal Article] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH2021

Author(s)

Journal Title

DOI

ISBN

Data Source

[Journal Article] How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?2021

Author(s)

Journal Title

DOI

ISBN

Data Source

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

Author(s)

Organizer

Data Source

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

Author(s)

Organizer

Data Source

[Presentation] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

Author(s)

Organizer

Data Source

[Presentation] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

Author(s)

Organizer

Data Source

[Presentation] エクスパンダー性と符号の局所検査性2023

Author(s)

Organizer

Data Source

[Presentation] Hardness Self-Amplification from Feasible Hard-Core Sets2022

Author(s)

Organizer

Data Source

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

Author(s)

Organizer

Data Source

Shimizu Nobutaka 清水伸高