Snap Cube Puzzle: Snap cubes have a post on one side, and holes (into which a post can fit) on the other five sides. How many ways to build a 2x2x2 cube out of eight snap cubes such that (1) the entire structure is connected, and (2) all the posts are in the interior – no posts sticking out of the surface? (All the different structures look the same from the outside; the difference is in the orientation of the eight posts internally.)

New blog post: Euler characteristics of non-manifold polycubes, https://11011110.github.io/blog/2019/04/23/euler-characteristics-nonmanifold.html

Why asymptotics matters: slow quadratic-time process creation in Windows 10: https://randomascii.wordpress.com/2019/04/21/on2-in-createprocess/ (via https://news.ycombinator.com/item?id=19716673)

Planar point sets determine many pairwise crossing segments: https://arxiv.org/abs/1904.08845

János Pach, Natan Rubin, and Gábor Tardos make significant progress on whether every \(n\) points in the plane have a large matching where all edges cross each other. A 1994 paper by Paul Erdős and half a dozen others only managed to prove this for "large" meaning \(\Omega(\sqrt{n})\). The new paper proves a much stronger bound, \(n/2^{O(\sqrt{\log n})}\) (Ryan Williams' favorite function).

Czech president Miloš Zeman "has repeatedly used presidential powers to block the professorships of political opponents": https://www.insidehighered.com/news/2019/04/12/czech-president-blocks-professorships-academic-critics. Charles University is now suing to allow their promotions to go through.

Regular polygon surfaces: https://arxiv.org/abs/1804.05452

Ian Alevy answers Problem 72 of The Open Problems Project (http://cs.smith.edu/~jorourke/TOPP/P72.html#Problem.72): every topological sphere made of regular pentagons can be constructed by gluing regular dodecahedra together.

You can also glue dodecahedra to get higher-genus surfaces, as in this image from https://momath.org/mathmonday/the-paragons-system/, but Alevy's theorem doesn't apply, so we don't know whether all higher-genus regular-pentagon surfaces are formed that way.

Mathematical sign language: https://aperiodical.com/2019/04/mathematical-sign-language-interview-with-dr-jess-boland/

Hearing-impaired eletrical engineering researcher Jess Boland discovered that weren't enough technical terms in British Sign Language to cover the mathematics she uses in her work, so she's been creating new ones as well as promoting the ones BSL already had. Katie Steckles interviews her for The Aperiodical.

(@aperiodical has a Mathstodon account but they're letting it go stale instead of promoting their new posts...)

Vox on the sexist backlash against astronomer Katie Bouman, of black hole image fame, after she was cast by the media in the "lone genius" role typically reserved for men and untypical of how science actually happens: https://www.vox.com/science-and-health/2019/4/16/18311194/black-hole-katie-bouman-trolls

(see also https://www.cnn.com/2019/04/12/us/andrew-chael-katie-bouman-black-hole-image-trnd/index.html or any of several other similar stories)

Good article, terrible headline: https://blog.computationalcomplexity.org/2019/04/good-article-terrible-headline.html

Bill Gasarch rants about several recent instances of clickbaity, inaccurate, and overhyped media coverage of theoretical computer science topics. I suspect the answer to his question "is it just our field?" is no.

A proposed new Berlin transit map replaces stylized axis-parallel and diagonal line segments with smooth curves: https://www.berlintransitmap.de/

The old design was seen as "out of style", "too robotized", and too difficult to follow routes. There's still a strong preference for axis-parallel and diagonal lines in the new map, but the connections between them have been smoothed out.

Via https://www.metafilter.com/180431/Berlin-Transit-Map-now-with-pleasing-Curves

New blog post: Monochromatic grids in colored grids, https://11011110.github.io/blog/2019/04/14/monochromatic-grids-colored.html

Sad news from Berkeley (https://blog.computationalcomplexity.org/2019/04/elwyn-berlekamp-died-april-9-2019.html): Elwyn Berlekamp has died. Berlekamp made significant contributions to combinatorial game theory (motivated, as I understand it, by the mathematical study of Go endgames), coding theory, and algorithms for polynomials. See also the Wikipedia article about him, https://en.wikipedia.org/wiki/Elwyn_Berlekamp

New blog post: Coloring kinggraphs, https://11011110.github.io/blog/2019/04/11/coloring-kinggraphs.html

SIAM-ACM Conference on Algorithmic Principles of Computer Systems (APOCS): https://www.siam.org/Conferences/CM/Main/apocs20

This is a new conference to be held with SODA, next January in Salt Lake City, covering "all areas of algorithms and architectures that offer insight into the performance and design of computer systems". Submission titles and abstracts are due August 9 (with full papers due a week later) so if this is an area you're interested in there's still plenty of time to come up with something to submit.

EU falsely calls Internet Archive's major collection pages, scholarly articles, and copies of US government publications "terrorism" and demands they be taken down from the internet: https://blog.archive.org/2019/04/10/official-eu-agencies-falsely-report-more-than-550-archive-org-urls-as-terrorist-content/

(see also https://boingboing.net/2019/04/11/one-hour-service.html).

The EU is about to vote to require terrorism takedowns to happen within an hour, and these requests are coming on European times when all Internet Archive employees (in California) are asleep, making manual review of these bad takedowns difficult.

The Supreme Court’s Math Problem: https://slate.com/news-and-politics/2019/03/scotus-gerrymandering-case-mathematicians-brief-elena-kagan.html

Jordan Ellenberg explains why, in testing for gerrymandering, asking about deviation from proportional representation is the wrong question. Democratic systems naturally concentrate power to the majority rather than being proportional. The right question is whether that concentration is at the natural level, or is artificially accelerated in one direction or another.

Via https://www.metafilter.com/180163/The-Supreme-Courts-Math-Problem

PLOS disappears one (or maybe more) of its hosted blogs without any warning to the blog author, without any attempt at keeping old blog links still working, and with only a belated apology: https://retractionwatch.com/2019/04/08/with-a-badly-handled-tweet-plos-angers-scientists-after-a-blog-disappears/

Photos from a recent computational geometry workshop in Barbados: https://11011110.github.io/blog/2019/04/07/photos-from-barbados.html

Periodic billiard paths: http://web.colby.edu/thegeometricviewpoint/2014/04/25/periodic-billiard-paths/

If the boundary of a given polygon is made of mirrors, these are paths that a laser beam could take that would eventually reflect back to the starting point and angle and then repeat infinitely. It remains a heavily-studied open question whether such paths exist in every triangle. This blog post from 2014 provides a proof that they do exist in polygons whose vertex angles are all rational multiples of π.

Sandy Irani (one of my colleagues at UCI) is being given the IEEE TCMF Distinguished Service Award for her work chairing the ad hoc committee to combat harassment and discrimination in the theory of computing community, and for then getting many theory conferences to follow its recommendations: http://focs2019.cs.jhu.edu/awards/

For the committee and its report, see https://www.ics.uci.edu/~irani/safetoc.html

- Home page
- https://www.ics.uci.edu/~eppstein/

I'm a computer scientist at the University of California, Irvine, interested in algorithms, data structures, discrete geometry, and graph theory.

Joined Apr 2017