# 75th Anniversary Celebration Plenary Lectures

Celebrates

Celebrates

Celebrates

### Warren Weaver Hall

251 Mercer St.

New York, NY 10012

## 75th Anniversary Celebration

**Plenary Talks**

Friday, May 6, 2011

Warren Weaver Hall, Room 109

**9-9:45**

**Leslie Greengard** (NYU), *Fast algorithms and potential theory in scientific computing*

Over the last two decades, fast algorithms based on potential theory have brought a variety of large-scale calculations in computational physics within practical reach. In this lecture, we will provide an overview of these methods and discuss their applications to electromagnetics, acoustics, elasticity, and fluid dynamics. We will also present some recent results in the theory of electromagnetic scattering that extend the earlier work of Blank, Friedrichs, and Grad.

**10:00 – 10:45 **

**Assaf Nao**r (NYU),* Quantitative geometry and efficient classification procedures*

This talk will illustrate to non-experts the use of geometric methods to design efficient partitioning algorithms for discrete objects or, in some cases, to prove that such algorithms must fail to perform well. These connections show that combinatorial optimization problems are intimately related to classical questions in continuous geometry, and we will describe some recent progress on old questions that translate to the best known results on algorithmic problems of central interest. This talk will provide an introduction to geometric aspects of computational complexity via an examination of specific examples. No specialized background will be required.**11:00 – 11:45 **

**Sylvia Serfaty (Paris 6/NYU)**, *Renormalized energy, Abrikosov lattice, and random matrices *

In joint work with Etienne Sandier, we introduced the "renormalized energy," a Coulombian interaction between points in the plane (it was derived as a limit of the Ginzburg-Landau model of superconductivity). We also introduced a one-dimensional analogue.

I will present the function, its properties, and the question of its minimization as well as its link with the "Abrikosov" hexagonal lattice. I will also describe results with Etienne Sandier and others with Alexei Borodin, which connect it with log gases and random matrices.

**12:00 – 2:00: Break**

**2:00 – 2:45 **

**Lloyd N. Trefethen** (Oxford), *Robust rational interpolation, Padé approximation, and extrapolation of sequences*

Approximating functions or data by polynomials is an everyday tool, starting with Taylor series. Approximating by rational functions can be much more powerful, but also much more troublesome. In different contexts rational approximations may fail to exist, fail to be unique, or depend discontinuously on the data. Some approximations show forests of seemingly meaningless pole-zero pairs or "Froissart doublets," and when these artifacts should not be there in theory, they often appear in practice because of rounding errors on the computer. Yet for some applications, like extrapolation of sequences and series, rational approximations are indispensable.

In joint work with Pedro Gonnet and Ricardo Pachon we have developed an elementary method to get around most of these problems in rational interpolation and least-squares fitting, based on the singular value decomposition. The talk will include many examples.**3:00 – 3:45 **

**Shafi Goldwasser **(MIT/Weizmann),* The Evolution of a Proof*

The Courant Institute is celebrating its 75th birthday. Today I will talk about two more birthdays of a personal nature that took place this (academic) year. The paper with Micali and Rackoff on "Zero Knowledge Interactive proof" appeared 25 years ago, and a paper with * ** ** ** *Feige, Lovasz, Safra, and Szegedy on "Interactive Proofs and the Hardness of Approximating Cliques" 20 years. I will describe the evolution of the notion of probabilistic and interactive proof, touch (ever so) briefly on subsequent influences on cryptography and complexity theory, and describe new challenges.**4:00 – 4:45**

**Dennis Shasha** (NYU), *The Changing Nature of Invention in Computer Science*

What drives inventions in computing? Necessity seems to play only a minor role. Anger at the way things are is much more powerful, because it leads to easier ways to work (the invention of new computer languages). A general dissatisfaction with the practical or theoretical structure of the world can open up whole new approaches to problems (complexity theory and cryptography). Finally, a genuine collaboration between people and machines can lead to an entirely new kind of engineering for devices that will travel to far-off planets or to hostile environments.

The talk will discuss the work of several inventors in computing and engineering, their inventions, and how they came up with them and how they plan to come up with more in the future. The ensuing discussion will address the fundamental nature of invention in a world partly populated by intelligent machines.**5:00 – 5:45**

**Tadashi Tokieda** (Cambridge),* Linguistic curiosities*

[Abstract Forthcoming]

*A reception will follow in the 13th floor commons.*