博士（人間・環境学）, 京都大学

制約充足

充足可能性

論理と推論

人工知能

離散アルゴリズム

情報通信, ソフトウェア

情報通信, 情報学基礎論

情報通信, 知能情報学

2018年03月 - 現在
電気通信大学, 大学院情報理工学研究科 情報･ネットワーク工学専攻

2016年04月 - 2018年02月
電気通信大学, 大学院情報理工学研究科 情報･ネットワーク工学専攻

2014年03月 - 2016年03月
電気通信大学, 大学院情報システム学研究科 情報システム基盤学専攻

2012年04月01日 - 2014年02月28日
北海道大学, 情報科学研究科, 学術研究員

2012年04月01日 - 2014年02月28日
JST ERATO湊離散構造処理系プロジェクト, 博士研究員

2006年04月01日 - 2008年03月31日
富士通研究所, 自律システム研究部, 研究員

2009年04月 - 2012年03月
京都大学, 大学院人間・環境学研究科, 共生人間学専攻, 博士後期課程

2004年04月 - 2006年03月
京都大学, 大学院人間・環境学研究科, 共生人間学専攻, 博士前期課程

2009年04月01日 - 2004年03月31日
京都大学, 総合人間学部, 基礎科学科

2004年03月31日
京都大学, 総合人間学部, 基礎科学科

2000年04月01日
京都大学, 工学部, 物理工学科

2021年06月 - 現在
論文誌デジタルプラクティス編集委員, 論文誌デジタルプラクティス編集委員会

2017年04月 - 現在
Mathematical Reviews 査読者, 米国数学会

2023年 - 2024年
電子情報通信学会 英文論文誌A 小特集 編集委員

2021年04月 - 2024年
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）

2019年08月 - 2024年
Program committee member, International Joint Conferences on Artificial Intelligence

2021年03月 - 2023年03月
program committee member, International Conference on Smart Computing and Artificial Intelligence

2018年04月 - 2022年04月
運営委員, 情報処理学会 アルゴリズム研究会

2020年04月01日 - 2022年03月31日
編集委員, 電子情報通信学会ISSソサエティ誌

2016年06月01日 - 2021年06月01日
専門委員, 電子情報通信学会 ED コンピュテーション研究会

2020年04月01日 - 2021年03月31日
代表会員, 情報処理学会

2020年04月01日 - 2021年03月31日
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）

2020年04月01日 - 2021年03月31日
情報処理学会 代表会員

2016年04月01日 - 2021年03月31日
企画委員, 人工知能学会

2019年10月 - 2020年10月
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）

2019年10月 - 2020年10月
電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）編集委員

2020年04月01日
電子情報通信学会 情報・システムソサイエティ誌 編集委員

2017年04月01日 - 2020年03月31日
人工知能学会 人工知能基本問題研究会 幹事

2017年04月01日 - 2020年03月31日
幹事, 人工知能学会 人工知能基本問題研究会

2016年04月01日 - 2020年03月31日
情報処理学会 会誌編集委員会専門委員会(基礎・理論分野/FWG), 2018年幹事
2019年主査

2016年04月01日 - 2020年03月31日
編集委員, 情報処理学会 会誌編集委員会専門委員会(基礎・理論分野/FWG), 2018年幹事
2019年主査

2018年10月 - 2019年10月
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）

2018年10月 - 2019年10月
電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）編集委員

2018年04月 - 2019年06月
情報処理学会 第81回全国大会 プログラム委員

2018年04月 - 2019年06月
プログラム委員, 情報処理学会 第81回全国大会

2016年06月01日 - 2019年06月
電子情報通信学会 ED リエゾン委員

2016年06月01日 - 2019年06月
リエゾン委員, 電子情報通信学会 ED

2015年12月 - 2019年06月
電子情報通信学会 情報・システムソサイエティ 論文賞選定委員

2015年12月 - 2019年06月
論文賞選定委員, 電子情報通信学会 情報・システムソサイエティ

2015年06月04日 - 2019年06月
電子情報通信学会 情報・システムソサイエティ英文論文誌編集委員会

2015年06月04日 - 2019年06月
編集委員会, 電子情報通信学会 情報・システムソサイエティ英文論文誌

2018年04月 - 2019年03月
LAシンポジウム事務局

2018年04月 - 2019年03月
事務局, LAシンポジウム

2017年10月01日 - 2018年10月
電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）編集委員, 2019年からゲストエディタ（編集幹事）

2017年10月01日 - 2018年10月
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）, 2019年からゲストエディタ（編集幹事）

2018年04月
情報処理学会 アルゴリズム研究会 運営委員

2016年06月01日
電子情報通信学会 ED コンピュテーション研究会専門委員

2016年04月01日
人工知能学会 企画委員

Toward Individual Fairness Testing with Data Validity
Takashi Kitamura; Sousuke Amasaki; Jun Inoue; Yoshinao Isobe; Takahisa Toda
Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering, ACM, 掲載ページ 2284-2288, 出版日 2024年10月27日, 査読付
研究論文（国際会議プロシーディングス）, 英語

Diversity-aware fairness testing of machine learning classifiers through hashing-based sampling.
Zhenjiang Zhao; Takahisa Toda; Takashi Kitamura
責任著者, Inf. Softw. Technol., 167巻, 掲載ページ 107390-107390, 出版日 2024年03月, 査読付
研究論文（学術雑誌）, 英語

Approximation-guided Fairness Testing through Discriminatory Space Analysis.
Zhenjiang Zhao; Takahisa Toda; Takashi Kitamura 0001
Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering, 掲載ページ 1007-1018, 出版日 2024年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Solving Reconfiguration Problems of First-Order Expressible Properties of Graph Vertices with Boolean Satisfiability
Takahisa Toda; Takehiro Ito; Jun Kawahara; Takehide Soh; Akira Suzuki; Junichi Teruyama
筆頭著者, The 35th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2023), 掲載ページ 294-302, 出版日 2023年11月, 査読付
研究論文（国際会議プロシーディングス）, 英語

ZDD-based algorithmic framework for solving shortest reconfiguration problems
Takehiro Ito; Jun Kawahara; Yu Nakahata; Takehide Soh; Akira Suzuki; Junichi Teruyama; Takahisa Toda
CPAIOR, 出版日 2023年05月, 査読付
研究論文（国際会議プロシーディングス）

Efficient Fairness Testing Through Hash-Based Sampling
Zhenjiang Zhao; Takahisa Toda; Takashi Kitamura
責任著者, Search-Based Software Engineering, Springer International Publishing, 掲載ページ 35-50, 出版日 2022年11月15日, 査読付
論文集(書籍)内論文, 英語

Applying Combinatorial Testing to Verification-Based Fairness Testing
Takashi Kitamura; Zhenjiang Zhao; Takahisa Toda
Search-Based Software Engineering, Springer International Publishing, 掲載ページ 101-107, 出版日 2022年11月15日, 査読付
論文集(書籍)内論文

交差回避制約を用いた単純配線決定問題のCSP解法
渡辺 光洋; 戸田貴久
ラスト(シニア)オーサー, 電子情報通信学会論文誌D, 電子情報通信学会, J104-D巻, 04号, 出版日 2021年04月, 査読付
研究論文（学術雑誌）, 日本語

