Skip to content

Maryam Mirzakhani, 1977–2017

July 28, 2017

Including debt to Marina Ratner, 1938-2017

By joint permission of Assad Binakhahi, artist, and Radio Farda (source)     

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.
Read more…


Kitchen Tile Catalog Complete

July 16, 2017

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.
Read more…

Eric and Mike Turn 60

July 5, 2017

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.
Read more…

Oded Wins The Knuth Prize

June 22, 2017

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.
Read more…

TOC In The Future

June 12, 2017

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…

Does Logic Apply To Hearings?

June 8, 2017

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.

In real time, I heard Admiral Rogers’s comments. Then I heard and read the reports about them. I am at best puzzled about what happened.
Read more…

Goldilocks Principle And P vs. NP

May 30, 2017

The rule of three

Wikimedia Commons source

Robert Southey was the Poet Laureate of Britain from 1813 until his death in 1843. He published, anonymously, “The Story of the Three Bears” in 1837.

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