Breakthrough in Circuit Complexity

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.

Advertisements

5 Responses to “Breakthrough in Circuit Complexity”

  1. ryan williams Says:

    Just write him, that you knew everything…bebebebeee
    (once you tried it was a success)

  2. Dave Says:

    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…

  3. domotorp Says:

    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).”

  4. daveagp Says:

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

  5. domotorp Says:

    Especially for big people, like them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: