Takahisa TODA
| Department of Computer and Network Engineering | Associate Professor |
| Cluster I (Informatics and Computer Engineering) | Associate Professor |
Researcher Information
Field Of Study
Career
- Mar. 2018 - Present
The University of Electro-Communications, Graduate School of Informatics and Engineering Department of Computer and Network Engineering - Apr. 2016 - Feb. 2018
The University of Electro-Communications, Graduate School of Informatics and Engineering Department of Computer and Network Engineering - Mar. 2014 - Mar. 2016
The University of Electro-Communications, Graduate School of Information Systems Department of Information System Fundamentals - 01 Apr. 2012 - 28 Feb. 2014
北海道大学, 情報科学研究科, 学術研究員 - 01 Apr. 2012 - 28 Feb. 2014
JST ERATO湊離散構造処理系プロジェクト, 博士研究員 - 01 Apr. 2006 - 31 Mar. 2008
富士通研究所, 自律システム研究部, 研究員
Educational Background
- Apr. 2009 - Mar. 2012
Kyoto University, Graduate School of Human and Environmental Studies, Department of Human Coexistence, 博士後期課程 - Apr. 2004 - Mar. 2006
Kyoto University, Graduate School of Human and Environmental Studies, Department of Human Coexistence, 博士前期課程 - 01 Apr. 2009 - 31 Mar. 2004
Kyoto University, 総合人間学部, 基礎科学科 - 31 Mar. 2004
Kyoto University, 総合人間学部, 基礎科学科 - 01 Apr. 2000
Kyoto University, 工学部, 物理工学科
Member History
- Jun. 2021 - Present
論文誌デジタルプラクティス編集委員, 論文誌デジタルプラクティス編集委員会 - Apr. 2017 - Present
Mathematical Reviews 査読者, 米国数学会 - 2023 - 2024
電子情報通信学会 英文論文誌A 小特集 編集委員 - Apr. 2021 - 2024
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号） - Aug. 2019 - 2024
Program committee member, International Joint Conferences on Artificial Intelligence - Mar. 2021 - Mar. 2023
program committee member, International Conference on Smart Computing and Artificial Intelligence - Apr. 2018 - Apr. 2022
運営委員, 情報処理学会 アルゴリズム研究会 - 01 Apr. 2020 - 31 Mar. 2022
編集委員, 電子情報通信学会ISSソサエティ誌 - 01 Jun. 2016 - 01 Jun. 2021
専門委員, 電子情報通信学会 ED コンピュテーション研究会 - 01 Apr. 2020 - 31 Mar. 2021
代表会員, 情報処理学会 - 01 Apr. 2020 - 31 Mar. 2021
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号） - 01 Apr. 2020 - 31 Mar. 2021
情報処理学会 代表会員 - 01 Apr. 2016 - 31 Mar. 2021
企画委員, 人工知能学会 - Oct. 2019 - Oct. 2020
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号） - Oct. 2019 - Oct. 2020
電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）編集委員 - 01 Apr. 2020
電子情報通信学会 情報・システムソサイエティ誌 編集委員 - 01 Apr. 2017 - 31 Mar. 2020
人工知能学会 人工知能基本問題研究会 幹事 - 01 Apr. 2017 - 31 Mar. 2020
幹事, 人工知能学会 人工知能基本問題研究会 - 01 Apr. 2016 - 31 Mar. 2020
情報処理学会 会誌編集委員会専門委員会(基礎・理論分野/FWG), 2018年幹事
2019年主査 - 01 Apr. 2016 - 31 Mar. 2020
編集委員, 情報処理学会 会誌編集委員会専門委員会(基礎・理論分野/FWG), 2018年幹事
2019年主査 - Oct. 2018 - Oct. 2019
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号） - Oct. 2018 - Oct. 2019
電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）編集委員 - Apr. 2018 - Jun. 2019
情報処理学会 第81回全国大会 プログラム委員 - Apr. 2018 - Jun. 2019
プログラム委員, 情報処理学会 第81回全国大会 - 01 Jun. 2016 - Jun. 2019
電子情報通信学会 ED リエゾン委員 - 01 Jun. 2016 - Jun. 2019
リエゾン委員, 電子情報通信学会 ED - Dec. 2015 - Jun. 2019
電子情報通信学会 情報・システムソサイエティ 論文賞選定委員 - Dec. 2015 - Jun. 2019
論文賞選定委員, 電子情報通信学会 情報・システムソサイエティ - 04 Jun. 2015 - Jun. 2019
電子情報通信学会 情報・システムソサイエティ英文論文誌編集委員会 - 04 Jun. 2015 - Jun. 2019
編集委員会, 電子情報通信学会 情報・システムソサイエティ英文論文誌 - Apr. 2018 - Mar. 2019
LAシンポジウム事務局 - Apr. 2018 - Mar. 2019
事務局, LAシンポジウム - 01 Oct. 2017 - Oct. 2018
電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）編集委員, 2019年からゲストエディタ（編集幹事） - 01 Oct. 2017 - Oct. 2018
編集委員, 電子情報通信学会 情報・システムソサイエティ英文論文誌D（特集号）, 2019年からゲストエディタ（編集幹事） - Apr. 2018
情報処理学会 アルゴリズム研究会 運営委員 - 01 Jun. 2016
電子情報通信学会 ED コンピュテーション研究会専門委員 - 01 Apr. 2016
人工知能学会 企画委員
Research Activity Information
Paper
- 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, 27 Oct. 2024, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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
Lead, The 35th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2023), 294-302, Nov. 2023, Peer-reviwed
International conference proceedings, English - ZDD-based algorithmic framework for solving shortest reconfiguration problems
Takehiro Ito; Jun Kawahara; Yu Nakahata; Takehide Soh; Akira Suzuki; Junichi Teruyama; Takahisa Toda
CPAIOR, May 2023, Peer-reviwed
International conference proceedings - 交差回避制約を用いた単純配線決定問題のCSP解法
渡辺 光洋; 戸田貴久
Last, 電子情報通信学会論文誌D, 電子情報通信学会, J104-D, 04, Apr. 2021, Peer-reviwed
Scientific journal, Japanese - Exact Method for Generating Strategy-Solvable Sudoku Clues
Kohei Nishikawa; Takahisa Toda
Last, Algorithms, MDPI AG, 13, 7, 171-171, 16 Jul. 2020, Peer-reviwed, 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.
Scientific journal - 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, Aug. 2017, Peer-reviwed, 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.
Scientific journal - Dualization of boolean functions using ternary decision diagrams
Takahisa Toda
Lead, ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, SPRINGER, 79, 1-3, 229-244, Mar. 2017, Peer-reviwed, 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.
Scientific journal, English - ZDDs and Enumeration Problems: State-of-The-Art Techniques and Programming Tool
TODA Takahisa; SAITOH Toshiki; IWASHITA Hiroaki; KAWAHARA Jun; MINATO Shin-ichi
Computer Software, Japan Society for Software Science and Technology, 34, 3, 3_97-3_120, 2017, Peer-reviwed, 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.
Japanese - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Implementing Efficient All Solutions SAT Solvers
Takahisa Toda; Takehide Soh
Lead, ACM Journal of Experimental Algorithmics, Association for Computing Machinery (ACM), 21, 1-44, 04 Nov. 2016, Peer-reviwed, 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.
Scientific journal - ZDDと列挙問題 - 最新の技法とプログラミングツール
戸田貴久; 斎藤寿樹; 岩下洋哲; 川原純; 湊真一
日本ソフトウェア科学会論文誌 コンピュータソフトウェア, 34, 3, 97-120, 2016, Peer-reviwed, Invited
Scientific journal, Japanese - 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, Peer-reviwed, 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.
International conference proceedings, English - BDD Construction for All Solutions SAT and Efficient Caching Mechanism
Takahisa Toda; Koji Tsuda
Lead, 30TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING, VOLS I AND II, ASSOC COMPUTING MACHINERY, 1880-1886, 2015, Peer-reviwed, 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.
International conference proceedings, English - Superset Generation on Decision Diagrams
Takahisa Toda; Shogo Takeuchi; Koji Tsuda; Shin-ichi Minato
Lead, WALCOM: Algorithms and Computation, LNCS, 8973, 317-322, 2015, Peer-reviwed
International conference proceedings, English - 超大規模なグラフ構造の効率的な処理技術
戸田 貴久; 竹内 聖悟; 美添 一樹
電子情報通信学会誌, 97, 12, 1097-1102, 01 Dec. 2014, 本稿では，大規模グラフ処理に関する三つの異なる課題を挙げ，実用上の性能を向上させる手法について解説する．はじめに，列挙問題における網羅的な場合分け処理を二分決定グラフを用いて効率化させる方法について述べる．次にSimpathアルゴリズムの並列化においてメモリ共有環境の性質を考慮し性能を向上させる例について述べる．そして，ゲーム木探索の大規模並列化におけるGPS将棋の例を述べ，分散ハッシュ表を用いた並列探索手法についても述べる．
Scientific journal, Japanese - 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, Jun. 2014, Peer-reviwed, 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.
Scientific journal, English - 乗法標準形で与えられた論理関数に対する二分決定グラフ構築の効率化
岩下 洋哲; 戸田 貴久; 津田 宏治; 湊 真一
人工知能学会全国大会論文集, 一般社団法人 人工知能学会, 2014, 0, 1D4OS11a2i-1D4OS11a2i, 2014, Peer-reviwed,SAT技術の発展にともない、様々な制約問題をCNF（乗法標準形）による論理式に符号化する技術が広く実用化されている。一方、制約問題からBDD（二分決定グラフ）を構築することができればBDDの強力な機能を用いた多様なアプリケーションを考えることができる。本発表では、制約問題のBDDをCNFから構築することを考え、その効率化のための様々な手法について議論する。
Japanese - Dualization of Boolean Functions Using Ternary Decision Diagrams
Takahisa Toda
Lead, Proceedings of the 13th International Symposium on Artificial Intelligence and Mathematics (ISAIM2014), 1-7, 2014, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Jul. 2013, Peer-reviwed
International conference proceedings, English - 二分決定グラフに基づく大規模ハイパーグラフの双対化とその応用
戸田貴久; 戸田貴久; 湊真一; 湊真一
人工知能学会全国大会論文集(CD-ROM), 人工知能学会, 27th, ROMBUNNO.2E5-OS-09B-4-4, Jun. 2013
Japanese - Enumerating and Indexing of Pattern Avoiding Permutations Using πDDs
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
IPSJ SIG Notes, 一般社団法人情報処理学会, 2013, 5, 1-8, Feb. 2013, Pattern avoiding permutation is a permutation whose subsequences don't match a certain order. Pattern avoiding permutation is discussed on not only theoretical areas but also application areas, for example, floorplan for compacting VLSI. In this paper, we provide the algorithms for enumerating and indexing of pattern avoiding permutations and vincular pattern avoiding permutations, which have a extend definition of pattern avoiding, based on the efficient data structure for the set of permutations, πDDs.
Symposium, Japanese - On separating families of bipartitions
Takahisa Toda; Ivo Vigan
DISCRETE MATHEMATICS, ELSEVIER SCIENCE BV, 313, 3, 286-292, Feb. 2013, Peer-reviwed, 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.
Scientific journal, English - Fast compression of large-scale hypergraphs for solving combinatorial problems
Takahisa Toda
Lead, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 8140, 281-293, 2013, Peer-reviwed, 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.
International conference proceedings, English - Hypergraph transversal computation with binary decision diagrams
Takahisa Toda
Lead, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7933, 91-102, 2013, Peer-reviwed, 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.
International conference proceedings, English - Extracting co-occurrence relations from ZDDs
Takahisa Toda
Lead, Algorithms, 5, 4, 654-667, 2012, Peer-reviwed, 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.
Scientific journal, English - On Separating Convex Points with Lines
Takahisa Toda; Ivo Vigan
Congressus Numerantium, 214, 143-153, 2012, Peer-reviwed
Scientific journal, English - On Partitioning Colored Points
Takahisa Toda
Lead, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E94A, 6, 1242-1246, Jun. 2011, Peer-reviwed, 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.
Scientific journal, English - Multipolytopes and Their Duality
Takahisa Toda
Lead, Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 457-464, 2011, Peer-reviwed
International conference proceedings, English - Convex sets in real projective space and its application to computational geometry
Takahisa Toda
Lead, Proceedings of the 7th Japan Conference on Computational Geometry and Graphs, 20-21, 2009, Peer-reviwed
International conference proceedings, English
MISC
- Toward development of logical model and abductive inference method of Werewolf agents with uncertain beliefs
TAKADA Yuta; TODA Takahisa
Corresponding, The Werewolf game is a game with incomplete information in which knowledge about the other players, such as roles assigned to players, is unknown and the game continues with debate about uncertain information or actions taken by players with uncertain beliefs until a win-condition is achieved. Aiming to develop an artificial intelligence that plays the Werewolf game, we consider a logical model for agents with uncertain beliefs based on BDI logic, and present a transformation of logical formulas from BDI logic to first-order logic so as to perform abductive inference on the private information of other players. We also discuss several issues of this approach to be resolved., The Japanese Society for Artificial Intelligence, May 2024, Proceedings of the Annual Conference of JSAI, JSAI2024, 4Xin285-4Xin285, Japanese, Summary national conference, 2758-7347 - Toward Individual Fairness Testing for XGBoost Classifier through Formal Verification
ZHAO Zhenjiang; TODA Takahisa; KITAMURA Takashi
Corresponding, There are growing concerns regarding the fairness of Machine Learning (ML) algorithms. Individual fairness testing is introduced to address the fairness concerns, and it aims to detect discriminatory instances which exhibit unfairness in a given classifier from its input space. XGBoost is one of the most prominent ML algorithms in recent years. In this study, we propose an individual fairness testing method for XGBoost classifier, leveraging the formal verification technique. To evaluate our method, we build XGBoost classifiers on three real-world datasets, and conduct individual fairness testing against them. Through the evaluation, we observe that our method can correctly detect discriminatory instances in XGBoost classifiers within an acceptable running time. Among all testing tasks, the longest running time for detecting 100 discriminatory instances is 2656.4 seconds., The Japanese Society for Artificial Intelligence, May 2024, Proceedings of the Annual Conference of JSAI, JSAI2024, 2L6OS19b04-2L6OS19b04, Japanese, Summary national conference, 2758-7347 - ZDDを用いた組合せ遷移ソルバー
伊藤健洋; 川原純; 中畑裕; 宋剛秀; 鈴木顕; 照山順一; 戸田貴久
2022, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2022, 1883-1893, 202202232397203031 - Efficient Processing Techniques for Very Large-scale Graph Structure
戸田 貴久; 竹内 聖悟; 美添 一樹
電子情報通信学会, Dec. 2014, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, 97, 12, 1097-1102, Japanese, 0913-5693, 40020285042 - Efficient Construction of BDDs from CNFs
戸田 貴久
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., The Institute of Electronics, Information and Communication Engineers, 06 Nov. 2013, Mathematical Systems Science and its Applications : IEICE technical report, 113, 279, 15-22, Japanese, 0913-5685, 110009886659, AA12529664 - Efficient Construction of BDDs from CNFs
戸田貴久
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., Information Processing Society of Japan (IPSJ), 30 Oct. 2013, IPSJ SIG Notes, 2013, 3, 1-8, Japanese, 0913-5685, 110009614883, AN1009593X - Three-way Indexing ZDDs for Large Scale Sparse Dataset
AOKI Hiroshi; TODA Takahisa; MINATO Shin-ichi
ZDDs are a data structure for 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 have unbalanced form and fall into the deterioration of performance. In this paper, we propose a new data structure three-way indexing ZDD, which is a variant of ZDDs. We furthermore present conversion algorithms between three-way indexing ZDDs and usual ZDDs. Experimental results show the effectiveness of our data structure and algorithms., The Institute of Electronics, Information and Communication Engineers, 11 Oct. 2013, IEICE technical report. Theoretical foundations of Computing, 113, 252, 1-8, Japanese, 110009820599, AN10013152
Books and other publications
Lectures, oral presentations, etc.
- SMTソルバーのAPIファザーMurxlaのカバレッジ改善に向けて, 第27回プログラミングおよびプログラミング言語ワークショップ
久保 拓巳; 戸田 貴久
Poster presentation, 第27回プログラミングおよびプログラミング言語ワークショップ
07 Mar. 2025 - 単位伝播で決定可能な補問題の拡張CNF表現に関する検討
戸田 貴久
Oral presentation, コンピュテーション研究会
07 Mar. 2025 - 検証ベースの公平性テスト技術の近似性能に関する考察
趙 振江; 戸田 貴久; 北村 崇師
Poster presentation, ソフトウェア工学の基礎ワークショップ
29 Nov. 2024 - 制約求解を用いない検証ベースの公平性テスト技術
趙 振江; 戸田 貴久; 北村 崇師
Poster presentation, 第27回情報論的学習理論ワークショップ
06 Nov. 2024 - 決定木ベースモデルへのロバスト性の検証技術を利用したブラックボックス手法の検討
久保 拓巳; 戸田 貴久
Poster presentation, 第27回情報論的学習理論ワークショップ
06 Nov. 2024 - 多様性を重視した公平性テスト技術とその多様性の考察
趙 振江; 戸田 貴久; 北村 崇師
Poster presentation, 第３０回ソフトウェア工学の基礎ワークショップ
10 Nov. 2023
09 Nov. 2023- 11 Nov. 2023 - だます人狼知能エージェントに関する初期的な考察
八木 啓至; 戸田 貴久
Oral presentation, 第49回ゲーム情報学研究発表会
18 Mar. 2023
17 Mar. 2023- 18 Mar. 2023 - Logical Approach to Testing and Verification of Machine Learning Models
Takahisa Toda
Invited oral presentation, 人工知能学会 第124回人工知能基本問題研究会, Invited
17 Mar. 2023
17 Mar. 2023- 17 Mar. 2023 - 決定的従属関係の含まれるベイジアンネットワークの近似推論手法に関する考察
中島祐輝; 戸田貴久
Oral presentation, 情報処理学会 第85回全国大会
04 Mar. 2023
02 Mar. 2023- 04 Mar. 2023 - ナイーブベイズ分類器におけるデルタ公平性
戸田貴久
Oral presentation, ウィンターワークショップ2023
21 Jan. 2023
20 Jan. 2023- 21 Jan. 2023 - 機械学習モデルの公平性のテスト手法
趙 振江; 戸田 貴久; 北村 崇師
Oral presentation, 第64回 プログラミング・シンポジウム 2023
06 Jan. 2023
06 Jan. 2023- 08 Jan. 2023 - 制約最適化に基づく画像の時間順並び替え
久保 拓巳; 戸田 貴久; 古賀 久志
Oral presentation, 第141回数理モデル化と問題解決研究発表会
12 Dec. 2022
12 Dec. 2022- 13 Dec. 2022 - 機械学習モデルの公平性テスト手法VBT-Xと今後の展望
趙 振江; 戸田 貴久; 北村 崇師
Poster presentation, 情報論的学習理論ワークショップ
22 Nov. 2022
20 Nov. 2022- 23 Nov. 2022 - ハッシュベースサンプリングによる効率的な公平性テスト
趙 振江; 戸田 貴久; 北村 崇師
Poster presentation, ソフトウェア工学の基礎ワークショップ
12 Nov. 2022
10 Nov. 2022- 12 Nov. 2022 - 類似学習節に基づくCDCLソルバーの高速化
趙 振江; 戸田 貴久
Oral presentation, Japanese, 第36回人工知能学会全国大会, 京都, Domestic conference
17 Jun. 2022 - 不確実性下における複合イベントの確率推定システムの開発
戸田 貴久; 夏 涛; 中島 祐輝; 八木 啓至
Poster presentation, Japanese, 第36回人工知能学会全国大会, 京都, Domestic conference
16 Jun. 2022 - 属性間依存度を考慮したデータベースの安全なフラグメント化
磯田 飛鳥; 戸田 貴久
Oral presentation, Japanese, 第14回データ工学と情報マネジメントに関するフォーラム, 情報処理学会, オンライン, Domestic conference
01 Mar. 2022 - 有界モデル検査による独立集合遷移問題の解法に関する考察
戸田 貴久; 伊藤 健洋; 川原 純; 宋 剛秀; 鈴木 顕; 照山 順一
Oral presentation, Japanese, 第186回アルゴリズム研究発表会, 情報処理学会, オンライン, Domestic conference
28 Jan. 2022 - 不確実性下における複合イベント処理に関する考察
夏 涛; 戸田 貴久
Oral presentation, Japanese, 第186回アルゴリズム研究発表会, 情報処理学会, オンライン, Domestic conference
28 Jan. 2022 - 命題論理式の解の一様サンプリングの改善
中島 祐輝; 戸田 貴久
Oral presentation, Japanese, 第20回情報科学技術フォーラム, オンライン, Domestic conference
27 Aug. 2021 - SATフィルターの検討
戸田貴久
Oral presentation, Japanese, 基盤(S) 離散構造処理系プロジェクト「2019年度 秋のワークショップ」, 北海道千歳市, Domestic conference
06 Nov. 2019 - SATサンプリングとその周辺
戸田貴久
Oral presentation, Japanese, 基盤(S) 離散構造処理系プロジェクト「短期滞在セミナー週間 (SSSW) 2019.09」, 北海道札幌市, Domestic conference
18 Sep. 2019 - 制約言語の観点におけるCP4IMの複雑さ
戸田貴久
Poster presentation, Japanese, 基盤(S) 離散構造処理系プロジェクト「2019年度 初夏のワークショップ」, 北海道札幌市, Domestic conference
28 Jun. 2019 - 交差回避制約によるSAT型ナンバーリンクソルバーの高速化
渡辺光洋; 戸田貴久
Oral presentation, Japanese, 第１０８回人工知能基本問題研究会, 人工知能学会, 長崎県長崎市, Domestic conference
14 Mar. 2019 - モデル検査における反例空間の構造解析
戸田貴久
Oral presentation, Japanese, 人工知能学会 第107回人工知能基本問題研究会(SIG-FPAI), Domestic conference
Aug. 2018 - ユークリッド距離に基づく多観点非類似度とその分割最適化クラスタリングへの応用
藤原勇二; 古賀久志; 戸田貴久
Oral presentation, Japanese, 人工知能学会 第106回人工知能基本問題研究会(SIG-FPAI), Domestic conference
Mar. 2018 - 共通要素を類似度とするハッシュベース集合間類似検索手法の改善
鈴木 聡; 古賀 久志; Gibran FUENTES; PINEDA Gibran; 戸田 貴久
Oral presentation, Japanese, 第10回データ工学と情報マネジメントに関するフォーラム(DEIM2018)
Mar. 2018 - 多観点類似度を用いた凝集型階層クラスタリング
藤原勇二; 古賀久志; 戸田貴久
Oral presentation, Japanese, 第16回情報科学技術フォーラム, Domestic conference
Sep. 2017 - モデル検査における反例発見から反例列挙への拡張
戸田貴久
Oral presentation, Japanese, 基盤(S) 離散構造処理系プロジェクト「2017年度 初夏のワークショップ」, 北海道札幌市, Domestic conference
Jun. 2017 - 集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム
山崎智博; 古賀久志; 戸田貴久
Oral presentation, Japanese, 信学技報, Domestic conference
May 2017 - 命題論理式を充足する変数割当の網羅的探索手法について
戸田貴久
Invited oral presentation, Japanese, 人工知能学会 第103回人工知能基本問題研究会(SIG-FPAI), Invited, 人工知能学会, 大分県由布市, Domestic conference
Mar. 2017 - 効率的なAllSATソルバーの実装と評価
戸田貴久; 宋剛秀
Oral presentation, Japanese, 第19回プログラミングおよびプログラミング言語ワークショップ（PPL2017）, 山梨県笛吹市, Domestic conference
Mar. 2017 - 命題論理式を充足する変数割当の網羅的探索手法について
戸田貴久
Invited oral presentation, Japanese, 人工知能学会 第103回人工知能基本問題研究会(SIG-FPAI), Invited, Domestic conference
Mar. 2017 - 擬似ブール制約を解く
戸田貴久
Poster presentation, Japanese, 情報系WINTER FESTA Episode2, 河原林ERATOプロジェクト, 東京, Domestic conference
Dec. 2016 - 擬似ブール制約を解く
戸田貴久
Oral presentation, Japanese, 基盤(S) 離散構造処理系プロジェクト「2016年度 秋のワークショップ」, 基盤(S) 離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
Nov. 2016 - AllSATにおける変数従属関係
戸田貴久; 井上武
Poster presentation, Japanese, 基盤(S) 離散構造処理系プロジェクト「2016年度 初夏のワークショップ」, 基盤(S) 離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
Jun. 2016 - 変数間の支配関係に基づく論理式の全解列挙手法
戸田貴久; 井上武
Oral presentation, Japanese, 第30回人工知能学会全国大会, 福岡県北九州市, Domestic conference
Jun. 2016 - 適応的に類似度を選択する類似画像検索方式
小林 馨; 古賀久志; 戸田貴久
Oral presentation, Japanese, 電子情報通信学会総合大会, Domestic conference
2016 - 部分構造の類似性を考慮したMin-Hashベースのグラフ類似検索
宮田昂充; 古賀久志; 戸田貴久
Oral presentation, Japanese, 電子情報通信学会総合大会, Domestic conference
2016 - 共通要素数を重視したハッシュベース集合間類似検索
板橋 大樹; 古賀 久志; Gibran Fuentes Pineda GIBRAN; 戸田 貴久
Oral presentation, Japanese, 第8回データ工学と情報マネジメントに関するフォーラム(DEIM2016), Domestic conference
2016 - 全解列挙型SATソルバー
戸田貴久
Poster presentation, Japanese, 情報系WINTER FESTA, Domestic conference
22 Dec. 2015 - AllSATソルバの最近の進展
戸田貴久
Oral presentation, Japanese, Genome Privacy CREST セミナートーク, Domestic conference
Nov. 2015 - Itemset Mining Using BDD-based ALLSAT Solvers
Takahisa Toda
Oral presentation, Japanese, 第29回人工知能学会全国大会, 2H4-OS-03a-3in, Domestic conference
May 2015 - BDDを用いたALLSATの枠組みとパターンマイニングへの応用
戸田貴久
Public discourse, Japanese, Invited, IBM 東京基礎研究所, IBM 東京基礎研究所
09 Apr. 2015 - ハイパーグラフにおける極大独立集合列挙のためのZDD構築手法
菅谷輝治
Oral presentation, Japanese, 電子情報通信学会 コンピュテーション研究会, Domestic conference
09 Mar. 2015 - ALLSATのためのBDD構築および効率的なキャッシング技法
戸田貴久
Oral presentation, Japanese, 人工知能学会 第97回人工知能基本問題研究会(SIG-FPAI), Domestic conference
Mar. 2015 - All Solutions SAT, BDD Compilation and Pattern Mining
Takahisa Toda
Poster presentation, English, JST ERATO Kawarabayashi Large Graph Project / Minato Discrete Structure Manipulation System Project Joint Workshop
Jan. 2015 - 2段階グラフカットを用いた動画からの移動物体抽出
土田和生; 古賀久志; 戸田貴久
Oral presentation, Japanese, 情報処理学会 コンピュータビジョンとイメージメディア研究会, Domestic conference
2015 - Efficient Caching Mechanism in BDD Compilation
Takahisa Toda
Oral presentation, English, ERATO-ALSIP Special Seminar 2014, International conference
13 Dec. 2014 - Dualization Using Decision Diagrams and Its Application for Itemset Mining
Takahisa Toda
Invited oral presentation, English, Decision Diagrams in Optimization I, INFORMS2014, Invited, International conference
10 Nov. 2014 - DPLL型BDD構築法の改善
戸田貴久
Oral presentation, Japanese, ２０１４年度秋のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道礼文島, Domestic conference
Sep. 2014 - サイクル描画について
戸田貴久
Public discourse, Japanese, 第20回列挙アルゴリズムセミナー, 群馬県渋川市, Domestic conference
Sep. 2014 - SATソルバーを用いたBDD構築法
戸田貴久
Oral presentation, Japanese, 第5回CSPSAT2研究会, 兵庫県神戸市, Domestic conference
21 Aug. 2014 - Generating Permutations under Pattern Occurence Constraints Using PiDDs
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
Oral presentation, English, The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery, in conjunction with PAKDD 2014, Tainan, Taiwan, International conference
13 May 2014 - A General Framework for Parallel Unary Operations on ZDDs
Shogo Takeuchi; Takahisa Toda; Shin-ichi Minato
Oral presentation, English, The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery, in conjunction with PAKDD 2014, Tainan, Taiwan, International conference
13 May 2014 - Three-way Indexing ZDDs for Large-scale Sparse Datasets
Hiroki Aoki; Takahisa Toda; Shin-ichi Minato
Oral presentation, English, The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery, in conjunction with PAKDD 2014, Tainan, Taiwan, International conference
13 May 2014 - 乗法標準形で与えられた論理関数に対する二分決定グラフ構築の効率化
岩下洋哲; 戸田貴久; 津田 宏治; 湊真一
Oral presentation, Japanese, 第28回人工知能学会全国大会, 人工知能学会, 愛媛県松山市, Domestic conference
12 May 2014 - メモリ階層を考慮したBDD演算とその並列化
戸田貴久
Poster presentation, Japanese, ２０１４年度春のワークショップ, ERATO湊離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
19 Apr. 2014 - ZDDにおける単項演算並列化の一般的枠組みの提案
竹内聖悟; 戸田貴久; 津田宏治; 湊真一
Oral presentation, Japanese, 第９２回人工知能基本問題研究会, 北海道函館市, Domestic conference
31 Jan. 2014 - 圧縮性に基づくパターン認識手法における特徴空間の改善
中島優次; 古賀久志; 戸田貴久
Oral presentation, Japanese, 電子情報通信学会 パターン認識・メディア理解研究会, Domestic conference
2014 - Twitterを利用した時事イベントとローカルイベントの同時検出
尾久陽平; 古賀久志; 戸田貴久
Oral presentation, Japanese, 電子情報通信学会 パターン認識・メディア理解研究会, Domestic conference
2014 - 論理関数のCNFからBDDの効率的な構築法
戸田貴久
Oral presentation, Japanese, ２０１３年度秋のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道登別市, Domestic conference
Nov. 2013 - 論理関数のCNFからBDDの効率的な構築法
戸田貴久
Oral presentation, Japanese, 第１４５回アルゴリズム研究会, 情報処理学会研究回報告, 情報処理学会, 岩手県花巻市, Domestic conference
30 Oct. 2013 - 巨大で疎な組合せ集合を表現するための三分索引化ZDD
青木洋士; 戸田貴久; 湊真一
Oral presentation, Japanese, コンピューテーション研究会、信学技報, 電子情報通信学会, 愛知県名古屋市, Domestic conference
Oct. 2013 - 二分決定グラフに基づくハイパーグラフ極小横断の列挙
戸田貴久
Poster presentation, Japanese, 第12回情報科学技術フォーラム, 電子情報通信学会 情報処理学会, 鳥取県鳥取市, Domestic conference
Sep. 2013 - 二分決定グラフに基づく大規模ハイパーグラフの双対化
戸田貴久
Oral presentation, Japanese, 第3回CSPSAT2研究会, 北海道札幌市, Domestic conference
26 Jul. 2013 - Efficiently generating classical and vincular pattern avoiding permutations based on permutation decision diagrams
Yuma Inoue; Takahisa Toda; Shin-ichi Minato
Oral presentation, English, Permutation Patterns 2013, Paris, France, International conference
04 Jul. 2013 - 二分決定グラフに基づく極小横断の列挙
戸田貴久
Public discourse, Japanese, 組合せ数学セミナー, 東京都目黒区, Domestic conference
Jul. 2013 - 二分決定グラフに基づくハイパーグラフ極小横断の列挙
戸田貴久
Poster presentation, Japanese, ２０１３年度初夏のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市
Jun. 2013 - 三分木によるZDDのパス長の均一化手法
青木洋士; 戸田貴久; 湊真一
Poster presentation, Japanese, ２０１３年度初夏のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
Jun. 2013 - 二分決定グラフに基づく大規模ハイパーグラフの双対化とその応用
戸田貴久; 湊真一
Oral presentation, Japanese, ２０１３年度人工知能学会全国大会（第27回）, 人工知能学会, 富山県富山市, Domestic conference
Jun. 2013 - 大規模ハイパーグラフからZDDの高速な構築アルゴリズム
戸田貴久
Oral presentation, Japanese, アルゴリズム研究会, 情報処理学会, 北海道小樽市, Domestic conference
May 2013 - ２分決定グラフに基づくハイパーグラフ双対化
戸田貴久
Public discourse, Japanese, 第17回列挙アルゴリズムセミナー, 群馬県渋川市, Domestic conference
Apr. 2013 - 順列二分決定グラフを用いたパターン回避順列の列挙索引化
井上祐馬; 戸田貴久; 湊真一
Oral presentation, Japanese, アルゴリズム研究会、情処研報, 情報処理学会, 福島県福島市, Domestic conference
Mar. 2013 - On Separating Convex Points with Lines
戸田貴久; Ivo Vigan
Oral presentation, Japanese, ERATOセミナー, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
Nov. 2012 - 二分決定グラフを用いたフロアプランの解析に向けて
戸田貴久
Oral presentation, Japanese, ２０１２年度秋のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道夕張市, Domestic conference
Oct. 2012 - 二分決定グラフから変数同等関係の抽出
戸田貴久
Poster presentation, Japanese, ２０１２年度初夏のワークショップ, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
Jun. 2012 - ２分割のなす分離族の数え上げ
戸田貴久; Ivo Vigan
Oral presentation, Japanese, 2011年度冬のLAシンポジウム予稿集, 京都府京都市, Domestic conference
Jan. 2012 - ２分割のなす分離族おん数え上げ
戸田貴久; Ivo Vigan
Oral presentation, Japanese, ERATOセミナー, JST ERATO湊離散構造処理系プロジェクト, 北海道札幌市, Domestic conference
26 Dec. 2011 - 集合を粉砕する二分割の集まりはいくつあるか？
戸田貴久; Ivo Vigan
Poster presentation, Japanese, 列挙学校, 神奈川県三浦郡湘南国際村センター, Domestic conference
Sep. 2011 - On Partitioning Colored Points
Takahisa Toda
Poster presentation, English, Kyoto Prize Satellite Workshop in Honor of Professor Laszlo Lovasz, 国立情報学研究所 東工大グローバルCOE「計算世界観の深化と展開」, 東工大蔵前会館（東京工業大学大岡山キャンパス）, Domestic conference
Nov. 2010 - 色付きの点の集まりはいつ超平面によりその色付け通りに分割できるか？
戸田貴久
Oral presentation, Japanese, 第21回代数、論理、幾何と情報科学研究集会, 滋賀県草津市
Sep. 2010 - 色付きの点の集まりはいつ超平面によりその色付け通りに分割できるか？
戸田貴久
Oral presentation, Japanese, 2010年度夏のLAシンポジウム予稿集, 富山県氷見市, Domestic conference
Jul. 2010 - Multi-convex sets in real projective spaces and their duality
Takahisa Toda
Oral presentation, English, Third Texas Southmost Geometry and Topology Conference, Texas, USA, International conference
Apr. 2010 - 与えられたどの凸多角形にも交差しない直線全体を構成するアルゴリズム
戸田貴久
Oral presentation, Japanese, 2009年度冬のLAシンポジウム予稿集, 京都府京都市, Domestic conference
Feb. 2010 - What is a Convex Set in a Real Projective Space? - An Interesting Helly-type Theorem -
Takahisa Toda
Poster presentation, English, Combinatorics: Methods and Applications in Mathematics and Computer Science, Workshop II: Combinatorial Geometry, California, USA, International conference
Oct. 2009 - Domain-theoretical aspects of convex sets in real projective space
Takahisa Toda
Oral presentation, English, Continuity, Computability, Constructivity: From Logic to Algorithms, Koln/Cologne, Germany, International conference
Jul. 2009
Courses
- Computer Literacy
Apr. 2022 - Present
The University of Electro-Communications - Fundamental Programming
Apr. 2022 - Present
The University of Electro-Communications - 計算数理
Apr. 2020 - Present
工学院大学 - 計算量の理論
Apr. 2019 - Present
法政大学 - Information Engineering Laboratory
Apr. 2024 - Mar. 2025
The University of Electro-Communications - 三大学協働基礎ゼミ
2025 - 2025 - Information Engineering Laboratory
Apr. 2022 - Mar. 2023
The University of Electro-Communications - Fundamental Programming
Apr. 2016 - Mar. 2022
The University of Electro-Communications - Seminar
Apr. 2020 - Mar. 2021
The University of Electro-Communications - Graduate Technical English
Apr. 2018 - Mar. 2020
The University of Electro-Communications - Computer Science Laboratory II
Apr. 2019
The University of Electro-Communications - 情報システム基盤学基礎１
Apr. 2014 - Mar. 2016
電気通信大学 - 数理科学特論I
Oct. 2015 - Oct. 2015
京都大学 - 情報システム基盤学基礎２
電気通信大学
Research Themes
- Engineering Approach for Expanding Combinatorial Reconfiguration: Toward a General-Purpose Solver Using Power Distribution Systems as a Steppingstone
川原 純; 飯岡 大輔; 戸田 貴久; 宋 剛秀; 鈴木 顕; 照山 順一; 中畑 裕
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (B), Kyoto University, Grant-in-Aid for Transformative Research Areas (B), 本研究では組合せ遷移の実装技術の構築とその産業応用に向けて、研究開発の共通基盤となるソフトウェア開発を目標とする。初年度にあたる本年度は、広く知られているグラフの独立集合の遷移問題（独立集合遷移問題）に対して、4種のアプローチを検討した。1つ目は、組合せ遷移の技法を用いたアルゴリズムの設計であり、主に、状態空間の部分探索の手法を検討した。2つ目は、SAT（充足可能性問題）ソルバーを活用するアプローチである。有限整数領域上の制約を命題論理式へと変換する SAT 符号化を行い、SATソルバーの強力な推論性能を用いて独立集合遷移問題を解くソルバーを開発した。3つ目は、ゼロサプレス型二分決定グラフ (ZDD) を活用するアプローチである。当初予定では、ZDD を上記2手法に援用した高速化を想定していたが、本研究において、ZDD が表す独立集合族を直接遷移させるアルゴリズムの開発に成功したため、ZDD を単独で用いて独立集合遷移問題を解くことが可能になった。4つ目の手法は、当初は予定していない新たな構想であるが、モデル検査と呼ばれる、システムの形式的な検査を可能にする技術を用いた手法である。入力グラフと開始、目標独立集合が与えられた際に、開始集合から目標集合に遷移可能ではないことを検証する記述をモデル検査ソルバーに与え、遷移可能な場合は反例として解となる遷移列を出力する。 以上の4つの技法について、アルゴリズム設計と実装を行った。アルゴリズムの比較実験のためには、適切な入力データが必要であるが、組合せ遷移問題に対する広く知られたベンチマークデータは存在しないため、入力データの作成整備を行った。 配電切替への組合せ遷移技術の適用についても研究を行い、配電切替を全域木遷移問題として定式化し、4つの技法の適用を検討して、実装を行っている。, 20H05794
Oct. 2020 - Mar. 2023 - Development of Practical Techniques for All Soltuion Enumeration of Large-scale Constraint Satisfaction Problems
Toda Takahisa
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B), The University of Electro-Communications, Grant-in-Aid for Young Scientists (B), In this research, we developed an efficient method for computationally hard problems that intrinsically require us to enumerate all solutions of constraint satisfaction problems (CSPs). As a major achievement, we developed a computer-aided method to help us to locate faults in the designs of hardware and software. Model checking is a widely applied method for the verification and debugging of information systems. A counterexample is detected from an erroneous system as a proof of error by executing model checking, however, there is a big gap between computing counterexamples and locating faults. We thus proposed a method for providing information regarding error in a more understandable form than counterexamples by abstracting many counterexamples, which is expected to aid us in moving a trace of failure (i.e., a counterexample) to an understanding of the essence of the failure. Beside the model checking application, we tackled security/privacy-related researches., 17K17725
Apr. 2017 - Mar. 2022 - A Large-scale Enumeration of Minimal Hitting Sets And Its Application to Knowledge Discovery
Toda Takahisa
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B), The University of Electro-Communications, Grant-in-Aid for Young Scientists (B), This research project developed practically efficient methods for the following important problems: the minimal hitting set enumeration problem and extended problems such as the dualization of Boolean functions and the all solutions SAT problem.Not only novel methods proposed in this research, but also most major methods proposed before were implemented as public software, and their efficiency and characteristics were confirmed through comprehensive experiments.These results and software are publicly available on our website. Toward applications to knowledge discovery, our software was applied to itemset mining problems based on the so-called declarative approach in data mining, and experiments using actual data taken from transaction databases were conducted, by which promising research problems in this approach and useful knowledge were obtained., 26870011
Apr. 2014 - Mar. 2018 - 組合せ最適化の研究助成
戸田 貴久
株式会社富士通研究所, 研究助成, Principal investigator
Oct. 2017 - 組合せ最適化の研究助成
戸田 貴久
株式会社富士通研究所, 研究助成, Principal investigator
Oct. 2016
