Muffin Math

Lance: It's Friday afternoon and the Dagstuhl workshop has ended. We have some time before we need take off so how about one final typecast.

Bill: Always a good idea.

Lance: First the exciting news, Nitin Saxena won the Shanti Swarup Bhatnagar prize for 2018,

Nitin Saxena

according to the many Indians at Dagstuhl, the most prestigious science prize in the country. The awards were announced on Wednesday during the workshop. He's the S in AKS.

Bill: That's really impressive. He was only two-years old when AKS had log-depth sorting networks.

Lance: Bill, you moron. You're thinking of Ajtai-Komlós-Szemerédi. I'm talking Agrawal-Kayal-Saxena Primes in P, topic of my second ever blog post. Nitin, an undergrad at that time, didn't just sit on his laurels--he has had awesome results on algebraic circuit complexity that truly justify this prize.

Bill: Well congrats to Nitin. Moving on, let's talk math.

Lance: We're at Dagstuhl so we have to call it computer science.

Bill: Ronen Shaltiel gave a great but depressing talk, Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs.

Lance: Nobody sings the Dagstuhl Blues.

Bill: Suppose you had a hard function and want to covert it to a harder function, known in the biz as hardness amplification. For constant depth circuits we have hardness results but no known process for amplification. For larger classes, like constant depth circuits with threshold gates, we do know ways to amplify.

Lance: But we have not hardness results there? Where are you going with this?

Bill: Ronen put it nicely, "We can only amplify hardness where we don't have it". Ronen and his colleagues proved results along those lines. Lance, does that depress you.

Lance: Not as much as the sprained ankle that made me miss that talk. My turn to pick a favorite talk. I loved Michael Forbes Hitting Sets for the Closure of Small Circuits. You take algebraic circuits with a parameter epsilon and take the limit as epsilon goes to zero. Forbes and Amir Shpilka show a PSPACE algorithm to find small sets containing non-zeros of these functions. These kinds of functions are studied in the GCT approach to lower bounds.

Bill: What lower bounds is this aiming to solve?

Lance: Showing the computation difference between the determinant and the permanent.

Josh Alman: You've left out the most exciting part of the conference.

Bill and Lance: So Josh, what was that?

Josh Alman: The world debut debut performance of Stud Muffin and Smilin' Sam singing "Do You Work on Muffin Math?"

Lance: That awesome duo looks familiar Bill. Where I have seen them before?

Bill: That Sam can really tickle the ivories.

Lance: And Stud was definitely in the room.

Bill: On that note, take us out.

Lance: In a complex world, keep it simple.