Tatsuie Tsukiji

24 papers A 3B 3Misc 2Journal 16
YearRankTypeTitle / Venue / Authors
2021 J jnl
EXPTIME Hardness of an n by n Custodian Capture Game.
Algorithms
Fumitaka Ito, Masahiko Naito, Naoyuki Katabami, Tatsuie Tsukiji
2021 J jnl
Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits.
Electron. Colloquium Comput. Complex.
Tatsuie Tsukiji
2020 J jnl
Hardness of Approximation for Langton's Ant on a Twisted Torus.
Algorithms
Takeo Hagiwara, Tatsuie Tsukiji
2016 J jnl
Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Takeo Hagiwara, Tatsuie Tsukiji, Zhi-Zhong Chen
2016 J jnl
Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Zhi-Zhong Chen, Tatsuie Tsukiji, Hiroki Yamada
2011 J jnl
Recognizing the Repeatable Configurations of Time-Reversible Generalized Langton's Ant Is PSPACE-Hard.
Algorithms
Tatsuie Tsukiji, Takeo Hagiwara
2006 J jnl
Approximated Vertex Cover for Graphs with Perfect Matchings.
IEICE Trans. Inf. Syst.
Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji
2006 J jnl
Computing bounded-degree phylogenetic roots of disconnected graphs.
J. Algorithms
Zhi-Zhong Chen, Tatsuie Tsukiji
2006 J jnl
Computing phylogenetic roots with bounded degrees and errors is NP-complete.
Theor. Comput. Sci.
Tatsuie Tsukiji, Zhi-Zhong Chen
2004 Misc conf
Approximated Vertex Cover for Graphs with Perfect Matchings.
COCOON
Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji
2004 B conf
Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs.
WG
Zhi-Zhong Chen, Tatsuie Tsukiji
2004 Misc conf
Computing Phylogenetic Roots with Bounded Degrees and Errors Is Hard.
COCOON
Tatsuie Tsukiji, Zhi-Zhong Chen
2004 J jnl
Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees.
Acta Informatica
Hosam M. Mahmoud, Tatsuie Tsukiji
2002 J jnl
Learning of Short Boolean Conjunctions from Negative Examples.
Syst. Comput. Jpn.
Tatsuie Tsukiji, Takashi Tokutani
2002 J jnl
The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
Theory Comput. Syst.
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
2001 J jnl
A Limit Law for Outputs in Random Recursive Circuits.
Algorithmica
Tatsuie Tsukiji, Hosam M. Mahmoud
2001 A conf
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
STACS
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
2000 J jnl
On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems
Electron. Colloquium Comput. Complex.
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
1999 B conf
Finding Relevant Variables in PAC Model with Membership Queries.
ALT
David Guijarro, Jun Tarui, Tatsuie Tsukiji
1999 A conf
Learning DNF by Approximating Inclusion-Exclusion Formulae.
CCC
Jun Tarui, Tatsuie Tsukiji
1997 B conf
Partial Occam's Razor and Its Applications.
ALT
Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe
1997 J jnl
Partial Occam's Razor and its Applications.
Inf. Process. Lett.
Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe
1996 J jnl
On a Small Class of Boolean Sums.
Theor. Comput. Sci.
Tatsuie Tsukiji
1996 A conf
On the Depth of Randomly Generated Circuits.
ESA
Tatsuie Tsukiji, Fatos Xhafa