Yamamoto Masaki 山本真基

… Alternative Names

MASAKI Yamamoto 山本真基

Less

Researcher Number	50432414
Other IDs
Affiliation (Current)	2025: 成蹊大学, 理工学部, 准教授
Affiliation (based on the past Project Information) *help	2012 – 2016: 成蹊大学, 理工学部, 准教授 2011: 関西学院大学, 理工学研究科, 専門技術員
Review Section/Research Field	Principal Investigator Fundamental theory of informatics Except Principal Investigator Science and Engineering
Keywords	Principal Investigator 混合時間 / 近似数え上げ / マルコフ連鎖モンテカルロ法 / サンプリングアルゴリズム Except Principal Investigator 最尤解探索問題 / 制約解探索問題 / 計算論的解析 / 統計力学的解析 / 充足可能性問題 / 伝搬系アルゴリズム … More / 平均時計算複雑さ / 解の一意化 / 充足解探索 / 劣線形領域計算 / 確率分布解析 / 強指数時間仮説 / 限定計算における計算限界 / 平均時計算量解析 / 情報理論的解析 / 解空間の構造解析 / 計算限界の確定 / 回路設計問題 / 解空間の離散体積計算問題 / ＳＯＳ法 / 平均時間計算量 / 制約式充足可能性問題 / 解の数え上げ問題 / 解空間の構造 / 計算困難さの相転移 / 計算困難さの解析 Less

Exploring the Limits of Computation from the Statistical Physics
- Principal Investigator
  
  Watanabe Osamu
- Project Period (FY)
  2012 – 2016
- Research Category
  
  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
- Review Section
  
  Science and Engineering
- Research Institution
  Tokyo Institute of Technology
Proposing new sapmling algorithmsPrincipal Investigator
- Principal Investigator
  
  MASAKI Yamamoto
- Project Period (FY)
  2011 – 2013
- Research Category
  
  Grant-in-Aid for Young Scientists (B)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  Seikei University
  Kwansei Gakuin University

All 2017 2013 2012 2011 Other

All Journal Article Presentation

[Journal Article] Approximately counting paths and cycles in a graph2017
- Author(s)
  M. Yamamoto
- Journal Title
  
  Discrete Applied Mathematics
  
  Volume: Volume 217, Part 2 Pages: 381-387
- DOI
  10.1016/j.dam.2016.09.002
- Peer Reviewed / Acknowledgement Compliant
- Data Source
  KAKENHI-PLANNED-24106008
[Journal Article] Message passing algorithms for MLS-3LIN problem2013
- Author(s)
  O.Watanabe
- Journal Title
  
  Algorithmica
  
  Volume: 66 Issue: 4 Pages: 848-868
- DOI
  10.1007/s00453-013-9762-7
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22300003, KAKENHI-PLANNED-24106008
[Journal Article] A Combinatorial Analysis for the Critical Clause Tree2013
- Author(s)
  Masaki Yamamoto
- Journal Title
  
  Theory Comput. Syst
  
  Volume: 52(2) Pages: 271-284
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] Derandomizing the HSSW Algorithm for 3-SAT2013
- Author(s)
  Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
- Journal Title
  
  Algorithmica
  
  Volume: 67(2) Pages: 112-124
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] A Combinatorial Analysis for the Critical Clause Tree2013
- Author(s)
  Masaki Yamamoto
- Journal Title
  
  Theory of Computing Systems
  
  Volume: 52(2) Issue: 2 Pages: 271-284
- DOI
  10.1007/s00224-012-9383-6
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-23700025, KAKENHI-PLANNED-24106008
[Journal Article] Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems2012
- Author(s)
  Yuichi Yoshida, Masaki Yamamoto, Hiro Ito
- Journal Title
  
  SIAM J. Comput
  
  Volume: 41(4) Pages: 1074-1093
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems2012
- Author(s)
  Yuichi Yoshida, Masaki Yamamoto, Hiro Ito
- Journal Title
  
  SIAM J. Comput.
  
  Volume: 41(4) Issue: 4 Pages: 1074-1093
- DOI
  10.1137/110828691
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22240001, KAKENHI-PROJECT-23700025, KAKENHI-PLANNED-24106003, KAKENHI-PROJECT-24800082, KAKENHI-PLANNED-24106008
[Journal Article] An exact algorithm for the Boolean connectivity problem for k-CNF2011
- Author(s)
  Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
- Journal Title
  
  Theor. Comput. Sci
  
  Volume: 412(35) Pages: 4613-4618
- NAID
  120003338848
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] Determining a Singleton Attractor of a Boolean Network with Nested Canalyzing Functions2011
- Author(s)
  Tatsuya Akutsu, Avraham A. Melkman, Takeyuki Tamura, Masaki Yamamoto
- Journal Title
  
  Journal of Computational Biology
  
  Volume: 18(10) Pages: 1275-1290
- NAID
  120003517916
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] Spectral Analysis of Random Sparse Matrices2011
- Author(s)
  Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto
- Journal Title
  
  IEICE Transactions
  
  Volume: 94-A(6) Pages: 1247-1256
- NAID
  10029802201
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise2011
- Author(s)
  Masaki Yamamoto, Shuji Kijima, Yasuko Matsui
