玉置 卓

最終更新日時:2017/07/20 10:18:19

印刷する

氏名(漢字/フリガナ/アルファベット表記)
玉置 卓/タマキ スグル/Suguru Tamaki
所属部署・職名(部局/所属/講座等/職名)
情報学研究科/通信情報システム専攻コンピュータ工学講座/助教
学部兼担
部局 所属 講座等 職名
工学部 工学部 情報学科
取得学位
学位名(日本語) 学位名(英語) 大学(日本語) 大学(英語) 取得区分
修士(情報学) 京都大学
博士(情報学) 京都大学
プロフィール
(日本語)
2006年京都大学大学院情報学研究科 博士課程修了。情報学博士。特任助教等を経て2009年1月より京都大学大学院情報学研究科通信情報システム専攻 助教。専門は理論計算機科学、とりわけアルゴリズム論や計算理論。充足可能性問題等の計算困難な組合せ問題に対する厳密アルゴリズム、近似アルゴリズムと近似困難性、および、数理論理学における証明系の計算複雑さの研究を行っている。
(英語)
He got Ph.D. in 2006 from Kyoto University. After working as a postdoctoral researcher, he is now an assistant professor of Graduate School of Informatics, Kyoto University. His research interests are mainly algorithms and computation theory. He is currently working on design and analysis of exact and approximation algorithms, hardness of approximation and complexity of propositional proof systems.
研究テーマ
(日本語)
厳密指数時間アルゴリズム, 近似アルゴリズム, 近似困難性, 証明計算量
(英語)
Exact Exponential Algorithm, Approximation Algorithm, Hardness of Approximation, Proof Complexity
研究分野(キーワード)
キーワード(日本語) キーワード(英語)
理論計算機科学 Theoretical Computer Science
離散数学 Discrete Mathematics
計算の理論 Theory of Computation
アルゴリズム理論 Theory of Algorithm
研究分野(科研費分類コード)
科研費分類コード
情報学基礎
論文 > 論文
(文系研究者の一般的な論文集への寄稿や単行本の分担執筆などは「著書等」を参照してください)
著者名 タイトル 書誌情報等 年月 査読の有無 言語
Suguru Tamaki and Osamu Watanabe Local Restrictions from the Furst-Saxe-Sipser Paper Theory of Computing Systems,60,1,20-32 2017/01 英語
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama Improved Exact Algorithms for Mildly Sparse Instances of Max SAT Theoretical Computer Science, to appear 2017 英語
Suguru Tamaki Parallel Repetition of Two Prover One Round Games: An Exposition Interdisciplinary Information Sciences,21,4,289-306 2015/12 英語
Suguru Tamaki and Yuichi Yoshida A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness Random Structures & Algorithms,47,2,386-406 2015/09 英語
Takayuki Sakai, Kazuhisa Seto and Suguru Tamaki Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction Theory of Computing Systems,57,2,426-443 2015/08 英語
Kazuhisa Makino,Suguru Tamaki,Masaki Yamamoto Derandomizing the HSSW Algorithm for 3-SAT. Algorithmica,67,2,112-124 2013/10 英語
玉置 卓 メタアルゴリズムと計算限界証明の不思議な関係 電子情報通信学会誌,96,9,679-682 2013/09 日本語
Kazuhisa Seto,Suguru Tamaki A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Computational Complexity,22,2,245-274 2013/06
Kazuhisa Makino,Suguru Tamaki,Masaki Yamamoto An exact algorithm for the Boolean connectivity problem for k-CNF. Theor. Comput. Sci.,412,35,4613-4618 2011/08 英語
Kazuhisa Makino,Suguru Tamaki,Masaki Yamamoto On the Boolean connectivity problem for Horn relations. Discrete Applied Mathematics,158,18,2024-2030 2010/11 英語
Kazuo Iwama,Kazuhisa Seto,Suguru Tamaki The Planar Hajós Calculus for Bounded Degree Graphs. IEICE Transactions,93-A,6,1000-1007 2010/05 英語
Kazuo Iwama,Kazuhisa Seto,Suguru Tamaki The complexity of the Hajós calculus for planar graphs. Theor. Comput. Sci.,411,7-9,1182-1191 2010/02 英語
Youichi Hanatani,Takashi Horiyama,Kazuo Iwama,Suguru Tamaki New Graph Calculi for Planar Non-3-Colorable Graphs. IEICE Transactions,91-A,9,2301-2307 2008/09 英語
Kazuo Iwama,Suguru Tamaki Exploiting partial knowledge of satisfying assignments. Discrete Applied Mathematics,155,12,1596-1603 2007/06 英語

  • <<
  • >>
  • 表示
