Toni Pitassi and Russell Impagliazzo highlighted a small sample of Misha's great work in proof complexity. Toni focused on automizability, given a proof system like resolution or DPLL (backtracking), how hard is it to find a proof not much larger than the original proof. Misha and his co-authors showed you cannot find

- Resolution proofs with a nearly linear factor larger than the smallest possible proof unless P=NP. (JSL 2001)
- Resolution proofs within a polynomial of the smallest proof size
unless W[p] is fixed-parameter tractable, which implies SAT can be
solved in time 2
^{εn}for some ε<1. (FOCS 2001)

Russell talked about the problem of showing lower bounds for DPLL algorithms. Alekhnovich, Hirsch and Itsykson showed that certain randomly generated satisfiable formulas cannot be solved by certain kinds of backtracking algorithms (ICALP 2004). The 2005 Complexity paper showed lower bounds even when allowing arbitrary pruning of the search tree. Work on strengthening this later paper was an ongoing project when Misha passed away.

When we lose our colleagues at or near the end of their careers we celebrate what they have given to our field. When we lose them early, like Alekhnovich at 28, we also regret what might have been. He would have continued his great research career as well as about to start a new phase in his personal life with a wedding in Russia planned for just next week. His loss still deeply affects many at this workshop.

Misha's tragic death was so striking (I actually got the message right at the moment when I was sending him an email) that I was unable to add anything at that moment.

ReplyDeleteMisha was a kind of mathematician that knew facts and proofs by heart and not by formal logic. Far not everyone of us is of that kind - for example, I am not.

Misha enjoyed the life and I think he knew what are the stakes.

His death is an enormous loss for the community, not to say about people closer to him.

P.S. Let me also apply the words "Misha's lead role" to our joint [AHI] paper as well.

P.P.S. Correction: Itsvkson -> Itsykson.

I'd like to add that while Misha certainly was enthusiastic and competitive in his work, he was never "aggressive" the negative sense.

ReplyDeleteHe was a really nice guy, especially when once you got to know outside of a professional context. When my two body problem was giving me grief at IAS, Misha was eager to cheer me up and he taught me how to go rock climbing. And that helped.

nate

later => latter

ReplyDeletegreat russian!what a loss!

ReplyDeleteI have learned of Misha's death only now.

ReplyDeleteHe was certainly a genius, and his contribution during less than a decade is well-worth a 40-year long carreer.

I think that it will be in place to organize a conference or/and an award in his memory.

If anyone has an idea in this direction and needs a hand, I will be happy to do.

Michael Elkin