[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

In Memoriam: Ker-I Ko (1950–2018)

  • Chapter
  • First Online:
Complexity and Approximation

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12000))

  • 943 Accesses

Abstract

Ker-I Ko was a colleague and a friend, and our friendships began from the mid 1980’s. Ker-I passed away peacefully due to lung failure on the 13th of December in 2018 at a hospital in New York, with his wife Mindy Pien and all three children by his side. His passing is a great loss to the theoretical computer science community.

Ker-I Ko is a talented scientist, novelist, and a warm, sincere long time friend. We will miss him profoundly.

Andrew Chi-Chih Yao

Turing Award recipient, 2000

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 43.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 54.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Chen, X., et al.: Centralized and decentralized rumor blocking problems. J. Comb. Optim. 34(1), 314–329 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  2. Li, W., Liu, W., Chen, T., Qu, X., Fang, Q., Ko, K.-I.: Competitive profit maximization in social networks. Theor. Comput. Sci. 694, 1–9 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ran, Y., Zhang, Z., Ko, K.-I., Liang, J.: An approximation algorithm for maximum weight budgeted connected set cover. J. Comb. Optim. 31(4), 1505–1517 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ko, K.-I.: On the complexity of computing the Hausdorff distance. J. Complex. 29(3–4), 248–262 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  5. Fuxiang, Y., Ko, K.-I.: On logarithmic-space computable real numbers. Theor. Comput. Sci. 469, 127–133 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fuxiang, Y., Ko, K.-I.: On parallel complexity of analytic functions. Theor. Comput. Sci. 489–490, 48–57 (2013)

    MathSciNet  MATH  Google Scholar 

  7. Bauer, A., Hertling, P., Ko, K.-I.: Computability and complexity in analysis. J. UCS 16(18), 2495 (2010)

    MathSciNet  Google Scholar 

  8. Cheng, Y., Ding-Zhu, D., Ko, K.-I., Lin, G.: On the parameterized complexity of pooling design. J. Comput. Biol. 16(11), 1529–1537 (2009)

    Article  MathSciNet  Google Scholar 

  9. Ko, K.-I., Fuxiang, Y.: On the complexity of convex hulls of subsets of the two-dimensional plane. Electr. Notes Theor. Comput. Sci. 202, 121–135 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cheng, Y., Ko, K.-I., Weili, W.: On the complexity of non-unique probe selection. Theor. Comput. Sci. 390(1), 120–125 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ko, K.-I., Fuxiang, Y.: Jordan curves with polynomial inverse moduli of continuity. Electr. Notes Theor. Comput. Sci. 167, 425–447 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  12. Ko, K.-I., Fuxiang, Y.: On the complexity of computing the logarithm and square root functions on a complex domain. J. Complex. 23(1), 2–24 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ko, K.-I., Weihrauch, K., Zheng, X.: Editorial: Math. Log. Quart. 4–5/2007. Math. Log. Q. 53(4–5), 325 (2007)

    Article  Google Scholar 

  14. Ko, K.-I., Fuxiang, Y.: Jordan curves with polynomial inverse moduli of continuity. Theor. Comput. Sci. 381(1–3), 148–161 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Brattka, V., Hertling, P., Ko, K.-I., Tsuiki, H.: Computability and complexity in analysis. J. Complex. 22(6), 728 (2006)

    Article  Google Scholar 

  16. Fuxiang, Y., Chou, A.W., Ko, K.-I.: On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain. J. Complex. 22(6), 803–817 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Chou, A.W., Ko, K.-I.: On the complexity of finding paths in a two-dimensional domain II: piecewise straight-line paths. Electr. Notes Theor. Comput. Sci. 120, 45–57 (2005)

    Article  MathSciNet  Google Scholar 

  18. Chou, A.W., Ko, K.-I.: The computational complexity of distance functions of two-dimensional domains. Theor. Comput. Sci. 337(1–3), 360–369 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  19. Brattka, V., Hertling, P., Ko, K.-I., Zhong, N.: Preface: MLQ - Math. Log. Quart. 4–5/2004. Math. Log. Q. 50(4–5), 327–328 (2004)

    Article  Google Scholar 

  20. Chou, A.W., Ko, K.-I.: On the complexity of finding paths in a two-dimensional domain I: shortest paths. Math. Log. Q. 50(6), 551–572 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ruan, L., Hongwei, D., Jia, X., Weili, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating sets. Theor. Comput. Sci. 329(1–3), 325–330 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  22. Ko, K.-I., Nerode, A., Weihrauch, K.: Foreword. Theor. Comput. Sci. 284(2), 197 (2002)

    Article  Google Scholar 

  23. Ko, K.-I.: On the computability of fractal dimensions and hausdorff measure. Ann. Pure Appl. Logic 93(1–3), 195–216 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ko, K.-I.: Computational complexity of fixed points and intersection points. J. Complex. 11(2), 265–292 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  25. Ko, K.-I., Lin, C.-L.: On the longest circuit in an alterable digraph. J. Glob. Optim. 7(3), 279–295 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  26. Chou, A.W.: Computational complexity of two-dimensional regions. SIAM J. Comput. 24(5), 923–947 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  27. Ko, K.-I.: A polynomial-time computable curve whose interior has a nonrecursive measure. Theor. Comput. Sci. 145(1&2), 241–270 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  28. Orponen, P., Ko, K.-I., Schöning, U., Watanabe, O.: Instance complexity. J. ACM 41(1), 96–121 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  29. Ko, K.-I.: On the computational complexity of integral equations. Ann. Pure Appl. Logic 58(3), 201–228 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  30. Ding-Zhu, D., Ko, K.-I.: A note on best fractions of a computable real number. J. Complex. 8(3), 216–229 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  31. Ko, K.-I., Tzeng, W.-G.: Three \(\Sigma ^p_2\)-complete problems in computational learning theory. Comput. Complex. 1, 269–310 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  32. Ko, K.-I.: Separating the low and high hierarchies by oracles. Inf. Comput. 90(2), 156–177 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  33. Ko, K.-I.: On the complexity of learning minimum time-bounded turing machines. SIAM J. Comput. 20(5), 962–986 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  34. Ko, K.-I.: On adaptive versus nonadaptive bounded query machines. Theor. Comput. Sci. 82(1), 51–69 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  35. Ko, K.-I.: A note on separating the relativized polynomial time hierarchy by immune sets. ITA 24, 229–240 (1990)

    MathSciNet  MATH  Google Scholar 

  36. Ko, K.-I.: Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy. J. ACM 37(2), 415–438 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  37. Ko, K.-I.: Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Inf. Comput. 81(1), 62–87 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  38. Ko, K.-I.: Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput. 18(2), 392–408 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  39. Du, D.-Z., Ko, K.-I.: On the complexity of an optimal routing tree problem. Acta Math. Appl. Sinica (Engl. Ser.) 5, 68–80 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  40. Du, D.-Z., Ko, K.-I.: Complexity of continuous problems on convex functions. Syst. Sci. Math. 2, 70–79 (1989)

    MATH  Google Scholar 

  41. Book, R.V., Ko, K.-I.: On sets truth-table reducible to sparse sets. SIAM J. Comput. 17(5), 903–919 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  42. Ko, K.-I.: Searching for two objects by underweight feedback. SIAM J. Discrete Math. 1(1), 65–70 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  43. Marron, A., Ko, K.-I.: Identification of pattern languages from examples and queries. Inf. Comput. 74(2), 91–112 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  44. Du, D., Ko, K.: Some completeness results on decision trees and group testing. SIAM J. Algebraic Discrete Methods 8, 762–777 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  45. Ko, K.-I., Hua, C.-M.: A note on the two-variable pattern-finding problem. J. Comput. Syst. Sci. 34(1), 75–86 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  46. Ko, K.-I.: On helping by robust oracle machines. Theor. Comput. Sci. 52, 15–36 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  47. Ko, K.-I.: Corrigenda: on the continued fraction representation of computable real numbers. Theor. Comput. Sci. 54, 341–343 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  48. Ko, K.-I.: Approximation to measurable functions and its relation to probabilistic computation. Ann. Pure Appl. Logic 30(2), 173–200 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  49. Ko, K.-I., Teng, S.-C.: On the number of queries necessary to identify a permutation. J. Algorithms 7(4), 449–462 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  50. Ko, K.-I.: On the computational complexity of best Chebyshev approximations. J. Complex. 2(2), 95–120 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  51. Ko, K.-I., Long, T.J., Ding-Zhu, D.: On one-way functions and polynomial-time isomorphisms. Theor. Comput. Sci. 47(3), 263–276 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  52. Ko, K.-I.: On the continued fraction representation of computable real numbers. Theor. Comput. Sci. 47(3), 299–313 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  53. Ko, K.-I.: On the notion of infinite pseudorandom sequences. Theor. Comput. Sci. 48(3), 9–33 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  54. Ko, K.-I.: Continuous optimization problems and a polynomial hierarchy of real functions. J. Complex. 1(2), 210–231 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  55. Ko, K.-I.: Nonlevelable sets and immune sets in the accepting density hierarchy in NP. Math. Syst. Theory 18(3), 189–205 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  56. Ko, K.-I., Schöning, U.: On circuit-size complexity and the low hierarchy in NP. SIAM J. Comput. 14(1), 41–51 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  57. Ko, K.-I.: On some natural complete operators. Theor. Comput. Sci. 37, 1–30 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  58. Ko, K.-I.: Reducibilities on real numbers. Theor. Comput. Sci. 31, 101–123 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  59. Ko, K.-I.: On the computational complexity of ordinary differential equations. Inf. Control 58(1–3), 157–194 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  60. Ko, K.-I.: On self-reducibility and weak p-selectivity. J. Comput. Syst. Sci. 26(2), 209–221 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  61. Ko, K.-I.: On the definitions of some complexity classes of real numbers. Math. Syst. Theory 16(2), 95–109 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  62. Ko, K.-I.: Some negative results on the computational complexity of total variation and differentiation. Inf. Control 53(1/2), 21–31 (1982)

    MathSciNet  MATH  Google Scholar 

  63. Ko, K.-I.: Some observations on the probabilistic algorithms and NP-hard problems. Inf. Process. Lett. 14(1), 39–43 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  64. Ko, K.-I.: The maximum value problem and NP real numbers. J. Comput. Syst. Sci. 24(1), 15–35 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  65. Ko, K.-I., Friedman, H.: Computational complexity of real functions. Theor. Comput. Sci. 20, 323–352 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  66. Ko, K.-I., Moore, D.J.: Completeness, approximation and density. SIAM J. Comput. 10(4), 787–796 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  67. Bauer, A., Hertling, P., Ko, K.-I.: CCA 2009 front matter - proceedings of the sixth international conference on computability and complexity in analysis. In: CCA (2009)

    Google Scholar 

  68. Bauer, A., Hertling, P., Ko, K.-I.: CCA 2009 preface - proceedings of the sixth international conference on computability and complexity in analysis. In: CCA (2009)

    Google Scholar 

  69. Yu, F., Chou, A.W., Ko, K.-I.: On the complexity of finding circumscribed rectangles for a two-dimensional domain. In: CCA, pp. 341–355 (2005)

    Google Scholar 

  70. Ko, K.-I., Yu, F.: On the complexity of computing the logarithm and square root functions on a complex domain. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 349–358. Springer, Heidelberg (2005). https://doi.org/10.1007/11533719_36

    Chapter  MATH  Google Scholar 

  71. Ko, K.-I.: Fractals and complexity. In: CCA (1996)

    Google Scholar 

  72. Ko, K.-I., Weihrauch, K.: On the measure of two-dimensional regions with polynomial-time computables boundaries. In: Computational Complexity Conference, pp. 150–159 (1996)

    Google Scholar 

  73. Chou, A.W., Ko, K.-I.: Some complexity issues on the simply connected regions of the two-dimensional plane. In: STOC, pp. 1–10 (1993)

    Google Scholar 

  74. Ko, K.-I.: A note on the instance complexity of pseudorandom sets. In: Computational Complexity Conference, pp. 327–337 (1992)

    Google Scholar 

  75. Ko, K.-I.: Integral equations, systems of quadratic equations, and exponential-time completeness (extended abstract). In: STOC, pp. 10–20 (1991)

    Google Scholar 

  76. Ko, K.-I.: On the complexity of learning minimum time-bounded Turing machines. In: COLT, pp. 82–96 (1990)

    Google Scholar 

  77. Ko, K.-I., Marron, A., Tzeng, W.-G.: Learning string patterns and tree patterns from examples. In: ML, pp. 384–391 (1990)

    Google Scholar 

  78. Ko, K.-I.: Computational complexity of roots of real functions (extended abstract). In: FOCS, pp. 204–209 (1989)

    Google Scholar 

  79. Ko, K.-I.: Relativized polynomial time hierarchies having exactly K levels. In: Computational Complexity Conference (1988)

    Google Scholar 

  80. Ko, K.-I.: Distinguishing bounded reducibilities by sparse sets. In: Computational Complexity Conference, pp. 181–191 (1988)

    Google Scholar 

  81. Ko, K.-I: Relativized polynominal time hierarchies having exactly K levels. In: STOC, pp. 245–253 (1988)

    Google Scholar 

  82. Book, R.V., Ko, K.-I.: On sets reducible to sparse sets. In: Computational Complexity Conference (1987)

    Google Scholar 

  83. Ko, K.-I.: On helping by robust oracle machines. In: Computational Complexity Conference (1987)

    Google Scholar 

  84. Ko, K.-I., Orponen, P., Schöning, U., Watanabe, O.: What is a hard instance of a computational problem? In: Selman, A.L. (ed.) Structure in Complexity Theory. LNCS, vol. 223, pp. 197–217. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-16486-3_99

    Chapter  Google Scholar 

  85. Ko, K.-I, Long, T.J., Du, D.-Z.: A note on one-way functions and polynomial-time isomorphisms (extended abstract). In: STOC, pp. 295–303 (1986)

    Google Scholar 

  86. Ko, K.: Applying techniques of discrete complexity theory to numerical computation. In: Book, R. (ed.) Studies in Complexity Theory, pp. 1–62. Research Notes in Theoretical Computer Science, Pitman (1986)

    Google Scholar 

  87. Ko, K.: Constructing oracles by lower bound techniques for circuits. In: Du, D., Hu, G. (eds.) Combinatorics, Computing and Complexity, pp. 30–76. Kluwer Academic Publishers and Science Press, Boston (1989)

    Chapter  Google Scholar 

  88. Ko, K.: Polynomial-time computability in analysis. In: Ershov, Y.L., et al. (eds.) Handbook of Recursive Mathematics. Recursive Algebra, Analysis and Combinatorics, vol. 2, pp. 1271–1317 (1998)

    Google Scholar 

  89. Ko, K.: Computational complexity of fractals. In: Downey, R., et al. (eds.) Proceedings of the 7th and 8th Asian Logic Conferences, pp. 252–269. World Scientific, Singapore (2003)

    Google Scholar 

  90. Ko, K., Lin, C.-L.: On the complexity of min-max optimization problems and their approximation. In: Du, D.-Z., Pardalos, P.M. (eds.) Minimax and Applications, pp. 219–239. Kluwer (1995)

    Google Scholar 

  91. Du, D.-Z., Ko, K.-I., Hu, X.: Design and Analysis of Approximation Algorithms. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-1701-9

    Book  MATH  Google Scholar 

  92. Du, D.-Z., Ko, K., Hu, X.: Design and Analysis of Approximation Algorithms. Higher Education Press, Beijing (2011). (in Chinese)

    Google Scholar 

  93. Du, D.-Z., Ko, K., Wang, J.: Introduction to Computational Complexity. Higher Education Press, Beijing (2002). (in Chinese)

    Google Scholar 

  94. Du, D.-Z., Ko, K.: Problem Solving in Automata, Languages and Complexity. Wiley, New York (2001)

    Book  Google Scholar 

  95. Du, D.-Z., Ko, K.: Theory of Computational Complexity. Wiley, New York (2000)

    Book  MATH  Google Scholar 

  96. Du, D.-Z., Ko, K. (eds.): Advances in Algorithms, Languages, and Complexity. Kluwer, Dordrecht (1997)

    MATH  Google Scholar 

  97. Ko, K.: Computational Complexity of Real Functions. Birkhauser Boston, Boston (1991)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Texas at Dallas, Richardson, TX, 75080, USA

    Ding-Zhu Du

  2. University of Massachusetts, Lowell, MA, 01854, USA

    Jie Wang

Authors
  1. Ding-Zhu Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jie Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ding-Zhu Du .

Editor information

Editors and Affiliations

  1. The University of Texas at Dallas, Richardson, TX, USA

    Ding-Zhu Du

  2. University of Massachusetts Lowell, Lowell, MA, USA

    Jie Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Du, DZ., Wang, J. (2020). In Memoriam: Ker-I Ko (1950–2018). In: Du, DZ., Wang, J. (eds) Complexity and Approximation. Lecture Notes in Computer Science(), vol 12000. Springer, Cham. https://doi.org/10.1007/978-3-030-41672-0_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-41672-0_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-41671-3

  • Online ISBN: 978-3-030-41672-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation