Laci Babai Turns 60

I'm at Ohio State for the Combinatorics, Groups, Algorithms, and Complexity Conference in honor of Laci Babai's 60th birthday. An incredible turn out with 74 talks. I've never seen a birthday conference with parallel sessions before. A nice mix of computer scientists and group theorists and a surprising number of Laci's former (and current) students made the trip incluing some Hungarians I haven't seen in twenty years.

I gave a talk yesterday on Wednesday about how Laci indirectly and directly affected my early research career. My Ph.D. thesis was on interactive proofs which Laci co-invented in 1985 as Arthur-Merlin games. When I graduated in 1989, I was lucky to get a 2-year position at the University of Chicago, a great theory department with Laci Babai as its star. That 2-year appointment lasted nearly 20 years, much because of the research I did with Laci those first few years.

I wrote four papers with Laci: MIP = NEXP, Arithmetization, Derandomization under worse-case assumptions and Holographic Proofs. These were all exciting papers. MIP = NEXP is surely the most influential paper I had since it led to Probabilistically Checkable Proof Systems.

Even when we didn't co-author, Laci was an invaluable research. My advisor, Mike Sipser, told me his approach to research in complexity: Find the underlying combinatorial problem and solve that problem. I took that a step further: Once I couldn't solve the combinatorial problem I walked down the hall to Laci's office where he could often find a simple trick that gave me what I needed.

Beyond research, Laci really gives himself to the community with his teaching, the Budapest Semesters in Mathematics and his open access journal Theory of Computing.

Thanks Laci for being my Merlin.