Tatsuie Tsukiji

According to our database, Tatsuie Tsukiji authored at least 19 papers between 1996 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits.

Tatsuie Tsukiji

Electron. Colloquium Comput. Complex., 2021

EXPTIME Hardness of an n by n Custodian Capture Game.

Fumitaka Ito, Masahiko Naito, Naoyuki Katabami, Tatsuie Tsukiji

Algorithms, 2021

2020

Hardness of Approximation for Langton's Ant on a Twisted Torus.

Takeo Hagiwara, Tatsuie Tsukiji

Algorithms, 2020

2016

Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata.

Takeo Hagiwara, Tatsuie Tsukiji, Zhi-Zhong Chen

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2016

Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications.

Zhi-Zhong Chen, Tatsuie Tsukiji, Hiroki Yamada

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2016

2011

Recognizing the Repeatable Configurations of Time-Reversible Generalized Langton's Ant Is PSPACE-Hard.

Tatsuie Tsukiji, Takeo Hagiwara

Algorithms, 2011

2006

Computing phylogenetic roots with bounded degrees and errors is NP-complete.

Tatsuie Tsukiji, Zhi-Zhong Chen

Theor. Comput. Sci., 2006

Computing bounded-degree phylogenetic roots of disconnected graphs.

Zhi-Zhong Chen, Tatsuie Tsukiji

J. Algorithms, 2006

Approximated Vertex Cover for Graphs with Perfect Matchings.

Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji

IEICE Trans. Inf. Syst., 2006

2004

Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees.

Hosam M. Mahmoud, Tatsuie Tsukiji

Acta Informatica, 2004

Computing Phylogenetic Roots with Bounded Degrees and Errors Is Hard.

Tatsuie Tsukiji, Zhi-Zhong Chen

Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

2002

Learning of Short Boolean Conjunctions from Negative Examples.

Tatsuie Tsukiji, Takashi Tokutani

Syst. Comput. Jpn., 2002

2001

A Limit Law for Outputs in Random Recursive Circuits.

Tatsuie Tsukiji, Hosam M. Mahmoud

Algorithmica, 2001

2000

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2000

1999

Learning DNF by Approximating Inclusion-Exclusion Formulae.

Jun Tarui, Tatsuie Tsukiji

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Finding Relevant Variables in PAC Model with Membership Queries.

David Guijarro, Jun Tarui, Tatsuie Tsukiji

Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1997

Partial Occam's Razor and its Applications.

Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe

Inf. Process. Lett., 1997

1996

On a Small Class of Boolean Sums.

Tatsuie Tsukiji

Theor. Comput. Sci., 1996

On the Depth of Randomly Generated Circuits.

Tatsuie Tsukiji, Fatos Xhafa

Proceedings of the Algorithms, 1996