The SPAMS Schedule - Fall 1999

abstrAct: Given a set S of 2n+3 points in general position in the plane, we say that a circle is "point-splitting" if it has 3 points of S on its circumference, n points of S inside it, and the remaining n points of S outside it.

The notion of a point-splitting circle is fundamental to all of mathematics.

It is known that any set S has at least one point-splitting circle; it is natural to ask how many point-splitting circles it might have. In this talk, we present the surprisingly simple answer to this and other related questions.

Abstract (whaddya mean you can't read Latex yet):

We will consider two different probabilistic models of percolation, namely {\it bond percolation} and {\it first-passage percolation}. Both models describe the passage of fluid through a porous medium.

{\bf Bond percolation.} Turn cubic lattice ${\mathbb Z}^d$ into a graph ${\mathbb L}^d$ by adding the edges connecting adjacent vertices. One can view the edges of this graph as an elaborate system of channels similar to a sponge. Water can pass through some of the channels, but there are channels that are cluttered (closed). We will assume that each edge is {\it open} with probability $p$ and {\it closed} with probability $1-p$ independently on other edges.

Is it possible that the origin is connected to an infinite set of vertices by the network of open paths? How many vertices will get wet if there is a source of water at the origin? We will address these and many other questions.

{\bf First-passage percolation.} In this model we associate to each edge $e\in {\mathbb L}^d$ a {\it random variable $X_e$}, the amount of time water would take to flow along this edge. If edges $e$, $f$,..,$g$ form a path, it will become wet by the time $X_{e}+X_{f}+...+X_{g}$. Assuming that at time $T=0$ only the origin is wet, which vertices will become wet by the time $n$? When on average will a given vertex become wet?

Abstract: After a brief review of some basic facts about convex polytopes, we will look at some examples of interesting polytopes, the most amazing of which are the cyclic polytopes. The cyclic polytopes have a few interesting properties whose proofs are very clever. During the second half of the talk we will learn to visualize four dimensional objects. You think that's impossible? Here is a quote which is equally likely to discourage you as to encourage you to come to the talk:

Here, however, a word of warning may be in order: do not try to visualize n-dimension objects for n >= 4. Such an effort is not only doomed to failure--it may be dangerous to your mental health. (If you do succeed, then you are in trouble.)

--Chvatal

Abstract: We explain what metric spaces are, explain why L1 is a particularly cool metric, and then show that every finite metric space can be quickly embedded in L1 with O(log n) distortion (we define that too). We will then explain how this was used to solve an open problem in theoretical computer science in 1994. This is popularly known as the Linial London Rabinovich result. It's cool, and it's very accessible.

Abstract: We will look at the definite summation of a hypergeometric term and find a closed form or prove that no closed form exists. This algorithm will seem very familar to those who have studied the Wilf-Zeiberger Method as they are very closely related. We will end by looking at one particular application I used.

Abstract: The low-degree test is a way to check if a given multivariate function over a finite field is actually a polynomial of specified degree. This is done in a probabilistic fashion, so that the test will say yes with low probability if there is no polynomial that closely approximates the function (i.e. is equal to it at a large number of points). The test finds applications in proving various bounds on the hardness of approximating computational problems. We will see one particular analysis of the basic test. All the work on this problem is basically to improve the analysis, rather than change the nature of the test.

Abstract: Boosting is a technique from computational learning theory for converting a low-accuracy learning algorithm into a high-accuracy one. Boosting algorithms are used extensively in practise and are also interesting from a theoretical point of view.

In this talk we will give an overview of what boosting is and how it works and give two theoretical computer science problems where boosting is useful-- one in complexity theory and one in learning theory. No prior knowledge of computational learning theory will be assumed.

Abstract: The time-discounted reward maximization problem on multiarmed bandits has been intensely studied by probabilists, and has been completely solved by John Gittins, via what is now known as "the Gittins indices". In the case of the discrete problem, we have found a way to extend his results to time-preserved, and in some cases, even to time-amplified rewards.

We present a simple, discrete version of the problem, together with some of the results, a polynomial-time decision-making algorithm, and some applications on particular instances of multiarmed bandits -- weighted graphs.

Abstract: There are different kinds of pattern in plants. A special family of patterns that has attracted researchers is known as phyllotactic patterns that are formed whenever a vascular plant repeatedly leaves, bractae, florets, etc. These patterns are directly related to the Fibonacci series and the golden mean. There have been many theories for these problems, which can be roughly characterized as geometrical approaches, and dynamical/ physiological approaches. Here we will consider the beginnings of a model based on the elasticity theory couple to growth.

No background required. I will describe the problem and the basic ideas involved in approximation algorithms before tackling the main topic. Work with Santosh Vempala.

Abstract: One of the great mysteries of fluid dynamics that is greatly studied yet still poorly understood is turbulence. What we usually think of as turbulence, i.e. chaotic mixing, falls within the classification of three dimensional turbulence.

In this seminar I plan to introduce the idea of two dimensional turbulence and show how within this theory coherent structures like vortices can actually grow instead of get torn apart, as our intuition of turbulence would have us believe.

Also, I hope to touch upon how the theory of two dimensional turbulence might in fact explain the formation of bands on Jupiter and the other gas giants. Throughout the talk focus will be placed not on the equations themselves as much as the physics behind them.