Skip to content

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…

Stopped Watches and Data Analytics

May 23, 2017

Is this a new or old paradox?

UK Independent source—and “a gentle irony”

Roger Bannister is a British neurologist. He received the first Lifetime Achievement Award from the American Academy for Neurology in 2005. Besides his extensive research and many papers in neurology, his 25 years of revising and expanding the bellwether text Clinical Neurology culminated in being added as co-author. Oh by the way, he is that Bannister who was the first person timed under 4:00 in a mile race.

Today I cover another case of “Big Data Blues” that has surfaced in my chess work, using a race-timing analogy to make it general.

Read more…