Ker-I Ko

Professor Emeritus
Computer Science
State University of New York at Stony Brook

My current affiliation

Department of Computer Science, National Chiao tung University, Hsinchu, Taiwan

Research Interests

Computational Complexity

---- In P or not in P, That is the question.


Survey Articles

Selected Research Papers

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.

Combinatorial Optimization

  • 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.



Ker-I Ko
Department of Computer Science
State University of New York at Stony Brook
Stony Brook, NY 11794-4400, USA
keriko [at] cs. sunysb. edu

Short Stories

Tao Wang Jia Zu

Tian Liang Hao Ge Qiu

Ke Long Jia Qi

Zhai Xiang