Seminars and Colloquia by Series

Group theory and the Graph Isomorphism problem

Series
ACO Distinguished Lecture
Time
Tuesday, January 10, 2017 - 11:05 for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Laszlo Babai – University of Chicago

Please Note: This lecture is part of ACO25, a conference celebrating the 25th anniversary of the ACO Program. For more details about the conference please visit http://aco25.gatech.edu/

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.

Graph Isomorphism: The emergence of the Johnson graphs

Series
ACO Distinguished Lecture
Time
Monday, January 9, 2017 - 16:30 for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Laszlo Babai – University of Chicago

Please Note: This lecture is part of ACO25, a conference celebrating the 25th anniversary of the ACO Program. For more details about the conference please visit http://aco25.gatech.edu/

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.

Graphs, Knots, and Algebras

Series
ACO Distinguished Lecture
Time
Tuesday, January 28, 2014 - 16:30 for 1 hour (actually 50 minutes)
Location
Clough Commons Room 152
Speaker
Alexander Schrijver – University of Amsterdam and CWI Amsterdam

Please Note: 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.

Analysis of Boolean functions, influence and noise

Series
ACO Distinguished Lecture
Time
Thursday, September 13, 2012 - 16:30 for 1 hour (actually 50 minutes)
Location
Weber SST Room 2
Speaker
Gil Kalai – Hebrew University of Jerusalem

Please Note: 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.

Game Dynamics and Equilibria

Series
ACO Distinguished Lecture
Time
Thursday, March 1, 2012 - 16:30 for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Sergiu Hart – Hebrew University of Jerusalem

Please Note: 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.

Vectors, Sampling and Massive Data

Series
ACO Distinguished Lecture
Time
Tuesday, November 1, 2011 - 16:30 for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Ravi Kannan – Microsoft Research India

Please Note: 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

Can (Theoretical Computer) Science come to grips with Consciousness

Series
ACO Distinguished Lecture
Time
Saturday, October 24, 2009 - 17:00 for 1 hour (actually 50 minutes)
Location
LeCraw Auditorium, College of Management
Speaker
Manuel Blum – Computer Science, Carnegie Mellon University

Please Note: 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.

Reflections on a favorite child

Series
ACO Distinguished Lecture
Time
Thursday, November 13, 2008 - 16:30 for 2 hours
Location
Klaus 1116
Speaker
Harold W. Kuhn – Princeton University

Please Note: 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.