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.

Where can one get a copy of the Babai-Frankl notes on "Linear Algebra Methods in Combinatorics"?

ReplyDeleteDoes this actually work?

so you say you wrote four papers with laci but then you go on stating that "even though we didn't co-author" .....

ReplyDelete?????

can you explain the semantics behind this please ?

I think Lance meant even he was not writing a paper with Laci, he was helpful in his research.

ReplyDelete^even WHEN he

ReplyDeleteok. this makes more sense. it's one thing to mean something, the other thing to actually e-x-p-l-i-c-i-t-l-y state so.

ReplyDeleteYou can find the book "Linear Algebra Methods in Combinatorics" in www.gigapedia.com

ReplyDelete