Computational Complexity

Thursday, April 29, 2004

 
Karp Symposium

Posted by Lance

[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 n¹⁰⁰⁰⁰⁰ 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.

OVERALL:
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 #

Comment Feeds: This Post All