Top all-time · #1140
Erik Demaine
Personal blog · erikdemaine.orgmathsciencedesign
Erik Demaine's personal blog at erikdemaine.org covers math, science and design. Since 2011, 63 different Hacker News readers have linked it 75 times, most often “Erik Demaine's Folding and Unfolding Page (2010)”. No feed was found, so read it on the site itself.
Most-linked posts?
- /6 people · 6 mentions · first linked 2012-03-20
- Erik Demaine's Folding and Unfolding Page (2010)4 people · 5 mentions · first linked 2012-02-18
- Cache-Oblivious Algorithms and Data Structures [pdf]4 people · 4 mentions · first linked 2015-05-08
- /classes/3 people · 3 mentions · first linked 2011-07-05
- /3 people · 3 mentions · first linked 2024-01-30
- Mathematical and puzzle fonts/typefaces2 people · 2 mentions · first linked 2024-02-15
- Computational Balloon Twisting: The Theory of Balloon Polyhedra [pdf]2 people · 2 mentions · first linked 2014-06-06
- The Fold and Cut Problem2 people · 2 mentions · first linked 2023-07-18
- Mathematical and Puzzle Fonts/Typefaces2 people · 2 mentions · first linked 2018-12-17
What Hacker News says?
the professor is a fascinating guy: http://erikdemaine.org/ https://en.wikipedia.org/wiki/Erik_Demaine EDIT: so is the coauthor! http://joebergeron.io/posts/post_four.html
Comment linking /
on “Advanced Data Structures (2017)”Submitted Tetris Font (2020) as a story · 723 points
HN discussionIt's been a while since I used this in anger, but my recollection is that it maintains a fixed-size set of items. The same algorithm is in section 3.2 of https://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf and might be clearer there.
Comment linking /papers/NetworkStats_TR2002/paper.pdf
on “Computer scientists invent an efficient new way to count”Submitted Curved-Crease Sculpture as a story · 185 points
HN discussionThat 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/
Comment linking /papers/NCL_TCS/
on “Tetris Font (2020)”Submitted Mathematical and puzzle fonts/typefaces as a story · 94 points
HN discussionI 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 f…
Comment linking /papers/PushingBlocks_CGTA/
on “Tetris Font (2020)”Submitted Any Monotone Boolean Function Can Be Realized by Interlocked Polygons (2010) as a story · 76 points
HN discussionThanks for the feature suggestion! I've gone ahead and implemented random valid stacking order. So if you reload the page, and enter text that repeats the same letter more than once, you will hopefully get different build orders (depending on random choices). For example: https://erikdemaine.org/fonts/tetris/?text=aaaaa&rotate=0&sp...
Comment linking /fonts/tetris/?text=aaaaa&rotate=0&speed=4
on “Tetris Font (2020)”Submitted The Fold-and-Cut Problem (2016) as a story · 42 points
HN discussionNice https://erikdemaine.org/fonts/tetris/?text=u%26rz+~uu&rot=1&...
Comment linking /fonts/tetris/?text=u%26rz+~uu&rot=1&hud=0
on “Tetris Font (2020)”Submitted Erik Demaine's Folding and Unfolding Page (2010) as a story · 30 points
HN discussionVery neat! I love how you can do an entire paragraph. For example https://erikdemaine.org/fonts/tetris/?text=%7D6G6C+8%40%3F%3...
on “Tetris Font (2020)”Submitted 3D QR Codes as a story · 27 points
HN discussionThis is cool, and some of Demaine’s other work is amazing too. https://erikdemaine.org/papers/Origamizer_SoCG2017/paper.pdf ^ provides an algorithm for generating any 3D solid via folding a 2D net (origami style)
Comment linking /papers/Origamizer_SoCG2017/paper.pdf
on “Tetris Font (2020)”- ot · 2014-10-16
Submitted Computational Balloon Twisting: The Theory of Balloon Polyhedra [pdf] as a story · 24 points
HN discussion Here are the videos for the Fall 2005 "Intro to Algorithms" class ( http://amps-videoserver2.mit.edu:8080/reports/sma/index5503f... ), and you can find videos of his other classes here ( http://erikdemaine.org/classes/ ).
Comment linking /classes/
on “MIT 6.006: Algorithms in Python”Submitted Tetris Font as a story · 8 points
HN discussionThe pattern matching (TC39 stage 1) and pipeline operators (TC39 stage 2) look great, and I'd love to have those in TypeScript. It will probably take a loooong while for those features to be available in JavaScript, but I feel like I can live without those for now :-). Fwiw it seems a lot of people really like the concept of "significant indentation". I'm thinking Python, YAML, Godot's GDScript. Not a lof of languag…
Comment linking /
on “Civet: A Superset of TypeScript”Submitted Lino Tagliapietra: Glass Magician (2011) as a story · 7 points
HN discussionIf anyone wants to read more, there are (pre this article) papers on cache friendly/oblivious priority queues, e.g. http://erikdemaine.org/papers/BufferTrees_STOC2002/paper.pdf The rough gist is that if the only thing you need to be able to do is insert and pop-min, then you can buffer up roughly a page's worth of incomplete work for each page, getting amortized performance that tracks the optimal number of cache tr…
Comment linking /papers/BufferTrees_STOC2002/paper.pdf
on “B-Heap vs. Binary Heap (2010)”Submitted Algorithms for Solving Rubik’s Cubes [pdf] as a story · 5 points
HN discussionAlso checkout Erik Demaine's work on computational folding & origami: https://erikdemaine.org/folding/
Comment linking /folding/
on “Origami Simulator”Submitted Computational Balloon Twisting: The Theory of Balloon Polyhedra [pdf] as a story · 4 points
HN discussionGreat suggestion -- Demaine's lecture videos were so illuminating for me when I studied cache-oblivious algos. Here's a corresponding paper describing the cache-oblivious Funnelsort algorithm: http://erikdemaine.org/papers/BRICS2002/paper.pdf
Comment linking /papers/BRICS2002/paper.pdf
on “An Introduction to Cache-Oblivious Data Structures”Submitted The Fold and Cut Problem as a story · 3 points
HN discussion> 1) The linearly-probed robin hood variant is just a sorted array. That's it. It's just a sorted array. Right. I stumbled on linear probing robin hood hashing as a simplification of Bender, Demaine and Farach-Colton's Packed memory array ( http://erikdemaine.org/papers/FOCS2000b/paper.pdf ) when inserts are randomised. > 2) The linearly-probed robin hood variant is only faster than regular linear probing for search…
Comment linking /papers/FOCS2000b/paper.pdf
on “Writing a Very Fast Hash Table with Tiny Memory Footprints”Submitted Dissection Font as a story · 3 points
HN discussionLooking at Lang's site, yes it is a super niche area, but there is a lot of self promotion - books, events, etc. I was first introduced to the general area of curved crease, etc was with David Huffman in the early 90s. He started that work in the early 70s. So, Lang proclaims to the the first, but salesmanship is important. Eric himself reconstructs some of huffman's work - https://erikdemaine.org/papers/Huffman_Ori…
Comment linking /papers/Huffman_Origami5/paper.pdf
on “Curved-Crease Sculpture”Submitted Retroactive Data Structures (2007) [pdf] as a story · 3 points
HN discussion
