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.

- 16 April 1997:
**Bernard Chazelle**(Princeton) . Discrepancy Theory and Computational Geometry. - 31 May 1996:
**Sanjeev Arora**(Princeton). Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems. - 30 May 1996:
**Laszlo Lovasz**(Yale University). The delight of walking randomly. - 11 April 1996:
**Christos Papadimitriou**(UC Berkeley). Computational Approaches to Organization Theory. - 25 January 1996:
**Andrew Yao**(Princeton). An Overview of Quantum Cryptography. - 1 December 1995:
**Frank Harary**(New Mexico State University). Recent results on hypercube theory. - 9 November 1995:
**Prabhakar Raghavan**(IBM Almaden). Queueing theory without independence assumptions. - 23 May 1995:
**N.G. de Bruijn**(Eindhoven University). Reflections on type-theoretical computer-aided checking of mathematics. - 5 April 1995:
**Robin Milner**(Cambridge University). Some applications of the pi calculus. - 4 November 1992:
**Christos Papadimitriou**(UC San Diego). Complexity as a Metaphor. - 19 May 1994:
**Moshe Y. Vardi**(IBM Almaden and Rice University). Infinitary logics in computer science. - 4 May 1994:
**Leonard Adleman**(University of Southern California). Finite model theory: A personal perspective. - 21 April 1994:
**Umesh Vazirani**. "Go with the winners" algorithms. - 10 February 1994:
**Sanjeev Arora**(UC Berkeley). Probabilistic checking of proofs and hardness of approximation problems. - 18 November 1993:
**Tom Leighton**(MIT). Multicommodity flows: A survey of recent research. - 1 November 1993:
**David S. Johnson**(AT&T Bell Laboratories) . Finite model theory: A personal perspective. - 11 March 1993:
**Ashok K. Chandra**(IBM Almaden) . Towards More Realistic Models of Parallel Computers. - 9 February 1993:
**David Harel**(Weizmann Institute). Towards a theory of infinite computable structures and databases. - 9 February 1993:
**Samson Abramsky**(Imperial College). Games, types, and interactions. - 12 November 1992:
**Donald Knuth**(Stanford). Textbook example of recursion. - 21 May 1992:
**Joel Spencer**(NYU). Flip a coin! From Erdos to algorithms. - 27 April 1992:
**Christos Papadimitriou**(UC San Diego). Inefficient existence proofs and complexity. - 2 April 1992:
**Ronald Fagin**(IBM Almaden). Finite model theory: A personal perspective. - 5 March 1992:
**Richard M. Karp**(UC Berkeley and ICSI). Physical mapping of chromosomes: A combinatorial problem in molecular biology.

**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.

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.

- Differences between the model theory of finite structures and infinite structures. Most of the classical theorems of logic fail for finite structures, which gives us a challenge to develop new concepts and tools, appropriate for finite structures.
- The relationship between finite-model theory and complexity theory. Surprisingly enough, it turns out that in some cases, we can characterize complexity classes (such as NP) in terms of logic, without using any notion of machine, computation, or time.
- Zero-one laws. There is a remarkable phenomenon, which says that certain properties (such as those expressible in first-order logic) are either almost surely true or almost surely false.
- Descriptive complexity. Here we consider how complex a formula
must be to express a given property.

- restriction fingerprinting, in which an enzyme called a restriction nuclease cleaves the fragment wherever a particular short sequence of nucleotides occurs, and the lengths of the resulting pieces are measured;
- hybridization fingerprinting, in which each fragment is tested to determine which of certain short nucleotide sequences called probes it contains.

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.