- You are here:
- GT Home
- Home
- News & Events

Series: ACO Distinguished Lecture

This lecture is part of ACO25, a conference celebrating the 25th anniversary of the ACO Program. For more details about the conference please visit <a title="http://aco25.gatech.edu/" href="http://aco25.gatech.edu/">http://aco25.gatech.edu/</a>

In this talk we outline the core group theoretic routine,
the "Local Certificates" algorithm, underlying the
new Graph Isomorphism test. The basic
strategy follows Luks's group-theoretic divide-and-conquer
approach (1980). We address the bottleneck of Luks's
technique via local-global interaction based on a
new group theoretic lemma.
Undergraduate-level familiarity with the basic concept of
group theory (homomorphism, kernel, quotient group,
permutation groups) will be assumed.

Series: ACO Distinguished Lecture

This lecture is part of ACO25, a conference celebrating the 25th anniversary of the ACO Program. For more details about the conference please visit <a href="http://aco25.gatech.edu/" title="http://aco25.gatech.edu/">http://aco25.gatech.edu/</a>

One of the fundamental computational problems in the complexity
class NP on Karp's 1973 list, the Graph Isomorphism problem asks
to decide whether or not two given graphs are isomorphic. While
program packages exist that solve this problem remarkably
efficiently in practice (McKay, Piperno, and others), for
complexity theorists the problem has been notorious for its
unresolved asymptotic worst-case complexity.
In this talk we outline a key combinatorial ingredient of the
speaker's recent algorithm for the problem.
A divide-and-conquer approach requires efficient canonical
partitioning of graphs and higher-order relational structures.
We shall indicate why Johnson graphs are the sole obstructions
to this approach.
This talk will be purely combinatorial, no familiarity
with group theory will be required.

Series: ACO Distinguished Lecture

SHORT BIO:

Alexander Schrijver is Professor of Mathematics at the

University of Amsterdam and researcher at the Center for

Mathematics and Computer Science (CWI) in Amsterdam.

His research focuses on discrete mathematics and optimization,

in particular on applying methods from fundamental mathematics.

He is the author of four books, including 'Theory of Linear and

Integer Programming' and 'Combinatorial Optimization - Polyhedra

and Efficiency'.

He received Fulkerson Prizes in 1982 and 2003, Lanchester Prizes in

1987 and 2004, a Dantzig Prize in 2003, a Spinoza Prize in 2005,

a Von Neumann Theory Prize in 2006, and an Edelman Award in 2008.

He is a member of the Royal Netherlands Academy of Arts and Sciences

since 1995 and of three foreign academies, received honorary

doctorates from the Universities of Waterloo and Budapest, and was

knighted by the Dutch Queen in 2005.

Many graph invariants can be described as 'partition functions'
(in the sense of de la Harpe and Jones). In the talk we give an
introduction to this and we present characterizations of such
partition functions among all graph invariants. We show how
similar methods describe knot invariants and give rise to varieties
parametrizing all partition functions. We relate this to the
Vassiliev knot invariants, and show that its Lie algebra weight
systems are precisely those weight systems that are 'reflection
positive'. The talk will be introductory and does not assume any specific
knowledge on graphs, knots, or algebras.

Series: ACO Distinguished Lecture

Refreshments at 4PM in Lobby of Weber SST building

A few results and two general conjectures regarding analysis of
Boolean functions, influence, and threshold phenomena will be presented.
Boolean functions are functions of n Boolean variables with values in
{0,1}. They are important in combinatorics, theoretical computer
science, probability theory, and game theory.
Influence. Causality is a topic of great interest everywhere, and if
causality is not complicated enough, we can ask what is the influence
one event has on another one. Ben-Or and Linial studied influence
in the context of collective coin flipping---a problem in theoretical
computer science.
Fourier analysis. Over the last two decades, Fourier analysis of Boolean
functions and related objects played a growing role in discrete
mathematics, and theoretical computer science.
Threshold phenomena. Threshold phenomena refer to sharp transition in
the probability of certain events depending on a parameter p near a
critical value. A classic example that goes back to Erdos and Renyi, is
the behavior of certain monotone properties of random graphs.
Influence of variables on Boolean functions is connected to their
Fourier analysis and threshold behavior, as well as to discrete
isoperimetry and noise sensitivity.
The first Conjecture to be described (with Friedgut) is called the
Entropy-Influence Conjecture. (It was featured on Tao's blog.) It gives
a far-reaching extension to the KKL theorem, and theorems by Friedgut,
Bourgain, and the speaker.
The second Conjecture (with Kahn) proposes a far-reaching generalization of
results by Friedgut, Bourgain and Hatami.

Series: ACO Distinguished Lecture

Reception in the Atrium of the Klaus building at 4PM.

The concept of "strategic equilibrium," where each player's strategy is optimal against those of the other players, was introduced by John Nash in his Ph.D. thesis in 1950. Throughout the years, Nash equilibrium has had a most significant impact in economics and many other areas. However, more than 60 years later, its dynamic foundations - how are equilibria reached in long-term interactions - are still not well established.
In this talk we will overview a body of work of the last decade on dynamical systems in multi-player environments. On the one hand, the natural informational restriction that each participant may not know the payoffs and utilities of the other participants - "uncoupledness" - turns out to severely limit the possibilities to converge to Nash equilibria. On the other hand, there are simple adaptive heuristics - such as "regret matching" - that lead in the long run to correlated equilibria, a concept that embodies full rationality. We will also mention connections to behavioral and neurobiological studies, to computer science concepts, and to engineering applications.

Series: ACO Distinguished Lecture

There will be a reception in the Atrium of the Klaus building at 4PM.

Modeling data as high-dimensional (feature) vectors is a staple in Computer
Science, its use in ranking web pages reminding us again of its effectiveness.
Algorithms from Linear Algebra (LA) provide a crucial toolkit. But, for modern
problems with massive data, these algorithms may take too long. Random
sampling to reduce the size suggests itself. I will give a from-first-principles
description of the LA connection, then discuss sampling techniques developed
over the last decade for vectors, matrices and graphs. Besides saving time,
sampling leads to sparsification and compression of data.
Speaker's bio

Series: ACO Distinguished Lecture

Preceded with a reception at 4:10pm.

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.

Series: ACO Distinguished Lecture

RECEPTION TO FOLLOW

Fifty five years ago, two results of the Hungarian mathematicians, Koenig and Egervary, were combined using the duality theory of linear programming to construct the Hungarian Method for the Assignment Problem. In a recent reexamination of the geometric interpretation of the algorithm (proposed by Schmid in 1978) as a steepest descent method, several variations on the algorithm have been uncovered, which seem to deserve further study.
The lecture will be self-contained, assuming little beyond the duality theory of linear programming. The Hungarian Method will be explained at an elementary level and will be illustrated by several examples.
We shall conclude with account of a posthumous paper of Jacobi containing an algorithm developed by him prior to 1851 that is essentially identical to the Hungarian Method, thus anticipating the results of Koenig (1931), Egervary (1931), and Kuhn (1955) by many decades.