Ker-I Ko

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

Research Interests

Computational Complexity

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

Books

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.

Survey Articles

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

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.

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.

Teaching

(Fall 2007-Spring 2008) I am visiting ITCS of Tsinghua University, Beijing, China, this year. Please check my Tsinghua page.

Journals

I am an associate editor of the following journal:

Journal of Complexity (You may send your submissions directly to me.)

Conferences

Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), August 21-24, 2008, Hagen, Germany.

Contact

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
(631)632-8460

Writing

My recent story