| Noga Alon.
Disjoint paths, isoperimetric problems, and graph eigenvalues |
| Abstract:
The spectral properties of a graph are intimately related to its
structure. This can be applied in the study of discrete isoperimetric
problems and in the investigation of extremal and algorithmic questions
for graphs. I will discuss several recent examples illustrating this
theme. |
|
Manuel Blum. Can (Theoretical Computer) Science Get a Grip on Consciousness? |
| Abstract:
To come to grips with consciousness, I postulate that living entities in
general, and human beings in particular, are mechanisms... marvelous
mechanisms to be sure but not magical ones... just mechanisms. On this
basis, I look to explain some of the paradoxes of consciousness such as
Samuel Johnson's "All theory is against the freedom of the will; all
experience is for it."
I will explain concepts of self-awareness and free will from a mechanistic
view. My explanations make use of computer science and suggest why these
phenomena would exist even in a completely deterministic world. This is
particularly striking for free will.
The impressions of our senses, like the sense of the color blue, the sound
of a tone, etc. are to be expected of a mechanism with enormously many
inputs categorized into similarity classes of sight, sound, etc. Other
phenomena such as the "bite" of pain are works in progress. I show the
direction that my thinking takes and say something about what I've found and
what I'm still looking for. Fortunately, the sciences are discovering a
great deal about the brain, and their discoveries help enormously in guiding
and verifying the results of this work.
Power Point presentation |
| Richard Karp.
What Makes an Algorithm Great? |
| Abstract:
From time to time a new algorithm comes along that causes a
sensation in theoretical computer science or in an area of application
because of its resolution of a long-standing open question, its surprising
efficiency, its practical usefulness, the novelty of its setting or
approach, the elegance of its structure, the subtlety of its analysis or
its range of applications. We will give examples of algorithms that
qualify for greatness for one or more of these reasons, and discuss how to
equip students to appreciate them and understand their strengths and
weaknesses. Power Point presentation
|
| Mihalis Yannakakis.
Computational Aspects of Equilibria |
| Abstract:
Many models from a variety of areas involve the computation
of an equilibrium or fixed point of some kind.
Examples include Nash equilibria in games;
price equilibria in markets;
optimal strategies and the values of competitive games
(stochastic and other games);
stable configurations of neural networks;
analysis of the evolution of various types of dynamic stochastic models.
It is not known whether these problems can be solved in polynomial time.
Despite their broad diversity, there are certain common
computational principles that underlie different types of equilibria
and connect many of these problems to each other.
In this talk we will discuss some of these common principles
and the corresponding complexity classes that capture them;
the effect on the complexity of the underlying computational framework;
and the relationship with other open questions in computation.
|
