You are here


SundayFeb 19, 202311:00
The Chaim Leib Pekeris Memorial Lecture
Speaker:Alexander GiventalTitle:A belated introduction to mirror symmetryAbstract:opens in new windowin html    pdfopens in new window
The mirror conjecture is the somewhat vague yet highly inspiring and influential observation (made by string theorists some three decades ago) that two disparate mathematical fields --- one, called "symplectic topology" and studying discrete invariants of phase spaces in classical mechanics, the other, called "complex geometry" and studying deformations of complex structures on some other such phase spaces --- are in some sense equivalent to each other. In this talk, I plan to trace the history of symplectic topology and the mirror conjecture back to Pascal and even Euclid, and then illustrate the mirror phenomenon in a quite intricate "pre-historic" example: Arnold's strange duality between the so-called 14 exceptional singularities.
TuesdayFeb 05, 201911:00
The Chaim Leib Pekeris Memorial Lecture
Speaker:Tim RoughgardenTitle:How Computer Science Informs Modern Auction DesignAbstract:opens in new windowin html    pdfopens in new windowDolfi and Lola Ebner Auditorium
Over the last twenty years, computer science has relied on concepts borrowed from game theory and economics to reason about applications ranging from internet routing to real-time auctions for online advertising. More recently, ideas have increasingly flowed in the opposite direction, with concepts and techniques from computer science beginning to influence economic theory and practice. In this lecture, Tim Roughgarden will illustrate this point with a detailed case study of the 2016-2017 Federal Communications Commission incentive auction for repurposing wireless spectrum. Computer science techniques, ranging from algorithms for NP-hard problems to nondeterministic communication complexity, have played a critical role both in the design of the reverse auction (with the government procuring existing licenses from television broadcasters) and in the analysis of the forward auction (when the procured licenses sell to the highest bidder).
WednesdayFeb 07, 201811:00
The Chaim Leib Pekeris Memorial Lecture
Speaker:Professor Christos PapadimitriouTitle:A Computer Scientist Thinks about the BrainAbstract:opens in new windowin html    pdfopens in new windowDolfi and Lola Ebner Auditorium

Understanding the ways in which the Brain gives rise to the Mind (memory, behavior, cognition, intelligence, language) is the most challengingproblem facing science today. As the answer seems likely to be at least partly computational, computer scientists should work on this problem --- except there is no obvious place to start. I shall recount recent work (with W. Maass and S. Vempala) on a model for the formation and association of memories in humans, and reflect on why it may be a clue about language.

SundayJan 29, 201711:00
The Chaim Leib Pekeris Memorial Lecture
Speaker:Laszlo BabaiTitle:Hidden irregularity versus hidden symmetryAbstract:opens in new windowin html    pdfopens in new windowEbner Auditorium

Symmetry is defined in terms of structure-preserving transformations (automorphisms); regularity in terms of numerical invariants. Symmetry always implies regularity but there are many highly regular combinatorial objects (such as "strongly regular graphs") with no symmetry.  The opposite of irregularity is regularity, not symmetry.  Yet we show that in a well-defined sense, the opposite of hidden irregularity is hidden symmetry, and in fact hidden symmetry of a particularly robust kind.
The symmetry of a circle is easily destroyed: just "individualize" two non-opposite points -- color one of them red, the other blue -- and all the symmetry is gone.   In fact, the resulting structure is completely irregular: every point is uniquely identified by a pair of numerical invariants, namely, its pair of distances to the two individualized points. We shall say that the circle has a high degree of hidden irregularity.
In contrast, Johnson graphs are objects with robust symmetry: individualizing a small number of vertices of a Johnson graph hardly makes a dent in its symmetry.  
Recent work on the algorithmic problem of Graph Isomorphism has revealed that Johnson graphs are unique in this regard: Every finite relational structure of small arity either has a measurable (say 10%) hidden irregularity (revealed by individualizing a polylogarithmic number of elements) or has a large degree of hidden symmetry, manifested in a canonically embedded Johnson graph on more than 90% of the underlying set.
This dichotomy is the key Divide-and-Conquer tool in recent progress on the worst-case complexity of the Graph Isomorphism problem.
This subject is purely combinatorial and does not require advanced mathematical apparatus.  The group theoretic aspects of the new Graph Isomorphism test will be discussed in a follow-up seminar on January 30.

TuesdayJun 14, 201611:30
The Chaim Leib Pekeris Memorial Lecture
Speaker:Gil KalaiTitle:The Quantum Computer PuzzleAbstract:opens in new windowin html    pdfopens in new windowDolfi and Lola Ebner Auditorium

Quantum computers are hypothetical devices, based on quantum physics, which would enable us to perform certain computations (among them some that Chaim Leib Pekeris pioneered) hundreds of orders of magnitude faster than digital computers. This feature is coined “quantum supremacy.” We start the lecture with a gentle introduction to computing - classical and quantum, with basic notions of computational complexity, and with the vision of quantum computers. 

A main reason for concern regarding the feasibility of quantum computers is that quantum systems are inherently noisy. We will explain what is "noise" and describe an optimistic hypothesis regarding quantum noise that will allow quantum computing and a pessimistic hypothesis that won’t. The remarkable progress witnessed during the past two decades in the field of experimental physics of controlled quantum systems places the decision between the pessimistic and optimistic hypotheses within reach.  On the optimistic side, one aspect or another of  quantum supremacy might be seen by experiments in the near future: by implementing quantum error-correction or by systems of free bosons or by exotic new phases of matter called anyons or by quantum annealing, or in various other ways.

In the lecture I will explain my pessimistic line of research and here is a brief summary of my view:  understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

We will rely on the theory of noise-sensitivity and stability developed with Benjamini and Schramm in the late 90s and on recent work with Guy Kindler related to the mysterious gap between permanents and determinants (or, in other words, between bosons and fermions).

WednesdayJun 17, 201511:00
The Chaim Leib Pekeris Memorial Lecture
Speaker:Stanislav Smirnov Title:The Ising Model of a Ferromagnet from 1920 to the Present DayAbstract:opens in new windowin html    pdfopens in new windowDolfi and Lola Ebner Auditorium

The Ising model is an archetypical model of the order-disorder phase transition: though simple to formulate, it exhibits a complex behavior, much like the real-world phenomena in solid-state physics, ferromagnetism, chemistry, biology, computer science.

In 1920 the physicist Wilhelm Lenz proposed to model ferromagnetic materials by a lattice of plus-minus spins with interacting neighbors. His student Ernst Ising solved the model in dimension one four years later. The one-dimensional behavior turned out to be trivial, with no phase transition when the interaction strength changes, and for a decade people searched for other possible models. However, a ferromagnetic phase transition was established by Rudolf Peierls in higher dimensions, and in 1944 Lars Onsager famously calculated the free energy for the Ising model in two dimensions.

Since then the Ising model became widely studied, as it exhibits complicated phase transition behavior, yet allows a very detailed analysis in dimension two. We will give a historical introduction to the model, and then describe some recent results.