A TTIC Talk

Julia Chuzhoy is a professor at TTIC—the Toyota Technological Institute at Chicago. She is giving a talk this Friday at TTIC, 6045 S. Kenwood Avenue in the 5th Floor, Room 530. Her title is, “On Fixing Some Issues with Expanders.” An associated paper by her, however, has a much longer title.

Ken and I wrote a post on her work a while ago in 2015. That was on a joint result with Chandra Chekuri. He is the Paul and Cynthia Sayles Professor at UIUC.

A Well-Connected Talk

I am visiting TTIC till Friday and have to then return to home. So I will have to miss her talk. I hope it is well-connected enough that some of it gets back to me. Let me know how it goes.

I believe the main thrust of her talk should interest many since it attends to an important issue. The concept of expander graph is wonderful and has great connections to other areas of combinatorics, but the condition is costly to instantiate and verify and may go beyond what many algorithms truly need for good performance. Her method to weaken-and-sidestep the requirements, centered around a notion of well-connected graphs, should help extend applications of the general technology. She says:

We believe that the use of well-connected graphs instead of expanders in various dynamic distance-based problems (such as APSP in general graphs) has the potential of providing much stronger guarantees, since we are no longer necessarily restricted to superlogarithmic approximation factors.

Open Problems

Enjoy the talk. I think the results that follow from weakening expanders could be quite powerful.