Professor of Computer Science

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

- K. Ko, Computational Complexity
of Real Functions, Birkhauser Boston, Boston, MA, 1991. (Reviews)
- D.-Z. Du and K. Ko
(Editors), Advances in Algorithms, Languages, and Complexity, Kluwer,
Dordrecht, The Netherlands, 1997.
- D.-Z. Du and K. Ko, Problem Solving in
Automata, Languages and Complexity, John Wiley and Sons,
New York, NY, 2001. (Errata)
- D.-Z. Du, K. Ko and J. Wang, Introduction to
Computational Complexity (in Chinese), Higher Education
Press, Beijing, 2002.
- D.-Z. Du, K. Ko and X.
Hu, Design and Analysis of
Approximation Algorithms (in Chinese), Higher Education
Press, Beijing, 2011.
- D.-Z. Du, K. Ko and X.
Hu, Design and Analysis of
Approximation Algorithms, Springer
Science+Business Media, New York, 2012.
- D.-Z. Du and K. Ko, Theory of Computational
Complexity, John Wiley and Sons, New York,
NY, 2000. (Reviews) (Errata)

Second Edition, 2014.

- K. Ko, Applying
techniques of discrete complexity theory to numerical computation, in
"Studies in Complexity Theory," R. Book, Ed., Research Notes in
Theoretical Computer Science, Pitman, London, 1986, pp. 1-62.
- K. Ko, Constructing oracles by
lower bound techniques for circuits, in
"Combinatorics, Computing and Complexity," D. Du and G. Hu,
Eds., Kluwer Academic Publishers and Science Press, Boston, 1989, pp.
30-76.
- K. Ko, Polynomial-time
computability in analysis, in "Handbook of
Recursive Mathematics," Volume 2, Recursive Algebra, Analysis and
Combinatorics, Yu. L. Ershov et al., Eds., 1998, pp. 1271-1317. slides for the talk in
CCA 2010 (Polynomial-time computability in analysis: a survey,
Zhenjiang, China, June, 2010).
- K. Ko, Computational complexity
of fractals, in "Proceedings of the 7th and 8th Asian Logic
Conferences," R.~Downey et al., eds., World Scientific, Singapore,
2003, pp. 252-269.

## 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.
## Combinatorics

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

- Spring 2016

Computational Complexity

- ISI Highly Cited
Researcher, ISIHighlyCited.com,
Thomson Reuters.

Ker-I Ko

Department of Computer Science

National Chiao Tung University

Hsin-Chu, Taiwan

kyko [at] cs. nctu. edu. tw

(03)5712121 ext 56662

窄巷 台灣商務印書館, 2004.