Professor of Computer Science
---- In P or not in P, That is the question.
Second Edition, 2014.
Computational Complexity Theory
- K. Ko, T. Long and D. Du, On one-way functions and polynomial-time isomorphisms, Theoretical Computer Science, 47 (1986) 263-276.
- K. Ko, Relativized polynomial time hierarchies having exactly K levels, SIAM Journal on Computing, 18 (1989), 392-408.
- P. Orponen, K. Ko, U. Schoening and O. Watanabe, Instance complexity, Journal of Association for Computing Machinery, 41 (1994), 96-121.
Complexity Theory of Real Functions
- K. Ko and H. Friedman, Computational complexity of real functions, Theoretical Computer Science, 20 (1982), 323-352.
- K. Ko and K. Weihrauch, On the measure of two-dimensional regions with polynomial-time computable boundaries, in "Proceedings of IEEE 11th Conference on Computational Complexity," IEEE, 1996, 150-159.
- A. Chou and K. Ko, On the complexity of finding paths in a two-dimensional domain I: shortest paths, Math. Logic Quarterly, 50 (2004), 551-572.
- D. Du and K. Ko, Some completeness results on decision trees and group testing, SIAM Journal on Algebraic and Discrete Methods, 8 (1987), 762-777.
- K. Ko, Searching for two objects by underweight feedbacks, SIAM Journal on Discrete Mathematics, 1 (1988), 65-70.
- K. Ko and C.-L. Lin, On the complexity of min-max optimization problems and their approximation, in "Minimax and Applications", D.-Z. Du and P.M. Pardalos, Eds, Kluwer, 1995, 219-239.
- K. Ko and C.-L. Lin, On the longest circuit in an alterable digraph, Journal of Global Optimization, 7 (1995), 279-295.
Computational Learning Theory
- K. Ko, A. Marron and W.-G. Tzeng, Learning string patterns and tree patterns from examples, Proceedings of the 7th International Conference on Machine Learning, Morgan Kaufmann, 1990, 384-391.
- K. Ko, On the complexity of learning minimum time-bounded Turing machines, Proceedings of the 3rd Workshop on Computational Learning Theory, Morgan Kaufman, 1990, 82-96.
Department of Computer Science
National Chiao Tung University
kyko [at] cs. nctu. edu. tw
(03)5712121 ext 56662
窄巷 台灣商務印書館, 2004.