Interval-based Counterexample Analysis for Error Explanation
Takahisa Toda; Takeru Inoue
筆頭著者, Journal of Information Processing, Information Processing Society of Japan, 62巻, 10号, 掲載ページ 630-639, 出版日 2021年, 査読付
研究論文（学術雑誌）, 英語

Exact Method for Generating Strategy-Solvable Sudoku Clues
Kohei Nishikawa; Takahisa Toda
ラスト(シニア)オーサー, Algorithms, MDPI AG, 13巻, 7号, 掲載ページ 171-171, 出版日 2020年07月16日, 査読付, A Sudoku puzzle often has a regular pattern in the arrangement of initial digits and it is typically made solvable with known solving techniques called strategies. In this paper, we consider the problem of generating such Sudoku instances. We introduce a rigorous framework to discuss solvability for Sudoku instances with respect to strategies. This allows us to handle not only known strategies but also general strategies under a few reasonable assumptions. We propose an exact method for determining Sudoku clues for a given set of clue positions that is solvable with a given set of strategies. This is the first exact method except for a trivial brute-force search. Besides the clue generation, we present an application of our method to the problem of determining the minimum number of strategy-solvable Sudoku clues. We conduct experiments to evaluate our method, varying the position and the number of clues at random. Our method terminates within 1 min for many grids. However, as the number of clues gets closer to 20, the running time rapidly increases and exceeds the time limit set to 600 s. We also evaluate our method for several instances with 17 clue positions taken from known minimum Sudokus to see the efficiency for deciding unsolvability.
研究論文（学術雑誌）

Extended Min-Hash Focusing on Intersection Cardinality
Hisashi Koga; Satoshi Suzuki; Taiki Itabashi; Gibran Fuentes Pineda; Takahisa Toda
IDEAL, 1巻, 掲載ページ 17-26, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語

ZDDs and enumeration problems: State-of-the-art techniques and programming tool
Takahisa Toda; Toshiki Saitoh; Hiroaki Iwashita; Jun Kawahara; Shin ichi Minato
Computer Software, 34巻, 3号, 掲載ページ 97-120, 出版日 2017年08月, 査読付, Combinatorial enumeration problems are to find all combinations of items (solutions) that satisfy given constraints. There are many applications to various problems that are closely related to real-life such as power distribution network analysis. Recent researches have paid attention to a generic framework for computing various combinatorial enumeration problems through the method of efficiently constructing the data structure, ZDD, for all solutions of those problems in a top-down fashion, which is thus called top-down ZDD construction. The paper focuses on this subject and provides a comprehensive survey on algorithms that the construction is based on, an extended method for efficiently handling complicated constraints, the basics of the programming tool, TdZdd, that allows us to easily develop top-down construction-based programs, and practical programming examples of some applied problems.
研究論文（学術雑誌）

Dualization of boolean functions using ternary decision diagrams
Takahisa Toda
筆頭著者, ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, SPRINGER, 79巻, 1-3号, 掲載ページ 229-244, 出版日 2017年03月, 査読付, Dualization of Boolean functions is a fundamental problem that appears in various fields such as artificial intelligence, logic, data mining, etc. For monotone Boolean functions, many empirical researches that focus on practical efficiency have recently been done. We extend our previous work for monotone dualization and present a novel method for dualization that allows us to handle any Boolean function, including non-monotone Boolean functions. We furthermore present a variant of this method in cooperation with all solutions solver. By experiments we evaluate efficiency and characteristics of our methods.
研究論文（学術雑誌）, 英語

ZDDと列挙問題―最新の技法とプログラミングツール
戸田 貴久; 斎藤 寿樹; 岩下 洋哲; 川原 純; 湊 真一
コンピュータ ソフトウェア, 日本ソフトウェア科学会, 34巻, 3号, 掲載ページ 3_97-3_120, 出版日 2017年, 査読付, 列挙問題とは，与えられた条件を満たす対象(解)をすべて求める問題であり，電力網解析など社会のさまざまな問題への応用がある．さまざまな組合せ列挙問題に対して，問題の解集合を表現するデータ構造ZDDを高速に求める方法(トップダウンZDD構築法)を通して元の問題を効率的に解く汎用的な手法の研究が近年盛んに行われている.本論文ではトップダウンZDD構築に焦点を絞り，基礎となるアルゴリズムから，複雑な問題制約に対処するための発展的手法，プログラミングツールTdZddの基本的な使い方，さらに，具体的な応用問題を例にしたプログラミングまで解説する.
日本語

Exploiting Functional Dependencies of Variables in All Solutions SAT Solvers
Takahisa Toda; Takeru Inoue
筆頭著者, Journal of Information Processing, Information Processing Society of Japan, 25巻, 掲載ページ 459-468, 出版日 2017年, 査読付
研究論文（学術雑誌）

Improved compression-based pattern recognition exploiting new useful features
Taichi Uchino; Hisashi Koga; Takahisa Toda
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10255巻, 掲載ページ 363-371, 出版日 2017年, 査読付, Compression-based pattern recognition measures the similarity between objects with relying on data compression techniques. This paper improves the current compression-based pattern recognition by exploiting new useful features which are easy to obtain. In particular, we study the two known methods called PRDC (Pattern Representation on Data Compression) and NMD (Normalized Compression Distance). PRDC represents an object x with a feature vector that lines up the compression ratios derived by compressing x with multiple dictionaries. We smartly enhance PRDC by extracting new novel features from the compressed files. NMD measures the similarity between two objects by comparing their compression dictionaries. We extend NMD by incorporating the length of words in the dictionaries into the similarity measure.
研究論文（国際会議プロシーディングス）, 英語

Fast Exact Algorithm to Solve Continuous Similarity Search for Evolving Queries
Tomohiro Yamazaki; Hisashi Koga; Takahisa Toda
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10648巻, 掲載ページ 84-96, 出版日 2017年, 査読付, We study the continuous similarity search problem for evolving queries which has recently been formulated. Given a data stream and a database composed of n sets of items, the purpose of this problem is to maintain the top-k most similar sets to the query which evolves over time and consists of the latest W items in the data stream. For this problem, the previous exact algorithm adopts a pruning strategy which, at the present time T, decides the candidates of the top-k most similar sets from past similarity values and computes the similarity values only for them. This paper proposes a new exact algorithm which shortens the execution time by computing the similarity values only for sets whose similarity values at T can change from time T- 1. We identify such sets very fast with frequency-based inverted lists (FIL). Moreover, we derive the similarity values at T in O(1) time by updating the previous values computed at time T- 1. Experimentally, our exact algorithm runs faster than the previous exact algorithm by one order of magnitude.
研究論文（国際会議プロシーディングス）, 英語

Implementing Efficient All Solutions SAT Solvers
Takahisa Toda; Takehide Soh
筆頭著者, ACM Journal of Experimental Algorithmics, Association for Computing Machinery (ACM), 21巻, 掲載ページ 1-44, 出版日 2016年11月04日, 査読付, All solutions SAT (AllSAT for short) is a variant of the propositional satisfiability problem. AllSAT has been relatively unexplored compared to other variants despite its significance. We thus survey and discuss major techniques of AllSAT solvers. We accurately implemented them and conducted comprehensive experiments using a large number of instances and various types of solvers including a few publicly available software. The experiments revealed the solvers’ characteristics. We made our implemented solvers publicly available so that other researchers can easily develop their solvers by modifying our code and comparing it with existing methods.
研究論文（学術雑誌）

