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 http://www.cs.drexel.edu/modules.php?name=News&file=article&sid=160. 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 Abstract: 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 Topics: 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) computations. 2. Claiming that it is reasonable to study time complexity on Turing machines. 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] * * http://www.psychology.drexel.edu/ * *