Computational Complexity


Creative Commons License
This work is licensed under a Creative Commons License.

Powered by Blogger™

Thursday, April 29, 2004

Karp Symposium

[A report from weblog correspondent Bill Gasarch. Link to Allender's talk added 5/7]

On Wednesday April 28 there was a SYMPOSIUM HONORING DR. RICHARD M. KARP at Drexel University in Philadelphia.

They were honoring him for winning the BEN FRANKLIN MEDAL IN COMPUTER AND COGNITIVE SCIENCE (There are Ben Franklin Medals for Physics, Chemistry, Life Sciences, Earth Science, Computer and Cognitive Science, and Engineering.)

There were three talks:

ERIC ALLENDER: The Audacity of Computational Complexity.

This talk described the basics of complexity theory and mostly focused on reductions. A nice contrast that it made:

  1. in the year 2004 we have good reason to think that many problems (e.g., SAT, 3-COL) are hard, except factoring which is still hard to classify.
  2. in the year 1970 most problems (including SAT, 3-COL) were hard to classify.
The talk also pointed out some of the problems with Computational Complexity (e.g., "How can you call a n100000 algorithm feasible?") and answered them nicely (e.g., "we want to show problems are hard, so showing its not in P does that.") The talk both began and ended on the topic of CHECKERS and GO being computationally hard problems.

AVI WIGDERSON: The Power and Weakness of Randomness (When you are short on time).

This talk showed several examples of problems where randomness helps (hence randomized algorithms are powerful) but also indicated why there may be reason to think that you can always replace a randomized algorithms with a polynomial time algorithm (hence randomization adds no power). The problems it helped on involved sampling, routing in networks, and mazes.

RICHARD KARP: Even Approximation Solutions can be Hard to Compute.

This talk was about certain problems that can be approximated and certain ones that (it seems) cannot be. A nice contrast was variants of TSP, which ranged from what can be approximated very well, to what can be approximated some, to what can't be approximated. He also brought in randomized rounding as a technique for approximation. The talk ended on PCP (done informally) and how it can be used to show lower bounds for approximation.

The talks were all well presented and quite understandable. The point of the talks was to expose our area to people outside of theory and perhaps even outside of computer science. As such the theorists in the audience did not learn much new; however, it is still interesting to see someone else's perspective on material that you are familiar with.

9:56 AM # Comments []  

Wednesday, April 28, 2004

Conferences versus Journals

A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gödel Prize. I wish this was an isolated incident but it reflects on a sad state of affairs in computer science and theoretical computer science in particular. Too many papers in our field, including many great ones, do not get submitted to refereed journals. In an extreme case, Steve Cook received the Turing Award mostly for a STOC paper.

In most cases, conferences in computer science are more selective than journals. Your reputation in theoretical computer science is measured more by the conferences your papers appear than the journals. In other fields like mathematics, physics and biology, journals have a much greater reputation and most of their papers do appear in refereed form. I believe the reason is historical: computer science started as a quickly changing field and journals could not keep up with the rapidly emerging ideas.

Conference program committee cannot and do not produce full referee reports on conference submissions. Proofs are not verified. Papers are not proofread carefully for mistakes and suggested improvement of presentation. Computer science suffers by not having the permanency and stamp of approval of a journal publication on many of its best papers. The founders of the Gödel Prize put in the journal requirement to encourage potential award winning papers to go through the full refereeing process.

Many papers in our field do appear in journals and some researchers are extremely diligent in making sure all of their work appears in refereed form. Also I know of no computer scientist who purposely avoids sending their papers to a journal. But when we have a system that does not value journal publications, a computer scientist pressed for time often will not make the effort to take their papers past the conference version.

8:53 AM # Comments []  

Monday, April 26, 2004

Is Disney World NP-complete?

The Unofficial Guide to Walt Disney World 2004 gives a lesson on complexity by describing the optimal tour of the Magic Kingdom as a traveling salesman problem. Some excerpts:
As we add more attractions to our list, the number of possible touring plans grows rapidly...The 21 attractions in the Magic Kingdom One-Day Touring Plan for Adults as a staggering 51,090,942,171,709,440,000 possible touring plans...roughly six times more than the estimated number of grains of sand in the whole world...Fortunately, scientists have been hard at work on similar problems for many years..finding good ways to visit many places with minimum effort is such a common problem that it has its own nickname: the traveling salesman problem.
The book goes on to describe the computer program they use to approximate the optimal tour. Read more here (which I found by searching within the book for "traveling salesman" on the Amazon site). You'll need to be a registered user of to read it.

9:17 AM # Comments []  

Sunday, April 25, 2004

Gödel Prize

From the PODC (distributed computing) mailing list via Harry Buhrman. Usually the winners are kept secret until the ICALP or STOC conference but the PODC mailing list has already broken the news.
It has been recently announced that this year's winners of the Gödel Prize are

As we all know, the result was initially published simultaneously in STOC 1993 also by Eli Gafni and Liz Borowski, but the Gödel Prize is awarded only to journal articles.

Congratulations to the winners!

Note that for the second time, the Gödel's Prize honors a core PODC topic (in 1997, Joe Halpern and Yoram Moses won the prize). This is a sign both of the scientific quality of the PODC community, as well as the respect it wins in the theoretical CS world at large.

In case you are counting, that's Complexity 5, PODC 2.

6:53 AM # Comments []