Tuesday, September 25, 2018

Lance and Bill go to Dagstuhl: The Riemann Edition

Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Computation Complexity. Say hi Bill.

Bill: Hi Bill. So Lance are you disappointed we didn't go to Heisenberg for the Michael Atiyah talk claiming a solution to the Riemann Hypothesis.

Lance: I knew how fast I was going but I got lost going to Heisenberg. I think you mean the Heidelberg Laureate Forum a 100 miles from here. From what I heard we didn't miss much. For those who care here is the video, some twitter threads and the paper.

Bill: Too bad. When I first heard about the claim I was optimistic because (1) László Babai proved that graph isomorphism is in quasipolynomial-time at the age of 65 and (2) since Atiyah was retired he had all this time to work on it. Imagine Lance if you were retired and didn't have to teach or do administration, could you solve P vs NP? (This gets an LOL from Nutan Limaye)

Lance: I'll be too busy writing the great American novel. Before we leave this topic, don't forget about the rest of the Laureate Forum, loads of great talks from famous mathematicians and computer scientists. Why didn't they invite you Bill?

Bill: They did but I rather be at Dagstuhl with you to hear about lower bounds on matrix multiplication from Josh Alman. Oh, hi Josh I didn't see you there.

Josh: Happy to be here, it's my first Dagstuhl. I'm flying around the world from Boston via China to get here. Though my friends say it's not around the world if you stay in the Northern hemisphere. They are a lot of fun at parties. But not as much fun as matrix multiplication.

Bill: So Josh, what do you have to say about matrix multiplication. Is is quadratic time yet?

Josh: Not yet and we show all the current technique will fail.

Bill: Wouldn't Chris Umans disagree?

Kathryn Fenner: You shouldn't pick on Canadians [Ed note: Josh is from Toronto]. Pick on students from your own country.

Josh: (diplomatically) I think Chris Umans has a broader notion of what counts as known methods. There are some groups that aren't ruled out but we don't know how to use them.

Chris: Very well put. The distinction is between powers of a fixed group versus families of groups like symmetric groups. The later one seems like the best place to look.

Lance: Thanks Chris. Josh, what are your impressions of Dagstuhl so far?

Josh: I like the sun and grass. I wish it was easier to get here.

Lance: This is only the first day. You haven't even found the music room yet, past the white room, past the billiard room where Mr. Green was murdered with the candlestick. Oh hi Fred Green. Luckily Dr. Green is still alive. I remember my first Dagstuhl back in February of 1992.

Josh: Two months before I was born.

Lance: Way to make me feel old.

Bill: You are old.

Lance: You are older. Believe it or not six from that original 1992 meeting are here again this week: The two of us, Eric Allender, Vikaurum Arvind, Uwe Schöning and Jacobo Torán. Amazing how accents show up as we talk.

Bill: What did I sleep through this morning before Josh's talk?

Lance: Amnon Ta-Shma talked about his STOC 2017 best paper and Noga Ron-Zewi showed some new results on constructive list-decoding.

Bill: Let's do this again later in the week. Lance, takes us out.

Lance: In a complex world, best to keep it simple.


  1. Its affordable for Atiyah to call urgent summit,
    but not for me... :-))
    However according to well-known proverb:
    "Water streams dissolve stones..."


    1. Does you paper play the role of the water stream or of the stone? (just a joke :-)