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

### Computational Complexity

---- 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, Theory of Computational Complexity, John Wiley and Sons, New York, NY, 2000. (Reviews) (Errata)
- 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.
**NEW!**D.-Z. Du, K. Ko and X. Hu, Design and Analysis of Approximation Algorithms, Springer Science+Business Media, New York, 2012.

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

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

- 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