論文 > 国際学会
(文系研究者の一般的な論文集への寄稿や単行本の分担執筆などは「著書等」を参照してください)
著者名 タイトル 書誌情報等 年月 査読の有無 言語
Akinori Kawachi, Kenichi Kawano, François Le Gall and Suguru Tamaki Quantum Query Complexity of Unitary Operator Discrimination Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON) 2017/08 英語
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams and Huacheng Yu Beating Brute Force for Systems of Polynomial Equations over Finite Fields Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA),2190-2202 2017/01 英語
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS),82:1-82:16 2016/08 英語
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal and Suguru Tamaki Circuit size lower bounds and #SAT upper bounds through a general framework Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS),45:1-45:16 2016/08 英語
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama Improved Exact Algorithms for Mildly Sparse Instances of Max SAT Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC),90-101 2015/09 英語
Suguru Tamaki,Yuichi Yoshida Robust Approximation of Temporal CSP. Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 18th International Workshop on Randomization and Computation (RANDOM),419-432 2014/09 英語
Takayuki Sakai,Kazuhisa Seto,Suguru Tamaki Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction. Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT),32-47 2014/07 英語
Suguru Tamaki,Yuichi Yoshida Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues. Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 16th International Workshop on Randomization and Computation (RANDOM),313-324 2012/08 英語
Kazuhisa Seto,Suguru Tamaki A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. Proceedings of the 27th IEEE Conference on Computational Complexity (CCC),107-116 2012/06 英語
Gábor Kun,Ryan O'Donnell,Suguru Tamaki,Yuichi Yoshida,Yuan Zhou Linear programming, width-1 CSPs, and robust satisfaction. Proceedings of the 3rd ACM-SIGACT Conference on Innovations in Theoretical Computer Science (ITCS),484-495 2012/01 英語
Kazuhisa Makino,Suguru Tamaki,Masaki Yamamoto Derandomizing HSSW Algorithm for 3-SAT. Proceedings of the 17th Annual International Conference on Computing and Combinatorics (COCOON),1-12 2011/08 英語
Kazuo Iwama,Kazuhisa Seto,Tadashi Takai,Suguru Tamaki Improved Randomized Algorithms for 3-SAT. Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), Part I,73-84 2010/12 英語
Suguru Tamaki,Yuichi Yoshida A Query Efficient Non-adaptive Long Code Test with Perfect Completeness. Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 14th International Workshop on Randomization and Computation (RANDOM),738-751 2010/09 英語
Kazuhisa Makino,Suguru Tamaki,Masaki Yamamoto An Exact Algorithm for the Boolean Connectivity Problem for k-CNF. Proceedings of the 13th International Conference on Theory and Applications of Satisfiability Testing (SAT),172-180 2010/07 英語
Kazuhisa Makino,Suguru Tamaki,Masaki Yamamoto On the Boolean Connectivity Problem for Horn Relations. Proceedings of the 10th International Conference on Theory and Applications of Satisfiability Testing (SAT),187-200 2007/05 英語
Kazuo Iwama,Suguru Tamaki Improved upper bounds for 3-SAT. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),328-329 2004/01 英語
Kazuo Iwama, Suguru Tamaki Exploiting Partial Knowledge of Satisfying Assignments Proceedings of the 5th International Workshop on Algorithm Engineering (WAE),118-128 2001/08 英語
Kazuo Iwama, Suguru Tamaki Exploiting Partial Knowledge of Satisfying Assignments (extended abstract) Proceedings of the 4th Workshop on Theory and Applications of Satisfiability Testing (SAT) 2001/06 英語

  • <<
  • >>
  • 表示
