zlacker

I know him from proving NP-hardness of the game Sokoban:

https://erikdemaine.org/papers/PushingBlocks_CGTA/

And I clicked this submission because of his name, after all the time.

I didn't fully go through or understand the proof, but it was a refreshing addition to the classic problems I had to understand for college at the time.

Didn't need it, just fed my curiosity.

And when I clicked this link, my curiosity was fed again.

Seems like it's worth having heard of him, even as a non-scientist, because his subjects are just so interesting. Reminds me of Scott Aaronson in that regard.

>>moritz+(OP)
That paper does not prove that Sokoban is NP-hard. It does, however, cite an earlier paper proving the stronger result that Sokoban is PSPACE-complete:

Culberson, Joseph. "Sokoban is PSPACE-complete." (1997). https://era.library.ualberta.ca/items/f551dfd8-c8e6-4e78-883...

See also https://erikdemaine.org/papers/NCL_TCS/

>>areyou+N4
Yes, correct, and mentioned in the abstract. Sorry, I was imprecise and wrong.

Thanks for the links!