ZDDと列挙問題 - 最新の技法とプログラミングツール
戸田貴久; 斎藤寿樹; 岩下洋哲; 川原純; 湊真一
日本ソフトウェア科学会論文誌 コンピュータソフトウェア, 34巻, 3号, 掲載ページ 97-120, 出版日 2016年, 査読付, 招待
研究論文（学術雑誌）, 日本語

Effective Construction of Compression-based Feature Space
Hisashi Koga; Yuji Nakajima; Takahisa Toda
PROCEEDINGS OF 2016 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2016), IEEE, -巻, -号, 掲載ページ 116-120, 出版日 2016年, 査読付, This paper investigates how to construct a feature space for compression-based pattern recognition which judges the similarity between two objects z and y through the compression ratio to compress x with y('s dictionary). Specifically, we focus on the known framework called PRDC which represents an object x as a compression-ratio vector (CV) that lines up the compression ratios after x is compressed with multiple different dictionaries. For PRDC, the dimensions, i.e., the dictionaries determine the quality of CV space. This paper presents a practical technique to modify the chosen dictionaries which improves the performance of pattern recognition substantially by making them more independent.
研究論文（国際会議プロシーディングス）, 英語

BDD Construction for All Solutions SAT and Efficient Caching Mechanism
Takahisa Toda; Koji Tsuda
筆頭著者, 30TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING, VOLS I AND II, ASSOC COMPUTING MACHINERY, 掲載ページ 1880-1886, 出版日 2015年, 査読付, We improve an existing OBDD-based method of computing all total satisfying assignments of a Boolean formula, where an OBDD means an ordered binary decision diagram that is not necessarily reduced. To do this, we introduce lazy caching and finer caching by effectively using unit propagation. We implement our methods on top of a modern SAT solver, and show by experiments that lazy caching significantly accelerates the original method and finer caching in turn reduces an OBDD size.
研究論文（国際会議プロシーディングス）, 英語

Superset Generation on Decision Diagrams
Takahisa Toda; Shogo Takeuchi; Koji Tsuda; Shin-ichi Minato
筆頭著者, WALCOM: Algorithms and Computation, LNCS, 8973巻, 掲載ページ 317-322, 出版日 2015年, 査読付
研究論文（国際会議プロシーディングス）, 英語

超大規模なグラフ構造の効率的な処理技術
戸田 貴久; 竹内 聖悟; 美添 一樹
電子情報通信学会誌, 97巻, 12号, 掲載ページ 1097-1102, 出版日 2014年12月01日, 本稿では，大規模グラフ処理に関する三つの異なる課題を挙げ，実用上の性能を向上させる手法について解説する．はじめに，列挙問題における網羅的な場合分け処理を二分決定グラフを用いて効率化させる方法について述べる．次にSimpathアルゴリズムの並列化においてメモリ共有環境の性質を考慮し性能を向上させる例について述べる．そして，ゲーム木探索の大規模並列化におけるGPS将棋の例を述べ，分散ハッシュ表を用いた並列探索手法についても述べる．
研究論文（学術雑誌）, 日本語

Implicit Generation of Pattern-Avoiding Permutations by Using Permutation Decision Diagrams
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E97A巻, 6号, 掲載ページ 1171-1179, 出版日 2014年06月, 査読付, Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure pi DDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.
研究論文（学術雑誌）, 英語

乗法標準形で与えられた論理関数に対する二分決定グラフ構築の効率化
岩下 洋哲; 戸田 貴久; 津田 宏治; 湊 真一
人工知能学会全国大会論文集, 一般社団法人 人工知能学会, 2014巻, 0号, 掲載ページ 1D4OS11a2i-1D4OS11a2i, 出版日 2014年, 査読付,

SAT技術の発展にともない、様々な制約問題をCNF（乗法標準形）による論理式に符号化する技術が広く実用化されている。一方、制約問題からBDD（二分決定グラフ）を構築することができればBDDの強力な機能を用いた多様なアプリケーションを考えることができる。本発表では、制約問題のBDDをCNFから構築することを考え、その効率化のための様々な手法について議論する。

日本語

Dualization of Boolean Functions Using Ternary Decision Diagrams
Takahisa Toda
筆頭著者, Proceedings of the 13th International Symposium on Artificial Intelligence and Mathematics (ISAIM2014), 掲載ページ 1-7, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Three-way Indexing ZDDs for Large-Scale Sparse Datasets
Hiroshi Aoki; Takahisa Toda; Shin-ichi Minato
TRENDS AND APPLICATIONS IN KNOWLEDGE DISCOVERY AND DATA MINING, SPRINGER-VERLAG BERLIN, 8643巻, 掲載ページ 457-469, 出版日 2014年, 査読付, Zero-suppressed decision diagrams (ZDDs) are a data structure for representing combinations over item sets. They have been applied to many areas such as data mining. When ZDDs represent large-scale sparse datasets, they tend to obtain an unbalanced form, which results performance degradation. In this paper, we propose a new data structure three-way indexing ZDD, as a variant of ZDDs. We furthermore present algorithms to convert between three-way indexing ZDDs and ordinary ZDDs. Experimental results show the effectiveness of our data structure and algorithms.
研究論文（国際会議プロシーディングス）, 英語

A General Framework for Parallel Unary Operations on ZDDs
Shogo Takeuchi; Takahisa Toda; Shin-ichi Minato
TRENDS AND APPLICATIONS IN KNOWLEDGE DISCOVERY AND DATA MINING, SPRINGER-VERLAG BERLIN, 8643巻, 掲載ページ 494-503, 出版日 2014年, 査読付, A zero-suppressed binary decision diagram is a compressed data structure that represents families of sets. There are various basic operations to manipulate families of sets over ZDDs such as union, intersection, and difference. They can be efficiently computed without decompressing ZDDs. Among them, there are many important unary operations such as computing the ZDD for all extremal sets ( maximal sets or minimal sets) from an input ZDD. Unary operations are useful in various fields such as constraint programming, data mining, and artificial intelligence. Therefore, they must be efficiently computed. In this paper, we propose a general framework for parallel unary operations on ZDDs. We analyze the computational complexity and evaluate the effectiveness of our method by performing computational experiments.
研究論文（国際会議プロシーディングス）, 英語

Efficiently generating classical and vincular pattern avoiding permutations based on permutation decision diagrams
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
In Proc. of Permutation Patterns 2013, 掲載ページ 43-44, 出版日 2013年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語

二分決定グラフに基づく大規模ハイパーグラフの双対化とその応用
戸田貴久; 戸田貴久; 湊真一; 湊真一
人工知能学会全国大会論文集(CD-ROM), 人工知能学会, 27th巻, 掲載ページ ROMBUNNO.2E5-OS-09B-4-4, 出版日 2013年06月
日本語

順列二分決定グラフを用いたパターン回避順列の列挙索引化
井上 祐馬; 戸田 貴久; 湊 真一
情報処理学会研究報告. AL, アルゴリズム研究会報告, 一般社団法人情報処理学会, 2013巻, 5号, 掲載ページ 1-8, 出版日 2013年02月, パターン回避順列とは,任意の部分列が特定の順序関係を持たないような順列をいう.パターン回避順列は,VLSIの設計などの応用に現れるフロアプランとの対応が明らかになるなど,応用分野でも近年注目を集めている.本稿では,順列集合を効率的に扱うことができるπDDというデータ構造に基づき,パターン回避順列,およびその拡張である隣接条件付きパターン回避順列を列挙索引化するアルゴリズムを示す.
研究論文（研究会，シンポジウム資料等）, 日本語

On separating families of bipartitions
Takahisa Toda; Ivo Vigan
DISCRETE MATHEMATICS, ELSEVIER SCIENCE BV, 313巻, 3号, 掲載ページ 286-292, 出版日 2013年02月, 査読付, We focus on families of bipartitions, i.e. set partitions consisting of at most two components. A family of bipartitions is a separating family for a set if every two elements in the set are separated by some bipartition. In this paper we enumerate separating families of arbitrary size. We furthermore enumerate inclusion-wise minimal separating families of minimum and maximum sizes. (C) 2012 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語

Fast compression of large-scale hypergraphs for solving combinatorial problems
Takahisa Toda
筆頭著者, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 8140巻, 掲載ページ 281-293, 出版日 2013年, 査読付, We present a fast algorithm to compress hypergraphs into the data structure ZDDs. We furthermore analyze the computational complexity. Our algorithm uses multikey Quicksort given by Bentley and Sedgewick. By conducting experiments with various datasets, we show that our algorithm is significantly faster and requires much smaller memory than an existing method. © 2013 Springer-Verlag.
研究論文（国際会議プロシーディングス）, 英語

Hypergraph transversal computation with binary decision diagrams
Takahisa Toda
筆頭著者, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7933巻, 掲載ページ 91-102, 出版日 2013年, 査読付, We study a hypergraph transversal computation: given a hypergraph, the problem is to generate all minimal transversals. This problem is related to many applications in computer science and various algorithms have been proposed. We present a new efficient algorithm using the compressed data structures BDDs and ZDDs, and we analyze the time complexity for it. By conducting computational experiments, we show that our algorithm is highly competitive with existing algorithms. © 2013 Springer-Verlag.
研究論文（国際会議プロシーディングス）, 英語

Extracting co-occurrence relations from ZDDs
Takahisa Toda
筆頭著者, Algorithms, 5巻, 4号, 掲載ページ 654-667, 出版日 2012年, 査読付, A zero-suppressed binary decision diagram (ZDD) is a graph representation suitable for handling sparse set families. Given a ZDD representing a set family, we present an efficient algorithm to discover a hidden structure, called a co-occurrence relation, on the ground set. This computation can be done in time complexity that is related not to the number of sets, but to some feature values of the ZDD. We furthermore introduce a conditional co-occurrence relation and present an extraction algorithm, which enables us to discover further structural information. © 2012 by the author.
研究論文（学術雑誌）, 英語

On Separating Convex Points with Lines
Takahisa Toda; Ivo Vigan
Congressus Numerantium, 214巻, 掲載ページ 143-153, 出版日 2012年, 査読付
研究論文（学術雑誌）, 英語

On Partitioning Colored Points
Takahisa Toda
筆頭著者, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E94A巻, 6号, 掲載ページ 1242-1246, 出版日 2011年06月, 査読付, P. Kirchberger proved that, for a finite subset X of R-d such that each point in X is painted with one of two colors, if every d+2 or fewer points in X can be separated along the colors, then all the points in X can be separated along the colors. In this paper, we show a more colorful theorem.
研究論文（学術雑誌）, 英語

Multipolytopes and Their Duality
Takahisa Toda
筆頭著者, Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 掲載ページ 457-464, 出版日 2011年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Convex sets in real projective space and its application to computational geometry
Takahisa Toda
筆頭著者, Proceedings of the 7th Japan Conference on Computational Geometry and Graphs, 掲載ページ 20-21, 出版日 2009年, 査読付
研究論文（国際会議プロシーディングス）, 英語

不確実な信念を持つ人狼知能エージェントの論理モデルと仮説推論手法の開発に向けて
高田 雄太; 戸田 貴久
責任著者, 人狼知能の研究では，だましたり，見破ったり，説得したりといった行為をあたかも人間がやるかのように模倣する知的エージェントの実現が大きな目標の１つである．本研究では，他のエージェント の発言や行動，あるいは，人狼ゲームのレギュレーションに論理的に矛盾しないようなふるまいをするエージェントを実現するための実践的な枠組みの開発を目的にする． この目的に向けて，本研究では不確実な信念を持つエージェントの論理モデルを考案する． さらに，そのような論理モデルの下で記述した知識をもとにして不確実な事象に対する推論手法を考案する．また，これらの課題点について議論する．, 一般社団法人 人工知能学会, 出版日 2024年05月, 人工知能学会全国大会論文集, JSAI2024巻, 掲載ページ 4Xin285-4Xin285, 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議）, 2758-7347

形式検証によるXGBoostの個人公平性テストの試み
趙 振江; 戸田 貴久; 北村 崇師
責任著者, 近年，機械学習モデルの普及とともに，機械学習モデルの公平性に関する懸念が高まっている．公平性の懸念に取り組む概念の一つとして，個人公平性は，センシティブな属性（例えば，性別，人種，年齢など）以外の属性が同じ値を持つ二人に対してモデルが同じ予測結果を与えることを求める．そうではない場合は，そのモデルが個人公平性に違反していると言う．個人公平性テストは与えられたモデルが個人公平性に違反しているかどうかをテストする．XGBoost は近年最も注目を集めている機械学習モデルの一つである．本研究では，XGBoost の個人公平性テストのために形式検証を活用する方法を提案する．結果として，我々は提案手法を実装し，実世界のデータ上に構築された XGBoost モデルに対して公平性テストを実施して，提案手法を評価する．, 一般社団法人 人工知能学会, 出版日 2024年05月, 人工知能学会全国大会論文集, JSAI2024巻, 掲載ページ 2L6OS19b04-2L6OS19b04, 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議）, 2758-7347

ZDDを用いた組合せ遷移ソルバー
伊藤健洋; 川原純; 中畑裕; 宋剛秀; 鈴木顕; 照山順一; 戸田貴久
出版日 2022年, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2022巻, 1883-1893, 202202232397203031

超大規模なグラフ構造の効率的な処理技術 (小特集 ｢フカシギの数え方｣から広がるアルゴリズムの理工学 : 二分決定グラフによる離散構造処理と広がる応用分野)
戸田 貴久; 竹内 聖悟; 美添 一樹
電子情報通信学会, 出版日 2014年12月, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, 97巻, 12号, 掲載ページ 1097-1102, 日本語, 0913-5693, 40020285042

論理関数のCNFからBDDの効率的な構築法 (システム数理と応用)
戸田 貴久
論理関数のCNFが与えられるとき,その論理式を表す二分決定グラフBDDを構築するための新しい手法を提案する.CNFは従来から用いられている論理関数の伝統的な表現法の一つである.BDDには論理関数を操作するための様々な演算が備わっているので,CNFよりもBDDを用いる方が適切な多くの問題がある.しかし,CNFからBDDの構築は自明な計算ではない.本稿では,まずCNFを表す中間表現を計算し,それからBDDに変換する二段階のBDD構築法を提案する.さらに,提案法で中間表現として用いられるデータ構造は,BDD構築だけでなく,有向グラフ上の列挙問題など様々な問題に対して有用であることも示す., 一般社団法人電子情報通信学会, 出版日 2013年11月06日, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113巻, 279号, 掲載ページ 15-22, 日本語, 0913-5685, 110009886659, AA12529664

論理関数のCNFからBDDの効率的な構築法
戸田貴久
論理関数の CNF が与えられるとき，その論理式を表す二分決定グラフ BDD を構築するための新しい手法を提案する．CNF は従来から用いられている論理関数の伝統的な表現法の一つである．BDD には論理関数を操作するための様々な演算が備わっているので，CNF よりも BDD を用いる方が適切な多くの問題がある．しかし，CNF から BDD の構築は自明な計算ではない．本稿では，まず CNF を表す中間表現を計算し，それから BDD に変換する二段階の BDD 構築法を提案する．さらに，提案法で中間表現として用いられるデータ構造は，BDD 構築だけでなく，有向グラフ上の列挙問題など様々な問題に対して有用であることも示す．We propose an algorithm to construct the binary decision diagram (BDD) for a CNF formula of a Boolen function. A CNF formula is a usual representation of Boolean functions and has been used for a long time. On the other hand, various operations to manipulate Boolean functions are available in a BDD, and thus there are many problems where using BDDs are more efficient, however converting CNFs to BDDs is not a trivial task. In this paper, we propose a construction algorithm through two stages: we first compute an intermediate representation of a CNF formula, and then construct the corresponding BDD. We furthermore show that the data structure used as an intermediate representation is useful not only in BDD construction, but also in various problems such as enumeration problems on directed graphs., 一般社団法人情報処理学会, 出版日 2013年10月30日, 研究報告アルゴリズム（AL）, 2013巻, 3号, 掲載ページ 1-8, 日本語, 0913-5685, 110009614883, AN1009593X

巨大で疎な組合せ集合を表現するための三分索引化ZDD
青木 洋士; 戸田 貴久; 湊 真一
ZDDはアイテムの組合せ集合を表現するデータ構造である.ZDDは様々なデータマイニングなどの問題に利用されている.巨大で疎な組合せ集合を表すZDDは,バランスの悪い形状になりやすく,これは性能の低下の原因になりやすい.本稿では,ある種のZDDとして三分索引化ZDDを提案する.さらに,三分索引化ZDDと従来のZDDとの変換アルゴリズムを示す.計算機実験により,提案データ構造のZDDと比べた優位性を示す., 一般社団法人電子情報通信学会, 出版日 2013年10月11日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 113巻, 252号, 掲載ページ 1-8, 日本語, 110009820599, AN10013152

超高速グラフ列挙アルゴリズム –フカシギの数え方が拓く，組合せ問題の新アプローチ−
ERATO 湊離散構造処理系プロジェクト
学術書, 日本語, 共著, 第２章, 森北出版, 出版日 2015年04月08日, ISBN 9784627852617

SMTソルバーのAPIファザーMurxlaのカバレッジ改善に向けて, 第27回プログラミングおよびプログラミング言語ワークショップ
久保 拓巳; 戸田 貴久
ポスター発表, 第27回プログラミングおよびプログラミング言語ワークショップ
発表日 2025年03月07日

単位伝播で決定可能な補問題の拡張CNF表現に関する検討
戸田 貴久
口頭発表（一般）, コンピュテーション研究会
発表日 2025年03月07日

検証ベースの公平性テスト技術の近似性能に関する考察
趙 振江; 戸田 貴久; 北村 崇師
ポスター発表, ソフトウェア工学の基礎ワークショップ
発表日 2024年11月29日

制約求解を用いない検証ベースの公平性テスト技術
趙 振江; 戸田 貴久; 北村 崇師
ポスター発表, 第27回情報論的学習理論ワークショップ
発表日 2024年11月06日

決定木ベースモデルへのロバスト性の検証技術を利用したブラックボックス手法の検討
久保 拓巳; 戸田 貴久
ポスター発表, 第27回情報論的学習理論ワークショップ
発表日 2024年11月06日

多様性を重視した公平性テスト技術とその多様性の考察
趙 振江; 戸田 貴久; 北村 崇師
ポスター発表, 第３０回ソフトウェア工学の基礎ワークショップ
発表日 2023年11月10日
開催期間 2023年11月09日- 2023年11月11日

だます人狼知能エージェントに関する初期的な考察
八木 啓至; 戸田 貴久
口頭発表（一般）, 第49回ゲーム情報学研究発表会
発表日 2023年03月18日
開催期間 2023年03月17日- 2023年03月18日

機械学習モデルのテスト・検証への論理的アプローチ
戸田貴久
口頭発表（招待・特別）, 人工知能学会 第124回人工知能基本問題研究会, 招待
発表日 2023年03月17日
開催期間 2023年03月17日- 2023年03月17日

決定的従属関係の含まれるベイジアンネットワークの近似推論手法に関する考察
中島祐輝; 戸田貴久
口頭発表（一般）, 情報処理学会 第85回全国大会
発表日 2023年03月04日
開催期間 2023年03月02日- 2023年03月04日

ナイーブベイズ分類器におけるデルタ公平性
戸田貴久
口頭発表（一般）, ウィンターワークショップ2023
発表日 2023年01月21日
開催期間 2023年01月20日- 2023年01月21日

機械学習モデルの公平性のテスト手法
趙 振江; 戸田 貴久; 北村 崇師
口頭発表（一般）, 第64回 プログラミング・シンポジウム 2023
発表日 2023年01月06日
開催期間 2023年01月06日- 2023年01月08日

制約最適化に基づく画像の時間順並び替え
久保 拓巳; 戸田 貴久; 古賀 久志
口頭発表（一般）, 第141回数理モデル化と問題解決研究発表会
発表日 2022年12月12日
開催期間 2022年12月12日- 2022年12月13日

機械学習モデルの公平性テスト手法VBT-Xと今後の展望
趙 振江; 戸田 貴久; 北村 崇師
ポスター発表, 情報論的学習理論ワークショップ
発表日 2022年11月22日
開催期間 2022年11月20日- 2022年11月23日

ハッシュベースサンプリングによる効率的な公平性テスト
趙 振江; 戸田 貴久; 北村 崇師
ポスター発表, ソフトウェア工学の基礎ワークショップ
発表日 2022年11月12日
開催期間 2022年11月10日- 2022年11月12日

類似学習節に基づくCDCLソルバーの高速化
趙 振江; 戸田 貴久
口頭発表（一般）, 日本語, 第36回人工知能学会全国大会, 京都, 国内会議
発表日 2022年06月17日

不確実性下における複合イベントの確率推定システムの開発
戸田 貴久; 夏 涛; 中島 祐輝; 八木 啓至
ポスター発表, 日本語, 第36回人工知能学会全国大会, 京都, 国内会議
発表日 2022年06月16日

属性間依存度を考慮したデータベースの安全なフラグメント化
磯田 飛鳥; 戸田 貴久
口頭発表（一般）, 日本語, 第14回データ工学と情報マネジメントに関するフォーラム, 情報処理学会, オンライン, 国内会議
発表日 2022年03月01日

有界モデル検査による独立集合遷移問題の解法に関する考察
戸田 貴久; 伊藤 健洋; 川原 純; 宋 剛秀; 鈴木 顕; 照山 順一
口頭発表（一般）, 日本語, 第186回アルゴリズム研究発表会, 情報処理学会, オンライン, 国内会議
発表日 2022年01月28日

不確実性下における複合イベント処理に関する考察
夏 涛; 戸田 貴久
口頭発表（一般）, 日本語, 第186回アルゴリズム研究発表会, 情報処理学会, オンライン, 国内会議
発表日 2022年01月28日

命題論理式の解の一様サンプリングの改善
中島 祐輝; 戸田 貴久
口頭発表（一般）, 日本語, 第20回情報科学技術フォーラム, オンライン, 国内会議
発表日 2021年08月27日

SATフィルターの検討
戸田貴久
口頭発表（一般）, 日本語, 基盤(S) 離散構造処理系プロジェクト「2019年度 秋のワークショップ」, 北海道千歳市, 国内会議
発表日 2019年11月06日

SATサンプリングとその周辺
戸田貴久
口頭発表（一般）, 日本語, 基盤(S) 離散構造処理系プロジェクト「短期滞在セミナー週間 (SSSW) 2019.09」, 北海道札幌市, 国内会議
発表日 2019年09月18日

制約言語の観点におけるCP4IMの複雑さ
戸田貴久
ポスター発表, 日本語, 基盤(S) 離散構造処理系プロジェクト「2019年度 初夏のワークショップ」, 北海道札幌市, 国内会議
発表日 2019年06月28日

交差回避制約によるSAT型ナンバーリンクソルバーの高速化
渡辺光洋; 戸田貴久
口頭発表（一般）, 日本語, 第１０８回人工知能基本問題研究会, 人工知能学会, 長崎県長崎市, 国内会議
発表日 2019年03月14日

モデル検査における反例空間の構造解析
戸田貴久
口頭発表（一般）, 日本語, 人工知能学会 第107回人工知能基本問題研究会(SIG-FPAI), 国内会議
発表日 2018年08月

ユークリッド距離に基づく多観点非類似度とその分割最適化クラスタリングへの応用
藤原勇二; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 人工知能学会 第106回人工知能基本問題研究会(SIG-FPAI), 国内会議
発表日 2018年03月

共通要素を類似度とするハッシュベース集合間類似検索手法の改善
鈴木 聡; 古賀 久志; Gibran FUENTES; PINEDA Gibran; 戸田 貴久
口頭発表（一般）, 日本語, 第10回データ工学と情報マネジメントに関するフォーラム(DEIM2018)
発表日 2018年03月

多観点類似度を用いた凝集型階層クラスタリング
藤原勇二; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 第16回情報科学技術フォーラム, 国内会議
発表日 2017年09月

モデル検査における反例発見から反例列挙への拡張
戸田貴久
口頭発表（一般）, 日本語, 基盤(S) 離散構造処理系プロジェクト「2017年度 初夏のワークショップ」, 北海道札幌市, 国内会議
発表日 2017年06月

集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム
山崎智博; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 信学技報, 国内会議
発表日 2017年05月

命題論理式を充足する変数割当の網羅的探索手法について
戸田貴久
口頭発表（招待・特別）, 日本語, 人工知能学会 第103回人工知能基本問題研究会(SIG-FPAI), 招待, 人工知能学会, 大分県由布市, 国内会議
発表日 2017年03月

効率的なAllSATソルバーの実装と評価
戸田貴久; 宋剛秀
口頭発表（一般）, 日本語, 第19回プログラミングおよびプログラミング言語ワークショップ（PPL2017）, 山梨県笛吹市, 国内会議
発表日 2017年03月

命題論理式を充足する変数割当の網羅的探索手法について
戸田貴久
口頭発表（招待・特別）, 日本語, 人工知能学会 第103回人工知能基本問題研究会(SIG-FPAI), 招待, 国内会議
発表日 2017年03月

擬似ブール制約を解く
戸田貴久
ポスター発表, 日本語, 情報系WINTER FESTA Episode2, 河原林ERATOプロジェクト, 東京, 国内会議
発表日 2016年12月

擬似ブール制約を解く
戸田貴久
口頭発表（一般）, 日本語, 基盤(S) 離散構造処理系プロジェクト「2016年度 秋のワークショップ」, 基盤(S) 離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2016年11月

AllSATにおける変数従属関係
戸田貴久; 井上武
ポスター発表, 日本語, 基盤(S) 離散構造処理系プロジェクト「2016年度 初夏のワークショップ」, 基盤(S) 離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2016年06月

変数間の支配関係に基づく論理式の全解列挙手法
戸田貴久; 井上武
口頭発表（一般）, 日本語, 第30回人工知能学会全国大会, 福岡県北九州市, 国内会議
発表日 2016年06月

適応的に類似度を選択する類似画像検索方式
小林 馨; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2016年

部分構造の類似性を考慮したMin-Hashベースのグラフ類似検索
宮田昂充; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2016年

共通要素数を重視したハッシュベース集合間類似検索
板橋 大樹; 古賀 久志; Gibran Fuentes Pineda GIBRAN; 戸田 貴久
口頭発表（一般）, 日本語, 第8回データ工学と情報マネジメントに関するフォーラム(DEIM2016), 国内会議
発表日 2016年

全解列挙型SATソルバー
戸田貴久
ポスター発表, 日本語, 情報系WINTER FESTA, 国内会議
発表日 2015年12月22日

AllSATソルバの最近の進展
戸田貴久
口頭発表（一般）, 日本語, Genome Privacy CREST セミナートーク, 国内会議
発表日 2015年11月

BDDに基づくALLSATソルバーを用いたアイテムセットマイニング
戸田貴久
口頭発表（一般）, 日本語, 第29回人工知能学会全国大会, 2H4-OS-03a-3in, 国内会議
発表日 2015年05月

BDDを用いたALLSATの枠組みとパターンマイニングへの応用
戸田貴久
公開講演，セミナー，チュートリアル，講習，講義等, 日本語, 招待, IBM 東京基礎研究所, IBM 東京基礎研究所
発表日 2015年04月09日

ハイパーグラフにおける極大独立集合列挙のためのZDD構築手法
菅谷輝治
口頭発表（一般）, 日本語, 電子情報通信学会 コンピュテーション研究会, 国内会議
発表日 2015年03月09日

ALLSATのためのBDD構築および効率的なキャッシング技法
戸田貴久
口頭発表（一般）, 日本語, 人工知能学会 第97回人工知能基本問題研究会(SIG-FPAI), 国内会議
発表日 2015年03月

All Solutions SAT, BDD Compilation and Pattern Mining
Takahisa Toda
ポスター発表, 英語, JST ERATO Kawarabayashi Large Graph Project / Minato Discrete Structure Manipulation System Project Joint Workshop
発表日 2015年01月

2段階グラフカットを用いた動画からの移動物体抽出
土田和生; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 情報処理学会 コンピュータビジョンとイメージメディア研究会, 国内会議
発表日 2015年

Efficient Caching Mechanism in BDD Compilation
Takahisa Toda
口頭発表（一般）, 英語, ERATO-ALSIP Special Seminar 2014, 国際会議
発表日 2014年12月13日

Dualization Using Decision Diagrams and Its Application for Itemset Mining
Takahisa Toda
口頭発表（招待・特別）, 英語, Decision Diagrams in Optimization I, INFORMS2014, 招待, 国際会議
発表日 2014年11月10日

DPLL型BDD構築法の改善
戸田貴久
口頭発表（一般）, 日本語, ２０１４年度秋のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道礼文島, 国内会議
発表日 2014年09月

サイクル描画について
戸田貴久
公開講演，セミナー，チュートリアル，講習，講義等, 日本語, 第20回列挙アルゴリズムセミナー, 群馬県渋川市, 国内会議
発表日 2014年09月

SATソルバーを用いたBDD構築法
戸田貴久
口頭発表（一般）, 日本語, 第5回CSPSAT2研究会, 兵庫県神戸市, 国内会議
発表日 2014年08月21日

Generating Permutations under Pattern Occurence Constraints Using PiDDs
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
口頭発表（一般）, 英語, The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery, in conjunction with PAKDD 2014, Tainan, Taiwan, 国際会議
発表日 2014年05月13日

A General Framework for Parallel Unary Operations on ZDDs
Shogo Takeuchi; Takahisa Toda; Shin-ichi Minato
口頭発表（一般）, 英語, The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery, in conjunction with PAKDD 2014, Tainan, Taiwan, 国際会議
発表日 2014年05月13日

Three-way Indexing ZDDs for Large-scale Sparse Datasets
Hiroki Aoki; Takahisa Toda; Shin-ichi Minato
口頭発表（一般）, 英語, The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery, in conjunction with PAKDD 2014, Tainan, Taiwan, 国際会議
発表日 2014年05月13日

乗法標準形で与えられた論理関数に対する二分決定グラフ構築の効率化
岩下洋哲; 戸田貴久; 津田 宏治; 湊真一
口頭発表（一般）, 日本語, 第28回人工知能学会全国大会, 人工知能学会, 愛媛県松山市, 国内会議
発表日 2014年05月12日

メモリ階層を考慮したBDD演算とその並列化
戸田貴久
ポスター発表, 日本語, ２０１４年度春のワークショップ, ERATO湊離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2014年04月19日

ZDDにおける単項演算並列化の一般的枠組みの提案
竹内聖悟; 戸田貴久; 津田宏治; 湊真一
口頭発表（一般）, 日本語, 第９２回人工知能基本問題研究会, 北海道函館市, 国内会議
発表日 2014年01月31日

圧縮性に基づくパターン認識手法における特徴空間の改善
中島優次; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 電子情報通信学会 パターン認識・メディア理解研究会, 国内会議
発表日 2014年

Twitterを利用した時事イベントとローカルイベントの同時検出
尾久陽平; 古賀久志; 戸田貴久
口頭発表（一般）, 日本語, 電子情報通信学会 パターン認識・メディア理解研究会, 国内会議
発表日 2014年

論理関数のCNFからBDDの効率的な構築法
戸田貴久
口頭発表（一般）, 日本語, ２０１３年度秋のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道登別市, 国内会議
発表日 2013年11月

論理関数のCNFからBDDの効率的な構築法
戸田貴久
口頭発表（一般）, 日本語, 第１４５回アルゴリズム研究会, 情報処理学会研究回報告, 情報処理学会, 岩手県花巻市, 国内会議
発表日 2013年10月30日

巨大で疎な組合せ集合を表現するための三分索引化ZDD
青木洋士; 戸田貴久; 湊真一
口頭発表（一般）, 日本語, コンピューテーション研究会、信学技報, 電子情報通信学会, 愛知県名古屋市, 国内会議
発表日 2013年10月

二分決定グラフに基づくハイパーグラフ極小横断の列挙
戸田貴久
ポスター発表, 日本語, 第12回情報科学技術フォーラム, 電子情報通信学会 情報処理学会, 鳥取県鳥取市, 国内会議
発表日 2013年09月

二分決定グラフに基づく大規模ハイパーグラフの双対化
戸田貴久
口頭発表（一般）, 日本語, 第3回CSPSAT2研究会, 北海道札幌市, 国内会議
発表日 2013年07月26日

Efficiently generating classical and vincular pattern avoiding permutations based on permutation decision diagrams
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
口頭発表（一般）, 英語, Permutation Patterns 2013, Paris, France, 国際会議
発表日 2013年07月04日

二分決定グラフに基づく極小横断の列挙
戸田貴久
公開講演，セミナー，チュートリアル，講習，講義等, 日本語, 組合せ数学セミナー, 東京都目黒区, 国内会議
発表日 2013年07月

二分決定グラフに基づくハイパーグラフ極小横断の列挙
戸田貴久
ポスター発表, 日本語, ２０１３年度初夏のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市
発表日 2013年06月

三分木によるZDDのパス長の均一化手法
青木洋士; 戸田貴久; 湊真一
ポスター発表, 日本語, ２０１３年度初夏のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2013年06月

二分決定グラフに基づく大規模ハイパーグラフの双対化とその応用
戸田貴久; 湊真一
口頭発表（一般）, 日本語, ２０１３年度人工知能学会全国大会（第27回）, 人工知能学会, 富山県富山市, 国内会議
発表日 2013年06月

大規模ハイパーグラフからZDDの高速な構築アルゴリズム
戸田貴久
口頭発表（一般）, 日本語, アルゴリズム研究会, 情報処理学会, 北海道小樽市, 国内会議
発表日 2013年05月

２分決定グラフに基づくハイパーグラフ双対化
戸田貴久
公開講演，セミナー，チュートリアル，講習，講義等, 日本語, 第17回列挙アルゴリズムセミナー, 群馬県渋川市, 国内会議
発表日 2013年04月

順列二分決定グラフを用いたパターン回避順列の列挙索引化
井上祐馬; 戸田貴久; 湊真一
口頭発表（一般）, 日本語, アルゴリズム研究会、情処研報, 情報処理学会, 福島県福島市, 国内会議
発表日 2013年03月

On Separating Convex Points with Lines
戸田貴久; Ivo Vigan
口頭発表（一般）, 日本語, ERATOセミナー, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2012年11月

二分決定グラフを用いたフロアプランの解析に向けて
戸田貴久
口頭発表（一般）, 日本語, ２０１２年度秋のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道夕張市, 国内会議
発表日 2012年10月

二分決定グラフから変数同等関係の抽出
戸田貴久
ポスター発表, 日本語, ２０１２年度初夏のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2012年06月

２分割のなす分離族の数え上げ
戸田貴久; Ivo Vigan
口頭発表（一般）, 日本語, 2011年度冬のLAシンポジウム予稿集, 京都府京都市, 国内会議
発表日 2012年01月

２分割のなす分離族おん数え上げ
戸田貴久; Ivo Vigan
口頭発表（一般）, 日本語, ERATOセミナー, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, 国内会議
発表日 2011年12月26日

集合を粉砕する二分割の集まりはいくつあるか？
戸田貴久; Ivo Vigan
ポスター発表, 日本語, 列挙学校, 神奈川県三浦郡湘南国際村センター, 国内会議
発表日 2011年09月

On Partitioning Colored Points
Takahisa Toda
ポスター発表, 英語, Kyoto Prize Satellite Workshop in Honor of Professor Laszlo Lovasz, 国立情報学研究所 東工大グローバルCOE「計算世界観の深化と展開」, 東工大蔵前会館（東京工業大学大岡山キャンパス）, 国内会議
発表日 2010年11月

色付きの点の集まりはいつ超平面によりその色付け通りに分割できるか？
戸田貴久
口頭発表（一般）, 日本語, 第21回代数、論理、幾何と情報科学研究集会, 滋賀県草津市
発表日 2010年09月

色付きの点の集まりはいつ超平面によりその色付け通りに分割できるか？
戸田貴久
口頭発表（一般）, 日本語, 2010年度夏のLAシンポジウム予稿集, 富山県氷見市, 国内会議
発表日 2010年07月

Multi-convex sets in real projective spaces and their duality
Takahisa Toda
口頭発表（一般）, 英語, Third Texas Southmost Geometry and Topology Conference, Texas, USA, 国際会議
発表日 2010年04月

与えられたどの凸多角形にも交差しない直線全体を構成するアルゴリズム
戸田貴久
口頭発表（一般）, 日本語, 2009年度冬のLAシンポジウム予稿集, 京都府京都市, 国内会議
発表日 2010年02月

What is a Convex Set in a Real Projective Space? - An Interesting Helly-type Theorem -
Takahisa Toda
ポスター発表, 英語, Combinatorics: Methods and Applications in Mathematics and Computer Science, Workshop II: Combinatorial Geometry, California, USA, 国際会議
発表日 2009年10月

Domain-theoretical aspects of convex sets in real projective space
Takahisa Toda
口頭発表（一般）, 英語, Continuity, Computability, Constructivity: From Logic to Algorithms, Koln/Cologne, Germany, 国際会議
発表日 2009年07月

コンピュータリテラシー
2022年04月 - 現在
電気通信大学

基礎プログラミングおよび演習（K課程）
2022年04月 - 現在
電気通信大学

計算数理
2020年04月 - 現在
工学院大学

計算量の理論
2019年04月 - 現在
法政大学

情報工学工房
2024年04月 - 2025年03月
電気通信大学

三大学協働基礎ゼミ
2025年 - 2025年

情報工学工房
2022年04月 - 2023年03月
電気通信大学

基礎プログラミングおよび演習
2016年04月 - 2022年03月
電気通信大学

K課程輪講
2020年04月 - 2021年03月
電気通信大学

大学院技術英語
2018年04月 - 2020年03月
電気通信大学

MICS実験第二
2019年04月
電気通信大学

情報システム基盤学基礎１
2014年04月 - 2016年03月
電気通信大学

数理科学特論I
2015年10月 - 2015年10月
京都大学

情報システム基盤学基礎２
電気通信大学

工学アプローチによる組合せ遷移の展開：配電切替を足がかりとして汎用ソルバーへ
川原 純; 飯岡 大輔; 戸田 貴久; 宋 剛秀; 鈴木 顕; 照山 順一; 中畑 裕
日本学術振興会, 科学研究費助成事業 学術変革領域研究(B), 京都大学, 学術変革領域研究(B), 本研究では組合せ遷移の実装技術の構築とその産業応用に向けて、研究開発の共通基盤となるソフトウェア開発を目標とする。初年度にあたる本年度は、広く知られているグラフの独立集合の遷移問題（独立集合遷移問題）に対して、4種のアプローチを検討した。1つ目は、組合せ遷移の技法を用いたアルゴリズムの設計であり、主に、状態空間の部分探索の手法を検討した。2つ目は、SAT（充足可能性問題）ソルバーを活用するアプローチである。有限整数領域上の制約を命題論理式へと変換する SAT 符号化を行い、SATソルバーの強力な推論性能を用いて独立集合遷移問題を解くソルバーを開発した。3つ目は、ゼロサプレス型二分決定グラフ (ZDD) を活用するアプローチである。当初予定では、ZDD を上記2手法に援用した高速化を想定していたが、本研究において、ZDD が表す独立集合族を直接遷移させるアルゴリズムの開発に成功したため、ZDD を単独で用いて独立集合遷移問題を解くことが可能になった。4つ目の手法は、当初は予定していない新たな構想であるが、モデル検査と呼ばれる、システムの形式的な検査を可能にする技術を用いた手法である。入力グラフと開始、目標独立集合が与えられた際に、開始集合から目標集合に遷移可能ではないことを検証する記述をモデル検査ソルバーに与え、遷移可能な場合は反例として解となる遷移列を出力する。 以上の4つの技法について、アルゴリズム設計と実装を行った。アルゴリズムの比較実験のためには、適切な入力データが必要であるが、組合せ遷移問題に対する広く知られたベンチマークデータは存在しないため、入力データの作成整備を行った。 配電切替への組合せ遷移技術の適用についても研究を行い、配電切替を全域木遷移問題として定式化し、4つの技法の適用を検討して、実装を行っている。, 20H05794
研究期間 2020年10月 - 2023年03月

大規模制約充足問題の全解探索のための実用的な計算基盤の確立とその応用
戸田 貴久
日本学術振興会, 科学研究費助成事業 若手研究(B), 電気通信大学, 若手研究(B), 本研究では、制約充足問題のすべての解を探索する手法を活用して、そのような解探索が求められる高度な問題解決のための効率的な計算基盤の開発を行った。主な成果として、ハードウェアやソフトウェアの不具合の原因解析を支援するための自動化手法を開発した。 他の成果として、VLSIの単純配線問題や数独ヒント生成問題の効率的な解法を提案した。また新たな展開として、制約充足問題の解のサンプリング手法の開発とその応用、制約充足問題の最適化を応用したデータベースの匿名化に関する手法の開発など、当初想定していなかったプライバシー・セキュリティ関係の研究成果も得られた。, 17K17725
研究期間 2017年04月 - 2022年03月

決定グラフを用いた超大規模ヒッティング集合の列挙・索引化とその知識発見への応用
戸田 貴久
日本学術振興会, 科学研究費助成事業 若手研究(B), 電気通信大学, 若手研究(B), 本研究課題では、極小ヒッティング集合の列挙問題やその拡張問題（論理関数の双対化およびAll Solutions SAT問題）に対する実用上効率的な計算法の研究に取り組んだ。今回新たに考案した計算手法だけでなく、関連する主要な従来手法についても実装したソフトウェアを開発し、その有効性や特性を明らかにするために大規模な性能評価実験を実施した。それらの結果は誰でも利用できる形で公開している。また、知識発見への応用に向けて、本研究課題で得られた最新のソフトウェアをアイテムセットマイニング問題に適用し、実データを用いた評価実験を行い、今後の研究課題や各種の知見を得た。, 26870011
研究期間 2014年04月 - 2018年03月

組合せ最適化の研究助成
戸田 貴久
株式会社富士通研究所, 研究助成, 研究代表者
研究期間 2017年10月

組合せ最適化の研究助成
戸田 貴久
株式会社富士通研究所, 研究助成, 研究代表者
研究期間 2016年10月

状態遷移評価装置、状態遷移評価方法
特許権, 戸田貴久, 井上武, 特願2016-101190, 出願日: 2016年05月20日, 日本電信電話株式会社、国立大学法人 電気通信大学, 特開2017-208001, 公開日: 2017年11月24日, 特許第6602259, 発行日: 2019年10月18日

情報処理学会 第85回全国大会 学生セッション（アルゴリズム）座長
大会・シンポジウム等, パネル司会・セッションチェア等, 情報処理学会, 実施期間 2023年03月 - 2023年03月

ウィンターワークショップ 2023 T4: 機械学習システムの公平性とソフトウェア工学
学会・研究会等, 企画立案・運営等, 実施期間 2023年01月20日 - 2023年01月21日