Groups, Graphs and Algorithms

Explore the intersection of group theory, graph theory, and algorithms in this 50-minute invited address by László Babai at the 2018 Joint Mathematics Meetings. Delve into topics such as graph irregularity, canonical good coloring, Johnson graphs, and string isomorphism. Examine the Genes algorithm and strategy, and learn about breaking symmetry in mathematical structures. Investigate the Share Hypothesis and its implications for algorithmic problem-solving. Gain insights into the connections between abstract mathematical concepts and their practical applications in computer science and algorithm design.

Intro
Graphs
NP
Graph irregularity
Canonical good coloring or equipartition
Multiplicative cost
Johnson graphs
Hidden Johnson graphs
String isomorphism
Genes algorithm
Genes strategy
Breaking symmetry
Theorem
Share Hypothesis
Strategy