Wednesday, December 26, 2018
Ker-I Ko (1950-2018)
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.