Algorithms, Combinatorics and Optimization Seminar - Ryan O'Donnell
September 3, 2026 3:00PM—4:00PM
Location:
In Person
-
Wean 8220
Speaker:
RYAN O'DONNELL,
Professor
Computer Science Department
Carnegie Mellon University
https://www.cs.cmu.edu/~odonnell/
A non-sofic group
Thursday, September 3, 2026, 3 – 4pm Say you have the Cayley graph G of an infinite group. Wouldn't it be nice if, for every R, there was a finite graph that looked like G in the R-neighborhood of every vertex? Failing that, wouldn't it be nice if this held for a 1-o(1) fraction of vertices? That's what it means for G to be sofic. Well, it's not always meant to be; per OpenAI (and using tools by Gábor Kun and Andreas Thom), there exists a non-sofic group. I'll try to tell you about it; it's about 90% spectral graph theory.
4:00 pm → Jane Street-sponsored tea and cookies in the Math Lounge, Wean 6220 (bring your mug!).
Event Type: Seminars
Room Number: In Person
Building: Wean 8220
Speaker's Name: RYAN O'DONNELL
Speaker Website: www.cs.cmu.edu…
Speaker's Professional Title: Professor, Computer Science Department, Carnegie Mellon University
Talk Title: A non-sofic group
For More Information: rkrueger@andrew.cmu.edu
Affiliations: Computer Science Department (CSD), Tepper School of Business
Organization(s): School of Computer Science, Department of Mathematical Sciences
Event Website Title: Event Website
Event Website URL: aco.math.cmu.edu…
For More Information:
rkrueger@andrew.cmu.edu