Tatsuie Tsukiji

Publication Activity (10 Years)

Years Active: 1996-2021
Publications (10 Years): 5

Top Topics

Approximation Ratio

Computational Complexity

Cellular Automata

Top Venues

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

Electron. Colloquium Comput. Complex.

Publications

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