- Journal Title
  
  J. Comb. Optim
  
  Volume: 22(3) Pages: 392-408
- NAID
  110007338415
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise2011
- Author(s)
  Masaki Yamamoto, Shuji Kijima
- Journal Title
  
  Journal of Combinatorial Optimization
  
  Volume: 22(3) Pages: 392-408
- NAID
  110007338415
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] Spectral Analysis of Random Sparse Matrices2011
- Author(s)
  Masaki Yamamoto, Tomonori Ando
- Journal Title
  
  IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
  
  Volume: 94-A(6) Pages: 1247-1256
- NAID
  10029802201
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-23700025
[Journal Article] An exact algorithm for the Boolean connectivity problem for k-CNF2011
- Author(s)
  Masaki Yamamoto, Kazuhisa Makino
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 412(35) Pages: 4613-4618
- NAID
  120003338848
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-23700025
[Presentation] Approximately counting paths and cycles in a graph2013
- Author(s)
  Masaki Yamamoto
- Organizer
  ICSG2013
- Place of Presentation
  Sapporo, Japan
- Invited
- Data Source
  KAKENHI-PROJECT-23700025
[Presentation] Approximately counting paths and cycles in a graph2013
- Author(s)
  Masaki Yamamoto
- Organizer
  Inference, Computation, and Spin Glasses (ICSG2013)
- Place of Presentation
  Sapporo, Japan (A satellite meeting of STATPHYS 25, Seoul, Korea)
- Data Source
  KAKENHI-PROJECT-23700025
[Presentation] A tighter lower bound on the circuit size of the hardest Boolean functions2011
- Author(s)
  Masaki Yamamoto
- Organizer
  Electronic Colloquium on Computational Complexity (ECCC) 18:86
- Data Source
  KAKENHI-PROJECT-23700025
[Presentation] Derandomizing HSSW Algorithm for 3-SAT2011
- Author(s)
  Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
- Organizer
  COCOON 2011 : 1-12
- Data Source
  KAKENHI-PROJECT-23700025
[Presentation] Derandomizing HSSW Algorithm for 3-SAT2011
- Author(s)
  Masaki Yamamoto, Kazuhisa Makino
- Organizer
  COCOON2011
- Place of Presentation
  Dallas, U.S.A.
- Data Source
  KAKENHI-PROJECT-23700025
[Presentation] Approximately counting paths and cycles in a graph
- Author(s)
  Masaki Yamamoto
- Organizer
  ELC Workshop on Inference, Computation, and Spin Glasses
- Place of Presentation
  Sapporo, Japan
- Data Source
  KAKENHI-PLANNED-24106008
[Presentation] Analysis of message passing algorithms for the 3XORSAT problem
- Author(s)
  Takeshi Koshiba, Ryuhei Mori, Osamu Watanabe, Masaki Yamamoto
- Organizer
  ELC Workshop on Inference, Computation, and Spin Glasses
- Place of Presentation
  Sapporo, Japan
- Data Source
  KAKENHI-PLANNED-24106008

1. Watanabe Osamu (80158617)

# of Collaborated Projects: 1 results

# of Collaborated Products: 2 results
2. KABASHIMA Yoshiyuki (80260652)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
3. HUKUSHIMA Koji (80282606)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
4. 安藤映 (20583511)

# of Collaborated Projects: 1 results

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

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
6. 小柴健史 (60400800)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
7. 森立平 (60732857)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
8. Krzakala Florent

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
9. Zdeborova Lenka

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
10. Zhou Haijun

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
11. 伊藤大雄

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results

Yamamoto Masaki 山本 真基

MASAKI Yamamoto 山本 真基

Research Projects

Research Products

Co-Researchers

Exploring the Limits of Computation from the Statistical Physics

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Proposing new sapmling algorithmsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

[Journal Article] Approximately counting paths and cycles in a graph2017

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Message passing algorithms for MLS-3LIN problem2013

Author(s)

Journal Title

DOI

Data Source

[Journal Article] A Combinatorial Analysis for the Critical Clause Tree2013

Author(s)

Journal Title

Data Source

[Journal Article] Derandomizing the HSSW Algorithm for 3-SAT2013

Author(s)

Journal Title

Data Source

[Journal Article] A Combinatorial Analysis for the Critical Clause Tree2013

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems2012

Author(s)

Journal Title

Data Source

[Journal Article] Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems2012

Author(s)

Journal Title

DOI

Data Source

[Journal Article] An exact algorithm for the Boolean connectivity problem for k-CNF2011

Author(s)

Journal Title

NAID

Data Source

[Journal Article] Determining a Singleton Attractor of a Boolean Network with Nested Canalyzing Functions2011

Author(s)

Journal Title

NAID

Data Source

[Journal Article] Spectral Analysis of Random Sparse Matrices2011

Author(s)

Journal Title

NAID

Data Source

[Journal Article] A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise2011

Author(s)

Journal Title

NAID

Data Source

[Journal Article] A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise2011

Author(s)

Journal Title

NAID

Data Source

[Journal Article] Spectral Analysis of Random Sparse Matrices2011

Author(s)

Journal Title

NAID

Data Source

[Journal Article] An exact algorithm for the Boolean connectivity problem for k-CNF2011

Yamamoto Masaki 山本真基

MASAKI Yamamoto 山本真基