Wednesday, December 26, 2018

Ker-I Ko (1950-2018)

A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least none that we were aware of. Unfortunately we didn't make it through all of 2018 unscathed.

Computational complexity theorist Ker-I Ko passed away peacefully from lung failure on December 13. Ker-I Ko spent most of his career at Stonybrook where he had recently retired to take on a professorship at National Chiao Tung University in Taiwan.

I had only had a few brief meetings with Ko but I knew his work quite well. In his best known work, Ko, in a solo paper, created an infinite series of oracles A1, A2, … such that relative to Ak, the polynomial-time hierarchy collapses to exactly the kth level, that is Σk-1 ≠ Σk = Σk+1 = PH. Ko wielded the switching lemma like a scalpel, pulling part the k-1st and kth levels while leaving enough room to encode the k+1st level. He actually gives two sets of oracles, one which collapses PH to PSPACE while collapsing the hierarchy to the kth level and one that separates PH from PSPACE. Even his oracle showing P=NP≠PSPACE wasn't trivial and I used it as an example of a hard to settle complexity question.

Ko, with Tim Long and Ding-Zhu Du, showed that if P ≠ UP if and only if there exist two sets that were one-to-one length-increasing polynomial-time reducible to each other but not polynomial-time isomorphic. This paper played a large role in helping us understand the isomorphism conjecture.

Ko, with Pekka Orponen, Uwe Schöning and Osamu Watanabe, used Kolmogorov complexity to measure the complexity of an instance of a problem. The instance complexity of x in a set A is the smallest program that will correctly answer whether x is in A, and will not give an incorrect answer for any other y in A, though it can answer "I don't know" for y ≠ x.

Ko also had several papers on complexity of real-valued functions and wrote several textbooks and manuscripts. A big loss for all of us in the complexity world.

6 comments:

  1. Hi, I saw his name on the whiteboard when I was at Tsinghua some time ago. He was, I believe, on sabbatical at Tsinghua during that time. I never actually saw him in office; was always interested in getting to meet him. Sad news. He was very young, by today's standards.

    ReplyDelete
  2. I liked his observation from IPL(14)1982 that NP in BPP implies
    NP = RP (jemand)

    ReplyDelete
  3. My great condolences to his family and colleagues.

    ReplyDelete
  4. We also lost the theoretical computer scientist Babak Farzad, died of cancer at age 41, a few days ago.

    ReplyDelete
  5. I consider him as one of the founding fathers of complexity over real numbers and analysis. His papers and books on the topic are still main references for papers in the field.

    ReplyDelete