Talks are often held in Jordan Hall, on the Main Quad of Stanford's Campus. Click here for directions. Talks are also held in the Gates Building, near the Main Quad of Stanford's campus. Click here for directions.
Biography: Bernard Chazelle is professor of computer science at Princeton University. He received his PhD in computer science from Yale University in 1980. His research interests lie in the design and analysis of algorithms, in particular geometric algorithms. Recently, his work has focussed on derandomization, graph algorithms, and decomposition algorithms for 3D solids.
WWW:
http://www.cs.princeton.edu/~chazelle
In this talk we will present a new algorithm that is an approximation scheme: for any fixed c>0, it computes a tour whose cost is at most 1+c times the optimal. The algorithm's running time is n^{O(1/c)}.
The algorithm generalizes to many other geometric problems, including the famous Minimum Steiner Tree problem. It also generalizes (with some increase in running time) to d-dimensional instances.
Biography: Sanjeev Arora is a faculty member at Princeton University. His research interests include computational complexity, uses of randomness in computation, probabilistically checkable proofs, and computing approximate solutions to NP-hard optimization problems.
WWW:
http://www.cs.princeton.edu/~arora/
How much time will he need (on the average) before you get back to your hotel? Or before you get to the Louvre? How long does it take to see the whole city? How long does it take before you are hopelessly lost (i.e., you can be anywhere with the same probability)?
To the physisist, you are doing a Brownian motion; to the probabilist, you follow a Markov chain; and to the computer scientists, you use the best (in many cases, the only known) way to generate a random place in Paris.
Biography: László Lovász was born on March 9, 1948 in Budapest, Hungary. He is married, has 4 children. He obtained his doctoral degree in mathematics from the Eötvös Loránd University in Budapest, Hungary in 1971. Currently he is Professor of Mathematics and Computer Science at Yale University. He is a member of the Hungarian Academy of Sciences, and the Academia Europaea. His field of research is discrete mathematics, in particular its applications in the theory of algorithms and the theory of computing.
WWW:
http://www.cs.yale.edu/HTML/YALE/CS/Brochure/faculty/lovasz.html
Biography: Christos H. Papadimitriou currently teaches at the University of California at Berkeley. Before joining UCB, he taught at Harvard, MIT, Stanford, Athens Polytechnic, and UC San Diego. He has published four books Computational Complexity, The Theory of Database Concurrency Control, Combinatorial Optimization: Algorithms and Complexity, and Elements of the Theory of Computation. His interests include the theory of algorithms and complexity and its applications to databases, optimization, artificial intelligence, and game theory.
WWW:
http://HTTP.CS.Berkeley.EDU/~christos
Biography: Andrew C. Yao is William and Edna Macaleer Professor of Engineering and Applied Science at Princeton University. He received a Ph.D. degree in Physics from Harvard University in 1972, and a Ph.D. degree in Computer Science from the University of Illinois in 1975. He had served on the faculty at MIT, UC Berkeley and Stanford before joining Princeton University in 1986. Andrew Yao is a fellow of the ACM, and he was awarded the SIAM George Polya Prize in 1987 for his work in computational complexity.
Biography: FRANK HARARY holds the PhD from the U of California, Berkeley, 1948, in mathematical logic, This degree is so old that it was obtained B.C. (before computers). He has been awarded three honorary doctorates: U of Aberdeen, Scotland 1975 (mathematics); U of Lund, Sweden 1978 (social sciences); U of Exeter, England 1992 (computer science). He holds fellowships at both Cambridge U (Churchill College) and Oxford U (Wolfson College) and is also a Fellow of the National Academy of Sciences, India. He was awarded a Humboldt Senior Fellowship Prize in 1978. He founded both the Journal of Combinatorial Theory (1966) and the Journal of Graph Theory (1977, when it won the American Association of Publishers award for "Best new journal of the year"). He is a member of the editorial board of 14 scholarly journals. He has published over 600 papers on graph theory and its applications, not only in mathematics and computer science journals, but also in the fields of anthropology, art, biology, chemistry, geography, linguistics, mechanical engineering, operations research, physics, psychology, and statistics. He has written 7 books and edited 10 others. His 1969 book, "Graph Theory", became the fifth most cited work in the mathematical research literature. He has delivered over one thousand invited lectures at conferences and universities in a total of 71 countries. In particular, he has spoken in all 50 states of the USA and all 10 provinces of Canada. He has completed 5 alphabetical lists from A to Z, namely: co-authors, journals of published papers, American universities addressed, American cities where lectures have been given, and foreign cities. From the U of Michigan he is professor emeritus of mathematics. He is also distinguished professor emeritus of computer science at New Mexico State U.
Biography: Prabhakar Raghavan received his PhD from the University of California, Berkeley, in 1986. He worked at the Mathematical Sciences Department of IBM's T.J. Watson Research Center until July 1995; he is currently Manager of Mathematics and Related Computer Science at IBM's Almaden Research Center. His research interests are centered on applications of randomized algorithms and combinatorial optimization.
Biography: Professor de Bruijn is one of the world's most distinguished mathematicians. After writing many deep papers in mathematical analysis during the 1940s and 1950s, culminating in his definitive book on asymptotic methods, he began to turn his attention to questions of automating the validation of mathematical proofs. He has published papers on a great variety of topics, including an early Dutch computer program for pentominoes. He is also known for many theorems in combinatorial mathematics and graph theory, for studies of Penrose tiles, etc.
Related paper:
N.G. de Bruijn, Reflections on Automath. In: Selected Papers on
Automath, edited by R.P. Nederpelt, J.H. Geuvers and R.C. de
Vrijer, Studies in Logic, vol. 133, pp. 201-228. North-Holland
1994.
I shall discuss both these applications, as far as time allows. Along the way I shall define the pi calculus formally, and then use whatever of its theory is needed for the applications. In particular, I shall use a simple system of sorts (analogous to simple types in lambda calculus) in a refined version due to Pierce and Sangiorgi. I shall also explain the representation of the lambda calculus in the pi calculus, and show that its soundness depends on certain key properties of bisimilarity.
No previous knowledge of the pi calculus will be assumed.
Biography: 1991 Turing Award winner Robin Milner was appointed Professor of Computer Science at Cambridge (UK) in January 1995. Before that he was a Professor at Edinburgh, where he worked for twenty-two years. In 1986 he became founding Director of the Laboratory for Foundations of Computer Science at Edinburgh.
Biography: Christos H. Papadimitriou is the Irwin and Joan Jacobs Professor of Information and Computer Science at the University of California at San Diego. Before joining UCSD, he taught at Harvard, MIT, Stanford, and Athens Polytechnic. He has published four books, "Computational Complexity," "Elements of the Theory of Computation," "Combinatorial Optimization: Algorithms and Complexity," and "The Theory of Database Concurrency Control," as well as numerous journal articles on various aspects of the theory of algorithms and complexity, as well as its applications to optimization, databases, logic, artificial intelligence, and mathematical economics.
The talk, which represents joint work with P. Kolaitis, will be self-contained. Only a basic familiarity with first-order logic will be assumed.
Biography: Moshe Vardi is interested in applications of logic to computer science: database theory, finite-model theory, knowledge theory, and program specification and verification. Recent work includes the use of knowledge to analyze distributed systems, connections between fixpoint logics and complexity classes, and using automata to verify concurrent and nondeterministic programs. Currently serving as the chairperson of the Rice University Computer Science Department, he is also affiliated with the IBM Almaden Research Center.
FREE SUPER COMPUTERS will be given to all who attend this talk.
Biography: Currently the Henry Salvatori Professor of Computer Science at USC, Leonard Adleman coinvented the RSA public key cryptosystem and has worked on primality testing algorithms. His student Fred Cohen and he worked on computer viruses, and he also currently researches AIDS and immunology. A former MIT associate professor of mathematics, he received his Ph.D. from UC Berkeley.
By contrast, more straightforward search strategies can be shown to take exponential time in the worst case. Our original motivation for studying this model was that it mimics the polynomial time behavior of simulated annealing algorithms. The tree analysis suggests that a "go with the winners" implementation of simulated annealing might be superior to several independent runs of simulated annealing.
Joint work with David Aldous.
Recent work has yielded a simple explanation: many NP-hard optimization problems are also NP-hard to approximate. Among the problems for which this has been proved are Independent Set, Chromatic Number, Set Cover, Vertex Cover, Max-Cut, Decoding to the nearest codeword, Learning in the presence of Errors, and many others. At the heart of these new results is a new type of NP-completeness reduction which acts globally (as opposed to the classical reductions, which used local transformations involving gadgets etc.). A more interesting way to view this reduction is as a new probabilistic definition of NP : NP is exactly the class of languages for which membership proofs (i.e., certificates) can be checked in polynomial time by using only O(log n) random bits and examining only O(1) bits in them.
The talk will be a survey of this new area (including the work of other researchers) and its open problems.
Biography: Sanjeev Arora is a graduate student at UC Berkeley and has co-authored several papers which contributed to the above theory. These will form part of his dissertation (he is graduating this year). His other research interests include computational complexity, and the computational uses of randomness.
In the talk, we will survey recent work on improved algorithms for the multicommodity flow problem. Particular emphasis will be placed on approximation algorithms that can compute near optimal flow paths in a relatively small amount of time. A new and very simple local-control algorithm for multicommodity flow will also be presented. The latter algorithm is notable in that it does not rely on augmenting paths, shortest paths, min-cost paths, or similar techniques to push flow through the network. As a consequence, the algorithm is particularly well-suited for applications involving distributed networks.
We will also briefly mention recent work on the development of a max-flow/min-cut theorem for multicommodity flows.
The talk will be introductory in nature.
Biography: F. Thomson Leighton, professor of Applied Mathematics at MIT and a member of the MIT Laboratory of Computer Science, performs research in algorithms, VLSI, complexity theory, and combinatorics, with an emphasis in parallel algorithms and architectures. He is currently the editor-in-chief of the Journal of the ACM.
In bin packing, we are given a sequence of N items with sizes in the interval (0,1], and asked to pack them into a minimum number of unit-capacity bins. Under BEST FIT (in practice perhaps the best of the simple on-line heuristics), items are packed in order, with each item going into the bin with the smallest gap that can hold it (ties broken arbitrarily). If item sizes are uniformly distributed in the interval (0,1], it can be shown that the expected waste (sum of the gaps in all the bins) grows sublinearly with N. Surprisingly, if the distribution of sizes is uniform over an interval (0,u], u < 1, experiments indicate that the waste grows linearly. This also holds if sizes are uniform over the discrete sizes i/K, 1 <= i <= J, when J < K-2 is sufficiently large. Unfortunately, proving this observation (for ANY such continuous or discrete distribution), has remained an open problem for almost a decade.
Ed Coffman, Peter Shor, Richard Weber and I have been studying the simplest of the distributions for which linear waste appears to occur (the discrete uniform distribution with K=11,J=8). Assuming one is prepared to trust the result of a 24-hour computer run, we now have a proof. This talk will cover the bin packing background, and then give an overview of the mathematical and algorithmic techniques involved in our proof, as well as the general applicability and limitations of the approach. We also discuss related computer proofs that show that the expected waste is bounded when K=11,J<8 or K<11,J<K-1.
The talk should be accessible to a general Math/CS/OR audience.
Communication delays arise from two major limitations: bandwidth and latency, which have different consequences for algorithm design. A Block PRAM model of computation (BPRAM for short) models these two effects by allowing processors to communicate by transferring blocks of data - here n words can be transferred in time l+bn where l corresponds to latency, and b represents the (inverse of) bandwidth per processor. This model can be used to study several phenomena which arise in practice: inherent limits to parallelizing communication, computation-communication tradeoffs, bandwidth limits for problems such as sorting, FFT etc., importance of using both temporal and spatial locality of reference, the role of the l.p product of a machine as a determiner of the difficulty of generating efficient algorithms, etc. Furthermore, one can model phenomena akin to practice where tiny changes in the communication pattern can result in catastrophic changes in the running time of certain algorithms.
The research was done jointly with Alok Aggarwal and Marc Snir.
The talk will describe our recent work on infinite structures and databases, including the high undecidability of many problems on recursive graphs, a completeness result for computable database queries, and ways of deducing results for the finite case from those for the infinite case and vice versa. In view of the recent results about the impossibility of approximating problems hard for Max-SNP, one of our results seems to be particularly interesting, since it shows that any problem in NP whose infinite version is highly undecidable cannot be in Max-SNP (in fact, it is not even in Max-NP).
COMMENT: Of interest to Theoreticians and Mathematicians.
Biography: Christos H. Papadimitriou is the Irwin and Joan Jacobs Professor of Information and Computer Science at the University of California at San Diego. Before joining UCSD, he taught at Harvard, MIT, Stanford, and Athens Polytechnic. He has published four books, "Computational Complexity," "Elements of the Theory of Computation," "Combinatorial Optimization: Algorithms and Complexity," and "The Theory of Database Concurrency Control," as well as numerous journal articles on various aspects of the theory of algorithms and complexity, as well as its applications to optimization, databases, logic, artificial intelligence, and mathematical economics.
The most common approach to physical mapping is to compute, for each pair of fragments,a weight (either positive or negative) related to the probability that the two fragments overlap, and then construct an interval graph of maximum total weight. We argue that this approach makes insufficient use of fingerprint information. Instead, we cast the problem as a variant of the traveling-salesman problem in which the cost of travel between two cities depends on a small neighborhood around the cities within the overall tour. We then discuss some of the issues of algorithm design that arise in constructing efficient local optimization methods for this generalized traveling-salesman problem.
No prior knowledge of molecular biology will be needed to understand this talk.