What a pity that it’s not mine. You can read about it on any complexity blog, so I will spare you. At least I e-know the guy, we managed to lock horns about one of my mathoverflow questions, it was of course his fault (imo) that he did not understand my question first. I guess I will have to put him in my Wigderson box…

I recently read another very need TCS paper, it applies Green’s theorem from multivariable calculus to assign weights to the edges of a directed planar graph such that no cycle sums up to zero. I am interested in these questions, on one hand because of PPAD, on the other because of this TCSOverflow question. I really wonder why people voted up Scott Aaronson’s answer so much, when it only gave a completely uninteresting comment. Is it because he is so famous or just simply because my question is so brilliant that it attracted so many readers? I think we will soon learn the answer as Gunter Rote informed me that the related problem is hard, which would also make this NP-hard if we allow randomized reductions. I still have to think these over, so I will post about this another time.

### Like this:

Like Loading...

*Related*

This entry was posted on November 14, 2010 at 17:59 and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

November 14, 2010 at 18:41

Just write him, that you knew everything…bebebebeee

(once you tried it was a success)

November 14, 2010 at 18:49

Very interesting — so much for my half-baked idea to prove it was in P!

What is a Wigderson box? It sounds like you would put Schrodinger’s cat inside and then put it as part of a quantum circuit…

November 14, 2010 at 23:31

I have this unfinished business with him that when he visited ELTE in 2007 then I told him the main result of my Master’s Thesis, in june he wrote a mail to me that he discovered this result was already published, just nobody knew about it because it was not proved in the paper where it appeared and was not the main part, and finally in july he submitted a paper (that got published) with the theorem and its proof without even telling me, I just saw it by accident. It is theorem 6.1 here:

http://theoryofcomputing.org/articles/v003a011/

My favorite is the sentence before the proof:

“As Yao’s paper does not contain a proof of this theorem, we give here a sketch of the proof (which probably exists somewhere in the literature).”

November 15, 2010 at 12:57

I see, that’s pretty lame. Also, it can be quite expensive to get boxes large enough for multiple people to fit inside.

November 15, 2010 at 18:09

Especially for big people, like them.