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 A

_{1}, A

_{2}, … such that relative to A

_{k}, 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.

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.

ReplyDeleteI liked his observation from IPL(14)1982 that NP in BPP implies

ReplyDeleteNP = RP (jemand)

My great condolences to his family and colleagues.

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

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

ReplyDeleteRemembering Martin Hofmann in silence.

ReplyDeleteMissed professor Ker-I Ko who did excellent job on teaching theory of computation in stonybrook

ReplyDelete