ACM SIGCHI General Interest Announcements (Mailing List)


Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Tom Hewett <[log in to unmask]>
Reply To:
Tom Hewett <[log in to unmask]>
Mon, 19 Apr 2004 20:39:12 -0400
text/plain (154 lines)
For those who live within driving distance of Philadelphia.

Symposium on Computational Complexity - April 28 from 8 a.m. - noon
at Drexel University

I. What is the Symposium on Computational Complexity?

II. Schedule

III. Abstracts

IV. Registration

I. What is the Symposium on Computational Complexity?

The Drexel Department of Computer Science will hold the "Symposium on
Computational Complexity" on Wednesday, April 28, 2004 from 8:45 a.m.-noon
in Behrakis Grand Hall (32nd and Chestnut Streets, at Drexel University in
Philadelphia). The symposium, sponsored by Drexel, the Franklin Institute,
Cephalon, and BioAdvance, is in honor of Dr. Richard M. Karp, recipient of
the 2004 Benjamin Franklin Medal in Computer and Cognitive Science.
Registration and breakfast, from 8-8:45 a.m., will precede the symposium.

Professor Richard Karp of the University of California, Berkeley is the 2004
Benjamin Franklin Medalist in Computer Science and Cognitive Science. He
will receive his Medal in recognition of his discoveries in computational
complexity, the field of computer science that addresses the fundamental
speed limits governing the computer solution of problems. Applications of
results from the field are widespread, including cryptography, computer and
manufacturing design, DNA matching, and transportation scheduling.

Dr. Karp will deliver the lecture "Even Approximate Solutions Can Be Hard to
Compute." Other symposium speakers include Dr. Eric Allender of Rutgers
University and Nobel Prize Laureate Dr. Avi Widgerson of the Institute for
Advanced Study.

For more information on the symposium, visit

II. Schedule

8:00 - 8:45  Registration and Breakfast

8:45-9:15  Opening and Welcoming Remarks

9:15  The Audacity of Computational Complexity Theory, by Dr. Eric Allender,
Professor, Rutgers University, New Brunswick NJ

10:15    The power and weakness of randomness (when you are short on time),
by Dr. Avi Widgerson, Institute for Advanced Study, Princeton NJ

10:35  Coffee Break

11:00    Even Approximate Solutions Can Be Hard to Compute, by Dr. Richard
Karp, University of California, Berkeley and International Computer Science
Institute, Berkeley CA

12:00   Closing remarks

III. Abstracts

Title: The power and weakness of randomness (when you are short on time)

Speaker: Avi Wigderson, IAS, Princeton


Man has grappled with the meaning and utility of randomness for centuries.
Research in the Theory of Computation in the last 30 years has enriched this
study considerably. I will talk about two main aspects of this research on
randomness, demonstrating its power and weakness respectively.

1. Randomness is paramount to computational efficiency. I will show how the
use of randomness can dramatically speed up computation (and do other
wonders) for a variety of problems and settings.

2. Computational efficiency is paramount to understanding randomness. I will
explain the new, computationally-motivated definition of randomness, and try
to argue its merits as the "right" definition. I will then show how such
randomness may be generated deterministically, from computationally
difficult problems.

Title: The Audacity of Computational Complexity Theory

Speaker: Eric Allender, Professor, Rutgers University, New Brunswick NJ


Complexity Theory has been successful because of several daring (or even
audacious) steps, such as:

1. Claiming that asymptotic analysis has any bearing on real-world (finite)
2. Claiming that it is reasonable to study time complexity on Turing
3. Studying nondeterministic (and even less realistic) machines.
Using "polynomial time" as an abstraction for "feasible".

Indeed, people who have had only a brief introduction to the field of
computational complexity may be forgiven for doubting that it really has any
bearing on practical aspects of computing.

This talk will introduce some of the main concepts and accomplishments of
complexity theory, with emphasis on the considerations that have led
theoreticians to embrace notions (such as the ones cataloged above) that
initially seem absurd.

The talk will illustrate how complexity theory does provide convincing
proofs that certain interesting transformations from input to output cannot
be computed (in this universe).  It will discuss the question of whether
problems that require exponential time are actually infeasible (and it will
discuss why this question has been attracting more attention
recently).  It will provide a non-technical overview of the field of
computational complexity, and of the central role played by the
notion of reducibility.

IV. Registration

This event is free and open to the public, but registration is REQUIRED. To
register, email [log in to unmask] or call 215.895.2669. If you
have not registered as of April 28, you may still attend the speeches only.


Tom Hewett                                        *                   *
Professor of Psychology and                       *                   *
Professor of Computer Science                     *                   *
Department of Psychology                          *  "Things change." *
Drexel University                                 *                   *
32nd & Chestnut Streets                           *                   *
Philadelphia, PA 19104  USA                       *                   *
Phone: +1 215-895-2461   FAX: +1 215-895-1333     *   --Movie title   *
email: [log in to unmask]                          *                   *                 *                   *