• Search Research Projects
  • Search Researchers
  • How to Use
  1. Back to previous page

NAGAO Atsuki  長尾 篤樹

ORCIDConnect your ORCID iD *help
Researcher Number 20802622
Other IDs
Affiliation (Current) 2025: お茶の水女子大学, 基幹研究院, 准教授
Affiliation (based on the past Project Information) *help 2022 – 2024: お茶の水女子大学, 基幹研究院, 講師
2018 – 2021: お茶の水女子大学, 基幹研究院, 助教
Review Section/Research Field
Principal Investigator
Basic Section 60010:Theory of informatics-related
Except Principal Investigator
Basic Section 60010:Theory of informatics-related / Sections That Are Subject to Joint Review: Basic Section60010:Theory of informatics-related , Basic Section60020:Mathematical informatics-related / Basic Section 60020:Mathematical informatics-related
Keywords
Principal Investigator
計算量理論 / 計算量クラスの分離 / 分岐プログラム / 対数領域計算モデル / Read-k-time / Sub-SAT / 厳密アルゴリズム / アルゴリズム / 充足可能性問題 / 一回読み制限 / 木構造関数値評価問題 / 領域計算量 … More
Except Principal Investigator
… More 充足可能性問題 / パラメータ化アルゴリズム / 計算複雑性 / 組合せ最適化問題 / 解の唯一化 / SATアルゴリズム / 回路計算量 / 下界証明 / 二元体上の連立線形方程式 / 多数決関数 / 定数段数回路 / 解空間の連結性判定 / k-Horn式 / 3段回路 / Depth-3 Circuit / Branching Program / Bounded Width / Satisfiability / 計算量理論 / 指数時間仮説 / 幅限定 / 分岐プログラム / 置換分岐プログラム / 幅限定分岐プログラム / 充足可能性判定 / 厳密アルゴリズム / 強指数時間仮説 Less
  • Research Projects

    (5 results)
  • Research Products

    (3 results)
  • Co-Researchers

    (2 People)
  •  組合せ最適化問題に対する解の唯一化における計算複雑さの研究

    • Principal Investigator
      脊戸 和寿
    • Project Period (FY)
      2024 – 2027
    • Research Category
      Grant-in-Aid for Scientific Research (B)
    • Review Section
      Basic Section 60010:Theory of informatics-related
      Basic Section 60020:Mathematical informatics-related
      Sections That Are Subject to Joint Review: Basic Section60010:Theory of informatics-related , Basic Section60020:Mathematical informatics-related
    • Research Institution
      Hokkaido University
  •  Exploring the Function to Show the Limit of Log-space Computation ModelsPrincipal Investigator

    • Principal Investigator
      長尾 篤樹
    • Project Period (FY)
      2023 – 2026
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Review Section
      Basic Section 60010:Theory of informatics-related
    • Research Institution
      Ochanomizu University
  •  Research on Proof Techniques for Lower Bounds on Constant Depth Circuits

    • Principal Investigator
      Kazuhisa Seto
    • Project Period (FY)
      2021 – 2023
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Review Section
      Basic Section 60010:Theory of informatics-related
    • Research Institution
      Hokkaido University
  •  Comparison of Computational Limits Based on Memory Access Count in Logarithmic Space Computation ModelsPrincipal Investigator

    • Principal Investigator
      NAGAO Atsuki
    • Project Period (FY)
      2020 – 2023
    • Research Category
      Grant-in-Aid for Early-Career Scientists
    • Review Section
      Basic Section 60010:Theory of informatics-related
    • Research Institution
      Ochanomizu University
  •  Studies toward disproving the strong exponential time hypothesis

    • Principal Investigator
      Seto Kazuhisa
    • Project Period (FY)
      2018 – 2021
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Review Section
      Basic Section 60010:Theory of informatics-related
    • Research Institution
      Hokkaido University
      Seikei University

All 2022 2020

All Journal Article Presentation

  • [Journal Article] A Satisfiability Algorithm for Deterministic Width-2 Branching Programs2022

    • Author(s)
      Tomu MAKITA, Atsuki NAGAO, Tatsuki OKADA, Kazuhisa SETO, Junichi TERUYAMA
    • Journal Title

      IEICE Trans. Fundamentals

      Volume: E105.A Issue: 9 Pages: 1298-1308

    • DOI

      10.1587/transfun.2021EAP1120

    • ISSN
      0916-8508, 1745-1337
    • Year and Date
      2022-09-01
    • Language
      English
    • Peer Reviewed / Open Access
    • Data Source
      KAKENHI-PROJECT-18K11170, KAKENHI-PUBLICLY-21H05839, KAKENHI-PROJECT-21K11743, KAKENHI-PROJECT-20K19741, KAKENHI-PROJECT-22K11910, KAKENHI-PROJECT-18K18003, KAKENHI-PLANNED-20H05794
  • [Journal Article] Satisfiability Algorithm for Syntactic Read-k-times Branching Programs2020

    • Author(s)
      Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama
    • Journal Title

      Theory of Computing Systems

      Volume: 64 Issue: 8 Pages: 1392-1407

    • DOI

      10.1007/s00224-020-09996-3

    • Peer Reviewed / Open Access
    • Data Source
      KAKENHI-PROJECT-18K11170, KAKENHI-PROJECT-18K18003, KAKENHI-PROJECT-20K19741
  • [Presentation] A Moderately Exponential Time Satisfiability Algorithm for Linear-Sized Deterministic Width-2 Branching Programs2022

    • Author(s)
      Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, and Junichi Teruyama
    • Organizer
      電子情報通信学会コンピュテーション研究会
    • Data Source
      KAKENHI-PROJECT-21K11743
  • 1.  Seto Kazuhisa (20584056)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 2 results
  • 2.  小野 廣隆 (00346826)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results

URL: 

Are you sure that you want to link your ORCID iD to your KAKEN Researcher profile?
* This action can be performed only by the researcher himself/herself who is listed on the KAKEN Researcher’s page. Are you sure that this KAKEN Researcher’s page is your page?

この研究者とORCID iDの連携を行いますか?
※ この処理は、研究者本人だけが実行できます。

Information User Guide FAQ News Terms of Use Attribution of KAKENHI

Powered by NII kakenhi