Including debt to Marina Ratner, 1938-2017

Maryam Mirzakhani won the Fields Medal in 2014. We and the whole community are grieving after losing her to breast cancer two weeks ago. She made several breakthroughs in the geometric understanding of dynamical systems. Who knows what other great results she would have found if she had lived: we will never know. Besides her research she also was the first woman and the first Iranian to win the Fields Medal.

Today we wish to express both our great sorrow and our appreciation of her work.

All tessellating convex polygons found

 Cropped and combined from src1, src2.

Michaël Rao and Marjorie Rice are linked in this month’s news. Rao has just released a paper (see also slides and code here) completing the catalog of convex polygons that tile the plane. Rice, who passed away on July 2 (obit), had expanded the pentagon catalog from 9 to 13 while working in her kitchen in 1975. Rolf Stein found a fourteenth in 1985 and Casey Mann led a team of programmers to find a fifteenth in 2015. Rao has closed the book at 15.

Today Dick and I hail their accomplishments, which we noted from two articles by Natalie Wolchover in Quanta this past Tuesday. We also emphasize some related problems.

Birthday workshop at Rutgers last January

 Combined from source

Eric Allender and Michael Saks have been leading lights in computing theory for four decades. They have both turned 60 this year. I greatly enjoyed the commemorative workshop held in their honor last January 28–29 at DIMACS on the Rutgers campus.

Today Dick and I salute Eric and Mike on this occasion.

Just announced ${\dots}$

Oded Goldreich is one of the top researchers in cryptography, randomness, and complexity theory.

Today Ken and I wish to thank the Knuth Prize Committee for selecting Oded as the winner of the 2017 Knuth Prize.

Results of the panel at the Theory Fest

Géraud Sénizergues proved in 1997 that equivalence of deterministic pushdown automata (DPDAs) is decidable. Solving this decades-open problem won him the 2002 Gödel Prize.

Today Ken and I want to ponder how theory of computing (TOC) has changed over the years and where it is headed.

Of course we have some idea of how it has changed over the years, since we both have worked in TOC for decades, but the future is a bit more difficult to tell. Actually the future is also safer: people may feel left out and disagree about the past, but the future is yet to happen so who could be left out? Read more…

The problem of mining text for implications

 2016 RSA Conference bio, speech

Michael Rogers, the head of the National Security Agency, testified before the Senate Intelligence Committee the other day about President Donald Trump. He was jointed by other heads of other intelligence agencies who also testified. Their comments were, as one would expect, widely reported.

Today Ken and I want to talk about the state of ${\mathsf{P}}$ versus ${\mathsf{NP}}$ and the relationship to this story.