Luca Trevisan

For converting LaTex to WordPress, I'm a fan of https://lucatrevisan.wordpress.com/latex-to-wordpress/

"One of saints of computational complexity?" see https://lucatrevisan.wordpress.com/2016/10/07/avi60-zero-knowledge-for…

Over at Scott Aaronson's blog his father has mentioned that, according to the coroner, he may have had undiagnosed type-I diabetes [1]. His father also mentions that Michael supported the charity givedirectly.org if anyone prefers to offer condolences that way. It's a sad event for the theoretical CS community. I didn't know Michael, but looking at some of the other memorials some prominent researchers have written ([2], [3]), he appears to have been an extremely promising researcher and collaborator. [1] https://www.scottaaronson.com/blog/?p=3468#comment-1746556 [2] https://blogs.princeton.edu/imabandit/2017/09/28/michael-b-cohen/ [3] https://lucatrevisan.wordpress.com/2017/09/26/3915/

In a tangential note, if P=NP, a sufficiently carefully crafted algorithm very much like that suffices to solve any NP complete problem in polynomial time! (Of course the constants are ridiculously, absurdly large) http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessity-of-enume…

First of all this has no relevance if you're not a complexity theorist. No "practical" impact, not even remotely. A real downer, I know, but I thought that had to be stated up front. The question is why are complexity theorists excited about this. When a problem is too hard to solve, you look for easier versions to solve first. Here the easier version is to prove that the complexity class NEXP (which is intuitively vastly more powerful than even NP) is bigger than a certain class of circuits of constant depth (circuits with polynomial depth are known to be roughly equivalent to P, and constant-depth circuits are intuitively vastly less powerful). ETA: the circuits considered here are "non-uniform," which makes the previous paragraph slightly inaccurate. Nevertheless, the point stands that the goal here is to separate two complexity classes that are intuitively very different in their power. Circuit lower bounds -- proving that a restricted class of circuits, as above, is in fact limited in its computational power -- have been notorious for their hardness. The reason one would want to prove this kind of statement is not because these circuits are objects of practical interest, but because of the proof techniques that would come out as a side-effect, in the hope that these techniques would be applicable in solving other, harder problems. So that's the gist of it: the 3 reasons this theorem is exciting are: proof techniques, proof techniques and proof techniques. Now some…