[Computational Complexity] 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.
Thanks Laci for being my Merlin.
Posted By Lance to Computational Complexity at 3/25/2010 04:38:00 AM