Ker-I Ko

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

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

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.

Honors

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

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

Short Stories

Tian Liang Hao Ge Qiu

Ke Long Jia Qi

Zhai Xiang