What is Floer homology and what is it good for?

Property `Tau' and its Applications in Combinatorics and Geometry

Property '$\tau$' (which is related to Kazhdan Property T in representation theory) has surprising applications to several areas in Math and CS. We will introduce it and discuss some of these applications, including: (1) to problems in combinatorics - e.g., Margulis' expanding graphs: (2) to producing efficient methods of generating random elements in groups; (3) to a conjecture of Thurston on finite covers of hyperbolic manifolds.

Short Nonlinear Hyperbolic Pulse Propagation

The propagation of short pulse solutions of nonlinear hyperbolic systems is discussed in the limit of pulse length tending to zero. Amplitudes are scaled so that nonlinear effects are present in the leading terms. Recent results concern the scalings of geometric optics, diffractive geometric optics, and, with much less complete results, the passage of pulses through focal points. The fact that pulses have small support eases their analysis. The fact that the support of their Fourier Transform is very broad makes their analysis difficult. Ultra short laser technology outstrips mathematical analysis at the present time.

Fluid Dynamical Limits for the Boltzmann Equation

The endeavor to understand how fluid dynamical equations can be derived from kinetic theory goes back to the founding works of Maxwell and Boltzmann. Most of these derivations have been well understood at several formal levels for some time, and yet their full mathematical justifications are still missing. This talk will introduce this general problem and describe recent works in which the acoustic and incompressible Stokes limits are now globally establish for the classical Boltzmann equation considered over any periodic spatial domain of dimension two or more. Recent partial results regarding incompressible Navier-Stokes and incompressible Euler limits will also be discussed.

Information Theoretic Everlasting Encryption

Shannon has proved fifty years ago that in order to ensure information theoretic secrecy in encryption, the sender and receiver must share a secret key with entropy greater than the entropy of the message to be encrypted. Maurer has suggested in 1990 the bounded storage model for encryption as a way to overcome the Shannon barrier. We shall present a practical encryption scheme based on the bounded storage model, and prove that it is information theoretically secure against the strongest attacks by an adversary with unlimited computing power. The talk will survey fundamental cryptographic concepts and will be self-contained.

The fractal nature of the moduli of riemannian metrics on a manifold

Our focus is on the space of Riemannian metrics (up to isometry) on a given manifold of dimension at least five, and we study its geometry "Morse theoretically" by considering critical points of certain functionals. We show the existence of many critical points and study their locations.

An interesting feature is that we apply methods from computability theory to show the existence of many basins, which themself have basins, and so on. Ultimately, the picture one gets seems to be that of a "large scale fractal".

This is a joint work with Alex Nabutovsky.

Aerodynamic Shape Optimization via Control Theory and CFD (Lecture starts at 3:15, tea time: 3pm)

Geometry of the Group of Contact Transformations

KdV and Geometry

The Multilevel Plane Wave Time Domain Algorithm: Applications in Electromagnetic Scattering and FDTD Grid Truncation

This presentation will highlight different applications of plane wave time domain (PWTD) algorithms, viz. time domain (wave equation) extensions to the frequency domain (Helmholtz equation) fast multipole method, which permit the fast evaluation of transient wave fields generated by bandlimited sources. First, I will review the PWTD scheme and describe its incorporation into a time domain integral equation (TDIE) solver for analyzing electromagnetic scattering from perfectly conducting bodies. Classical TDIE solvers are notoriously costly as their computational complexity scales as O(N_s^2) per time step for a scatterer that is modeled in terms of N_s spatial unknowns. I will show that the computational cost of analyzing transient scattering phenomena using a multilevel PWTD enhanced TDIE solver scales as O(N_s log^2(N_s)) per time step. Second, I will describe PWTD-based kernels for truncating meshes used by differential equation based, open region wave equation solvers. Global mesh truncation schemes require the evaluation of retarded-time boundary integrals (RTBIs) and can be applied on boundaries conformal to the scatterer surface. This is unlike local boundary conditions that have to be imposed on convex surfaces. Unfortunately, the evaluation of RTBIs using classical methods is prohibitively expensive. Again, I will show that this computational bottleneck can be alleviated by employing the multilevel PWTD algorithm.

Vorticity in the Ginzburg-Landau Model of Superconductivity.

 
Monday March 27    Avi Wigderson, Institute for Advanced Study & Hebrew University (Lecture to be given in Room 109)
 
Note: This is a Joint Mathematics-Computer Science Colloquium, to be held in Room 109.

Some Insights of Computational Complexity Theory.

Computational complexity theory has been one of the most exciting fields of scientific research over the last few decades. This research studies the power of feasible computation,and is guided by a few clear and focused questions, deeply motivated on scientific, practical and philosophical grounds, like the P vs NP problem, and the questions on the power of randomized and quantum computation.

While these problems are far from resolved, Complexity Theory was able to offer fresh rigorous definitions to some central notions which naturally (or less so) arise from these questions, and unveil many rich and beuatiful conncetions between them.

In this general survey, I would like to probe some of the unique features and insights of the complexity theory viewpoint. This will be done by considering how (and why) notions which intrigued people for centuries or even millenia (like Knowledge,Randomness, Cryptography, Learning, Proof, and naturally,Computation), reveal new dimensions, and are suprisingly linked together, when viewed from our special Computational Complexity glasses.

Overall title: Nonlinear problems arising from economic theory.

Lecture two (for 4/11) - Variational problems with convexity constraints

Abstract
 

These lectures aim at describing new mathematical problems arising from economic theory. In the first one, we will show that the demand functions arising from the utility-maximization model of microeconomics must satisfy certain systems of nonlinear PDE, for which we shall give local existence results. In the second one, we will show how informational assymetry in contract theory leads to variational problem with global convexity constraints; we shall show existence and regularity of solutions, and give the Euler equation.

Boundary layer theory and zero-viscosity limit of Navier-Stokes equation.

 
Monday April 24    L. N. Trefethen, Oxford University

Random nonhermitian matrices (joint work with Mark Embree).

 
Friday April 28    William Kahan, University of California at Berkeley
 
Note: This is a Joint Computer Science-Mathematics Colloquium, to be held in Room 101 at 11:30 am; Refreshments at 11:00 in WWH 1301. Host: Chee Yap (yap@cs.nyu.edu).

Ruminations on the Design of Floating-Point Arithmetic.

Floating-point can be understood better now than half a century ago. But the benefit of better understanding cannot reach computer programmers and users, most of them unwitting users of floating-point, unless floating-point providers (implementors of hardware and of programming languages) attend to vastly many details. These seem unfairly burdensome because nobody else cares about more than a few of them. Which few? Each detail matters in somebody's program upon which others (perhaps we) may depend; but who knows? Disregarding any one detail will undermine the coherence of the rest of them and thus harm the whole community of floating-point users. The details descend from specifications for floating-point hardware and for its use by programming languages most of which, like Java, still disregard inconvenient details although they are implied by a few accidental constraints (like bus-widths) and by a short list of guiding principles paramount among which is Intellectual Economy. Alas, this crucial principle too much resembles pornography:

I don't know what it is, but

I hope to recognize it if I see it.

Recent progress in high performance and high accuracy linear algebra algorithms -- Throwing away information for fun and profit.

Solving systems of linear equations, and finding eigenvalues of symmetric matrices are standard problems that arise in many mathematical modeling problems. Solutions have existed for a long time, but these solutions are no longer good enough, because the demands of applications keep growing to larger problems, and to more ``sensitive'' problems that require higher accuracy. In addition, the larger problems in turn require large parallel computers where communication is much more expensive than computation.

We highlight several new algorithms under development, all of which have solved linear systems and eigenvalue problems many times larger, more sensitive or more quickly than before. Though these algorithms are all very different, one common mathematical approach distinguishes them from their predecessors: The new algorithms deliberately throw away just enough information about the problem to run both efficiently yet accurately. In contrast, their predecessors would either have to use much higher precision, send many more messages, or do many more operations to get the same answers.

Finally, we also describe one problem, computing reliable error bounds, where willingness to sacrifice information and accuracy provably does not help the complexity.

Partially random graphs and small world networks.

It is almost true that any two people in the US are connected by less than six steps from one friend to another. What are models for large graphs with such small diameters?

Watts and Strogatz observed (in Nature, June 1998) that a few random edges in a graph could quickly reduce its diameter (longest distance between two nodes). We report on an analysis by Newman and Watts (using mathematics of physicists) to estimate the diameter with an N-cycle and M random shortcuts, 1 << M << N.

We also study a related model, which adds N edges around a second (but now random) cycle. The average distance between pairs becomes nearly A log n + B. The eigenvalues of the adjacency matrix are surprisingly close to an arithmetic progression; for each cycle they would be cosines, the sum changes everything.

We will discuss some of the analysis (with Alan Edelman and Henrik Eriksson at MIT) and also some applications. We also report on the surprising eigenvalue distribution for trees (large and growing ) found by Li He and Xiangwei Liu. And a nice work by Jon Kleinberg discusses when the short paths can actually be located efficiently.

Last modified: March 29, 2000