Ernst Specker Reminiscences

Karl Lieberherr, College of Computer and Information Science, Northeastern University, Boston, Massachusetts

For the obituary "Remembering Ernst Specker" in "Elemente der Mathematik" by Erwin Engeler and Norbert Hungerbuehler.

Ernst Specker was one of my favorite professors during my studies at ETH Zurich from 1968 to 1977. He impressed me with his teaching skills and his deep interest in human issues: I was most impressed when my professor would give a sermon in a local church (Wasserkirche near the Limmat in down-town Zurich). It happened that my wife and I chose that church to get married. In his lectures he kept us on our toes by asking questions like: "Mr. X, do you believe that?" or "Ms. Y, how would you construct that?".

I had the privilege to have Ernst as my Master Thesis advisor. He encouraged me to continue with a career in Computer Science rather than Mathematics. During my PhD work with my advisor, Erwin Engeler, I stayed in touch with Ernst and told him about my clause learning algorithms for satisfiability and a paper by David Johnson on approximating satisfiability. I was lucky to catch Ernst's attention and he posed new questions and used his strong problem solving skills to get them answered. This lead to the "Complexity of Partial Satisfaction" paper in the Journal of the ACM, 1981, also called the Golden Ratio Result.

The development of the Golden Ratio Result for Maximum Satisfiability was an experience that was extremely valuable to me. Ernst used the development of the paper to teach me how to come up with results myself. When he had a result, he would let me rediscover it, maybe with hints, rather than giving me his solution directly. It was initially magic to me how to reduce the logical problem into a calculus question about the saddle point of a function with two variables.

Once the mathematical problem was solved (there exists an assignment of a given quality), new questions opened up: How can we efficiently find those assignments? Ernst was in the driver's seat to come up with the algorithm as he was the one who knew the magical facts about the existence of sufficiently many doubly-transitive permutation groups.

Close to Ernst's "retirement" we worked on a follow-up paper "Complexity of Partial Satisfaction II", generalizing the results to Boolean constraint satisfaction with arbitrary relations. He used his calculus skills to symbolically derive the saddle points which are the P-optimal thresholds where the problems become NP-hard.

During the last few years my wife and I greatly enjoyed being invited to Ernst's home during our visits to Switzerland and develop a more personal relationship with Ernst and Suzanne. They both took interest in our personal lives and my wife's artistic endeavors. Ernst and Suzanne kept several of his students from the 1970s in touch with each other during wonderful dinners at their home.

It was a privilege to have Ernst Specker in my life. He opened up so many possibilities for me. Even today I am working on the "Specker Challenge Game" = "Scientific Community Game" = SCG which is an abstraction of what went on in our Complexity of Partial Satisfaction work. SCG is used for teaching Computer Science as well as a tool to find innovative solutions to computational problems. I am grateful to Ernst for his guiding influence on my life.