
The Fields Institute 10th Anniversary Celebrations
June 1819, 2002
Speaker Abstracts

Stephen Cook,
University of Toronto
Propositional Proofs of Combinatorial Principles
A fundamental problem in propositional proof complexity is proving
superpolynomial lower bounds on proof lengths for specific proof
systems S. In general a formal proof in S is a sequence of formulas
with limited expressive power, and the lower bound is proved by
finding a combinatorial principle which translates into a family
of tautologies whose proofs require concepts not easily expressed
by the lines in a formal S proof. For example the Pigeonhole Principle
translates into tautologies requiring exponential size proofs
when the lines in the proof are restricted to have a bounded AND/OR
alternation depth. For less restricted proof systems no good lower
bounds are known, although linear algebra and graph theory supply
interesting combinatorial principles that are conjectured to require
superpolynomial proofs. When formal proofs are extended to allow
propositional existential quantifiers, the resulting proof system
is closely connected to the complexity class Polynomial Local
Search.

Persi Diaconis,
Standford University
Patterns in Eigenvalues
Typical large unitary matrices show remarkeable in their
eigenvalue distribution. These patterns occur in telephone incryption,
nuclear scattering and zeros of the zeta function. I will explain
what we know about the patterns and these connections.

Vaughan Jones, University of California
at Berkeley
Hilbert Space Representations of the annular(affine) Temperley
Lieb algebras and a conjecture of Freedman and Walker.
The annular TemperleyLieb algebra is spanned by noncrossing
diagrams in an annulus. Freedman and Walker conjectured a relationship
between the algebra in an annulus for an arbitrary TQFT and the
quantum double of the theory, and proved it for the SU(2) level
k theory. These ideas will be discussed with an emphasis on Hilbert
Space structure.

Martin Golubitsky,
University of Houston
Oscillations in Coupled Systems and Animal Gaits
Collins and Stewart noted that many quadruped gaits can be described
by spatiotemporal symmetries. For example, when a horse paces
it moves both left legs in unison and then both right legs and
so on. The motion is described by two symmetries: Interchange
front and back legs, and swap left and right legs with a halfperiod
phase shift.
Biologists postulate the existence of a central pattern generator
(CPG) in the neural system that sends periodic signals to the
legs. CPGs can be thought of as electrical circuits that produce
periodic signals and can be modeled by coupled systems of differential
equations with symmetries based on leg permuation.
In this lecture we discuss animal gaits; describe how periodic
solutions with prescribed spatiotemporal symmetry can be formed
in symmetric systems; construct a CPG architecture that naturally
produces quadrupedal gait rhythms; and make several testable predictions
about gaits.
This research is joint with Luciano Buono, Jim Collins, and Ian
Stewart.
Back to Top

Angus Macintyre, University of
Edinburgh
Various manifestations of the Frobenius map in model theory
Early work in logic by Tarski gave a precise meaning to the Lefshetz
Principle that algebraicgeometric statements true in sufficiently
high finite characteristic are true in characteristic zero.More
recent work has brought in the Frobenius maps (exponentiation
to a power of p),and tried to make sense of them in characteristic
zero.The principal result is that generic automorphisms of the
complex numbers are,essentially,limits of Frobenii.The proof depends
on the Weil Conjectures.The result has applications to the algebraic
theory of difference equations.
The Frobenius map on the Witt vectors is of basic importance in
many parts of algebra and number theory.Its model theory has been
thoroughly analyzed,and one now knows axioms for this Frobenius,in
principle allowing one to decide which difference equations are
solved by Frobenius. An analogue of the AxKochenErshov Theorem
has been proved,showing that as p goes to infinity the behaviour
of the Witt Frobenius converges to that of a feebler map on fields
of formal series over the algebraic closure of finite fields.
Back to Top

William Pulleyblank, IBM Research
Proteins, Petaflops and Algorithms
Computational biology is an important, rapidly growing
area of deep computing. The protein folding problem is one of
the most intriguing problems  how does a protein form a three
dimensional structure when it
is placed in water? Modeling this process goes far beyond the
capabilities of current supercomputers. I will discuss the problem
as well as different solution approaches currently being tried.
I will also discuss a project called Blue Gene which will build
a petaflop scale supercomputer suitable for one approach to this
problem within the next three years.
Back to Top

Chris Rogers, University of Bath
Monte Carlo valuation of American options
This paper introduces a `dual' way to price American options,
based on simulating the path of the option payoff, and of a judiciouslychosen
Lagrangian martingale. Taking the pathwise maximum of the payoff
less the martingale provides an upper bound for the price of the
option, and this bound is sharp for the optimal choice of Lagrangian
martingale. As a first exploration of this method, three examples
are investigated numerically; the accuracy achieved with even
very simpleminded choices of Lagrangian martingale is surprising.
The method also leads naturally to candidate hedging policies
for the option, and estimates of the risk involved in using them.
Back to Top

Karl Rubin, Stanford University
Ranks of elliptic curves
The rank of an elliptic curve is a measure of the number of solutions
of the equation that defines the curve. In recent years there
has been spectacular progress in the theory of elliptic curves,
but the rank remains very mysterious. Even basic questions such
as how to compute the rank, or whether the rank can be arbitrarily
large, are not settled.
In this lecture we will introduce elliptic curves and some of
the fundamental questions about them. The most interesting open
problems involve ranks, and we will discuss what is known, as
well as what is conjectured but not known, about them.
Some of this talk represents joint work with Alice Silverberg.


