SCIENTIFIC PROGRAMS AND ACTIVITIES

Speaker Abstracts

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.

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 Temperley-Lieb algebra is spanned by non-crossing 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.

Oscillations in Coupled Systems and Animal Gaits
Collins and Stewart noted that many quadruped gaits can be described by spatio-temporal 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 half-period 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 spatio-temporal 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 algebraic-geometric 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 Ax-Kochen-Ershov 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 judiciously-chosen 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 simple-minded 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.