講演等 > 招待講演
(文系研究者の一般的な学会報告はこの項に収録されております)
タイトル 会合名 開催主体 年月 言語
有限体上の多変数連立代数方程式系に対する総当り探索の打破 [招待あり] 電子情報通信学会コンピュテーション研究会 2017/03 日本語
Recent Developments on Circuit Satisfiability Algorithms [Invited] Fine-Grained Complexity and Algorithm Design Reunion 2016/12 英語
Recent Developments on Circuit Satisfiability Algorithms [Invited] Computational Complexity Conference (CCC) Satellite Tokyo Workshop 2016/06 英語
Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC0[p] [Invited] Workshop on Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms 2015/11 英語
Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates [Invited] Workshop on Connections Between Algorithm Design and Complexity Theory 2015/10 英語
The Complexity of Robust Satisfiabilityof the Constraint Satisfaction Problem [Invited] Dagstuhl Seminar 14201 2014/05 英語
計算複雑さへの招待 (4): 計算限界証明における障壁 [招待あり] 電子情報通信学会コンピュテーション研究会 2013/10
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis [Invited] Dagstuhl Seminar 13331 2013/08 英語
3SATに対する乱択アルゴリズムの改良 [招待あり] ERATO湊離散構造処理系+NEO 合同研究会 2010/07
Hajós Calculusの計算複雑さ [招待あり] ワークショップ「離散アルゴリズムの最先端」 2009/02
3SATの計算時間について [招待あり] 京都大学 アルゴリズム・計算量・数理計画・OR・etc. 合同研究会 2004/04

  • <<
  • >>
  • 表示
講演等 > 一般講演
(文系研究者の一般的な学会報告はこの項に収録されております)
タイトル 会合名 開催主体 年月 言語
Solving Systems of Polynomial Equations over GF(2) via Degree Reduction [Invited] Department of Computer Science Colloquium, University of Nevada, Las Vegas 2015/10 英語
指数時間厳密アルゴリズム [招待あり] 学術情報メディアセンターセミナー 「アルゴリズムと計算量理論」 2011/10
確率的証明の威力 [招待あり] 情報学研究科通信情報システム専攻談話会 2008/12
著書等 > 著書
著者名 タイトル 出版社等 年月 言語
伊藤大雄, 宇野裕之 編著 離散数学のすすめ 現代数学社 2010/05 日本語
外部資金:競争的資金・科学研究費補助金
種別 代表/分担 テーマ(日本語) テーマ(英語) 期間
若手研究 (B) 代表 計算困難な組合せ問題に対するアルゴリズムの設計と解析 2008/04/01〜2011/03/31
基盤研究 (A) 分担 情報補填を可能にするアルゴリズムの設計と解析 2009/04/01〜2010/03/31
基盤研究 (A) 分担 空間的な情報補填を可能にするアルゴリズムの研究 2010/04/01〜2013/03/31
若手研究 (B) 代表 計算困難問題に対する厳密指数時間アルゴリズムの研究 2011/04/01〜2014/03/31
新学術領域研究 (研究領域提案型) 分担 情報理論・符号理論からの計算限界研究 2012/06/28〜2017/03/31
基盤研究 (A) 分担 データの巨大化から生じる不完全情報への対処に主眼をおいた近似計算 2013/04/01〜2016/03/31
基盤研究 (C) 代表 制約充足問題に対する効率の良い厳密および近似アルゴリズムの研究 2014/04/01〜2018/03/31
基盤研究 (B) 分担 入力データが不完全なアルゴリズムで重要となる乱化技術の研究 2016/4〜2020/3
基盤研究(C) 代表 制約充足問題に対する効率の良い厳密および近似アルゴリズムの研究 (平成27年度分) 2015/04/01〜2016/03/31
基盤研究(C) 代表 制約充足問題に対する効率の良い厳密および近似アルゴリズムの研究 (平成28年度分) 2016/04/01〜2017/03/31
担当科目
講義名(日本語) 講義名(英語) 開講期 学部/研究科 期間
基礎情報処理演習(T20) 前期 工学部 2011/04〜2012/03
計算機科学実験及演習2(計算機) 後期 工学部 2011/04〜2012/03
計算機科学実験及演習2 Computer Science Laboratory and Exercise 2 後期 工学部 2012/04〜2013/03
計算機科学実験及演習2 Computer Science Laboratory and Exercise 2 後期 工学部 2013/04〜2014/03
計算機科学実験及演習2 Computer Science Laboratory and Exercise 2 後期 工学部 2014/04〜2015/03
計算機科学実験及演習2 Computer Science Laboratory and Exercise 2 後期 工学部 2015/04〜2016/03
計算機科学実験及演習2 Computer Science Laboratory and Exercise 2 後期 工学部 2016/04〜2017/03
計算機科学のための数学演習 Mathematics in Practice for Computer Science 前期 工学部 2016/04〜2017/03
計算機科学実験及演習2 Computer Science Laboratory and Exercise 2 後期 工学部 2017/04〜2018/03
計算機科学のための数学演習 Mathematics in Practice for Computer Science 前期 工学部 2017/04〜2018/03