Friday, August 13, 2010

P vs NP vs IEEE (Guest post by Paul Beame)

(Update on P vs NP: The proof uses Finite Model Theory which is sometimes called That stuff that Neil Immerman does.. Neil Immerman has found a flaw in it. See Lipton's Blog for more information. My prediction is still that something interesting will come out of this but NOT P ≠ NP. And for those of you who read my blog but do not follow Lance on Twitter (the empty set?) note that Lance tweeted Much ado about an unverified proof.. Of course, if we all felt that way then who would verify it? A PCP?)

Guest Post from Paul Beame!

While the complexity world is debating how much to invest in trying to extract useful information from the recent attempt at resolving P vs NP, there is another item that may be useful to complexity blog readers who also happen to be members of the IEEE Computer Society which sponsors the CCC, LICS, and FOCS conferences. Voting just opened in the election for IEEE CS officers including the President.

I'd like to alert voters to a write-in campaign for Joe Bumblis for president of the IEEE Computer Society.

As anyone who has run a CCC, FOCS, or LICS knows, the IEEE CS has had a lot of very bureaucratic rules for running conferences. Conferences are run by the IEEE CS Technical Committees (like the TC on Mathematical Foundations of Computing which does CCC, LICS, and FOCS and which I currently chair). These TCs are groups of volunteers who have little power in the current organization of the IEEE CS. These TC volunteers have long chafed against the bureaucracy, often with little response from the main organization. The main officers of the IEEE CS have been from the Publications and Standards part of the organization and these groups dominate the nominating committees. The TC side of the organization has been shut out. IEEE CS ran into financial difficulty for a variety of reasons unrelated to conferences and the result has been more bureaucracy based on the Standards mentality that the way to fix things is to set up more rules, which pit CS staff in opposition to TC and conference volunteers.

This year we finally succeeded in getting the IEEE CS to allow an option that should substantially reduce bureaucracy for conferences like CCC, LICS, and FOCS but the organization still resists anything like the flexibility for TCs that SIGs have within ACM and still is tied to bureaucratic rules. Many of the most active and thoughtful TC chairs have agreed that we need to push a write-in campaign to finally get someone from the TC side in a position of authority and Joe has agreed to serve. Joe has been vice-chair of the board of TC chairs and would bring a very different perspective that has a chance of shaking things up. By comparison one of the other candidates for president recently refused to authorize the LICS 2010 budget as part of the Federated Logic Conference (long after registrations had opened) because it was charging $10 too little for non-IEEE-members (or $8 too much for members, depending on how you count). It took my intervention to expose the ridiculousness of this position before he was overruled.

We need your vote now!

(NOTE FROM GASARCH- as someone who has run a CCC I can VERIFY what Paul is saying without pointing to Lipton's blog or using a PCP.)

8 comments:

  1. Funny that a blog called "Computational Complexity" played next to no role in the verification or, in this case, disproof, of a supposed proof of the central question of the field. Contrast this with the technical discussion at Lipton's blog, involving several people from other fields.

    Judging from the topics of recent posts on this blog, it seems that this blog has degenerated to serve only as a venue for debates about the merits/demerits of STOC/FOCS, as a venue where frustrated complexity theorists can rant about who got jobs and who did not, and other such political discussions and trivialities.

    ReplyDelete
  2. "those of you who read my blog but do not follow Lance on Twitter"
    != "the empty set"

    ReplyDelete
  3. I would like to adhere to both comments made above me ("Twitter"?).

    ReplyDelete
  4. harsh words @anon 1. harsh words. I disagree.
    this blog provides truth venom.

    ReplyDelete
  5. To Anon 1: Lipton is already doing a wonderful job engaging the help of various experts to verify the proof. What additional purpose would it serve to duplicate that discussion here? On the other hand, Bill and Lance could express their doubts about the truth of the proof, but wouldn't such premature judgments be considered "nasty" by some?

    So you see, regardless of what they do or don't do, someone is going to criticize them. Why not just wait until the dust has settled, and then discuss whatever is new, interesting, and TRUE about the paper. Perhaps they need time to digest it first before adding more noise.

    ReplyDelete
  6. i like it math and computer sciences

    ReplyDelete
  7. NP vs IEEE? Now there's a problem to work on.

    ReplyDelete
  8. Judging from the topics of recent posts on this blog, it seems that this blog has degenerated to serve only as a venue for debates about the merits/demerits of STOC/FOCS, as a venue where frustrated complexity theorists can rant about who got jobs and who did not, and other such political discussions and trivialities.

    ReplyDelete