Tiling with Three Polygons Is Undecidable

[xianshou]

First you ask how the hell someone could come up with this construction.

Then you realize it was this guy: https://en.wikipedia.org/wiki/Erik_Demaine

[atq2119]

And then you read the abstract and realize that this is an improvement of an earlier result using five polygons (which in turn built on a history of earlier results).

So, still a great result, but not as out there as one may think.

I think it's also worth pointing out that in theoretical CS and most of math, it is common to list authors alphabetically. I don't think we have a way of knowing the relative contribution of the two authors. Demaine is obviously accomplished, but I find the kind of hero worship found in this thread distasteful and the facts don't support it here. Give credit to Langerman; Demaine surely would!

[_Donny]

Woah! It is the same guy that got me through my algorithms course at university with his youtube MIT OpenCourseWare videos!

His lectures are absolute gold. He explains everything so clearly, simply, and efficiently.

I started skipping lectures in favor of watching his videos, and it saved me countless of hours -- and I got a perfect mark :)

[fuzzythinker]

His page - https://erikdemaine.org/

[heavensteeth]

>former child prodigy

I understand the idea behind that phrasing but I'm not sure I agree with it. Are you no longer a child prodigy once you turn 18? I don't think I'd ever say "former intelligent child".. Would I?

[YoumuChan]

The author gave a talk on this at Tufts during the FWCG last week. Fascinating talk.

One interesting question from audience was whether the ratio between the largest polygon piece and the smallest piece can be made bounded, as the current construction has unbounded ratio.

[whatshisface]

That's reminicient of the post correspondence problem. Is the PCP still undecidable for sets of three strings?

[petters]

I don't think that is known. But the limit is low, something like five

[joebergeron]

I read the title of this paper and thought to myself, “What are the chances this could be Erik Demaine?”. And sure enough!

[bryan0]

While not proven, is the intuition that this will also be undecideable for 1 and 2 polygon tilings?

[romwell]

Erik Demaine always has some fun stuff for us.