Integer linear programming, change-making, and Presburger arithmetic: https://gilkalai.wordpress.com/2019/03/22/danny-nguyen-and-igor-pak-presburger-arithmetic-problem-solved/

Integer arithmetic problems with O(1) variables and one level of quantifiers (example: given O(1) coin types, find the largest amount of money for which you cannot make change) have long been known to be polynomially solvable, but in FOCS 2017 Nguyen and Pak proved that only two levels of quantifiers make the problem hard. See also review https://mathscinet.ams.org/mathscinet-getitem?mr=3734216 and paper http://www.math.ucla.edu/~pak/papers/hard_presburger3.pdf

Squaring the spherical earth: https://uhills.org/the-university-hills-section-marker-a-history-of-maps-markers-and-monuments-that-eventually-created-university-hills/

For surveying purposes, Orange County is divided into "sections", typically 1 mile² (not axis-aligned!) with small brass markers at their corners. One corner lands in the UCI faculty housing development where I live, and the housing association took the opportunity to make a larger decorative marker for it. It's on a sidewalk between my house and the farmer's market, so I happened to walk past it this week.

Nature on how word processors and text editors have been shifting from roll-your-own equation editing to LaTeX: https://www.nature.com/articles/d41586-019-01796-1

Two colleagues from my department, Alex Nicolau and Alex Veidenbaum, are participating in a Venice Biennale project (http://artdaily.com/news/114313/University-of-California--Irvine-computer-scientists-breathe-life-into-Venice-Biennale-installations) in which viewers converse with computerized simulations of poet Paul Celan (https://en.wikipedia.org/wiki/Paul_Celan) and politician Nicolae Ceaușescu (https://en.wikipedia.org/wiki/Nicolae_Ceau%C8%99escu).

The Alexes usually work on the more technical side of CS (parallelizing compilers, computer architecture, and embedded systems) so it's interesting to me to see this softer direction from them.

While I'm publicizing activities associated with STOC and FCRC next week in Phoenix, here's another: the TCS Women Spotlight Workshop, https://sigact.org/tcswomen/tcs-women-2019/

It features an inspirational talk from Ronitt Rubinfeld (in my experience a great speaker), four "rising star" talks by Naama Ben-David, Debarati Das, Andrea Lincoln, and Oxana Poburinnaya, a panel/lunch for women at STOC, and a poster session of recent theoretical computer science research by women.

The SIGACT Committee for the Advancement of Theoretical Computer Science is planning a Wikipedia edit-a-thon, in Phoenix on June 24 as part of STOC: see https://thmatters.wordpress.com/2019/06/11/wikipedia-edit-a-thon-at-stoc19/

You can help, and you don't even have to brave the desert heat to do so! There's a shared spreadsheet linked from https://thmatters.wordpress.com/2017/05/02/tcs-wikipedia-project/ where CATCS is crowdsourcing TCS topics on Wikipedia that need help. Add your favorite missing algorithm, theorem, complexity class, etc, and it's likely it'll get some attention.

New blog post: Dancing arc-quadrilaterals, https://11011110.github.io/blog/2019/06/11/dancing-arc-quadrilaterals.html

In which an analogy to Matisse's ring of abstracted dancing figures lets me prove the nonexistence of Lombardi-style graph drawings for certain bipartite planar graphs and series-parallel graphs.

Square wave patterns in nature: https://en.wikipedia.org/wiki/Cross_sea (where this image comes from)

And wave patterns in social media: search for "cross sea" and note its appearance on gizmodo in 2014, amusingplanet in 2015, azula in 2017, providr in 2018, sciencealert in 2019...all repeating the same somewhat garbled explanation of mathematical wave models and danger to shipping.

Luca Trevisan posts a series of tutorials on online convex optimization, where you want to approximately minimize a sequence of convex functions before discovering what the functions are. It's a hot topic in TCS with connections to regularity lemmas, fast SDP approximation, and spectral sparsifiers.

See:

https://lucatrevisan.wordpress.com/2019/04/17/online-optimization-for-complexity-theorists/

https://lucatrevisan.wordpress.com/2019/04/22/online-optimization-post-0-definitions/

https://lucatrevisan.wordpress.com/2019/04/24/online-optimization-post-1-multiplicative-weights/

https://lucatrevisan.wordpress.com/2019/04/25/online-optimization-post-2-constructing-pseudorandom-sets/

https://lucatrevisan.wordpress.com/2019/05/06/online-optimization-post-3-follow-the-regularized-leader/

https://lucatrevisan.wordpress.com/2019/05/16/online-optimization-post-4-regularity-lemmas/

https://lucatrevisan.wordpress.com/2019/05/20/online-optimization-post-5-bregman-projections-and-mirror-descent/

Compact packings of the plane with three sizes of discs: https://arxiv.org/abs/1810.02231, Thomas Fernique, Amir Hashemi, and Olga Sizova

Here, "compact packing" means interior-disjoint disks forming only 3-sided gaps. The circle packing theorem constructs these for any finite maximal planar graph, with little control over disk size. Instead this paper seeks packings of the whole plane by infinitely many disks, with few sizes. 9 pairs of sizes and 164 triples work. Here's one from Fig.3 of the paper.

New blog post: A little knowledge can make the next step harder, https://11011110.github.io/blog/2019/06/07/little-knowledge-can.html

It's on a phenomenon in Sudoku and other similar puzzle games, where (if you use the assumption that there is a unique solution as the basis for certain puzzle-solving rules) then it matters which order you apply your inference rules: choosing a rule that makes a weak inference can prevent you from ever later using a different rule that would have allowed you to make a stronger inference.

Death of Proof (The Pleasures of Failure I): https://theinnerframe.wordpress.com/2018/07/16/death-of-proof-the-pleasures-of-failure-i/

The tale of Horgan's surface, a nonexistent minimal surface whose existence was incorrectly predicted by numerical experiments, named sarcastically after a journalist who incautiously suggested proof was dead. See also http://www.indiana.edu/~minimal/essays/horgan/index.html and https://www.scottaaronson.com/blog/?p=4133; via Carnival of Mathematics 170, https://mathenchant.wordpress.com/2019/06/06/carnival-of-mathematics-170/

Chip-firing games and sesquinary notation: https://mathenchant.wordpress.com/2017/09/17/how-do-you-write-one-hundred-in-base-32/

Jim Propp writes a monthly long-form math blog and somehow I hadn't encountered it before. This is one of its many interesting entries. One of the oddities about base 3/2 is that you calculate it bottom-up (by starting from a ones digit that's too big and then carrying things higher) instead of top-down (by greedily subtracting powers).

There are a lot of interesting-looking Soviet-era mathematics and science books and booklets (translated into English and free to read) at https://archive.org/details/@mirtitles

Via https://mathstodon.xyz/@jarban/102209797748141088, where @jarban linked to one on linear recurrence relations.

@robbykraft makes Voronoi origami! https://www.instagram.com/p/BaSVpX_nMpU/

See also http://orderinspace.blogspot.com/2015/07/voronoi.html from four years ago by "robby" — same person?

Remote-controlled papercraft steerable Strandbeest: https://hackaday.com/2019/06/01/paper-strandbeest-is-strong-enough-to-walk/, via https://news.ycombinator.com/item?id=20068166

Line arrangements in architecture: the beams of Cambridge's Mathematical Bridge (https://en.wikipedia.org/wiki/Mathematical_Bridge) form tangent lines to its arch and then extend through and support its trusswork, while another set of radial lines tie the structure together.

The bridge just looks like a wood truss bridge in real life but this artificially-colored image, from https://commons.wikimedia.org/wiki/File:Mathematical_Bridge_tangents.jpg, makes the underlying structure clearer.

IEEE bans Huawei employees from reviewing submissions to its journals, saying it is forced to do so by US government sanctions: https://www.sciencemag.org/news/2019/05/ieee-major-science-publisher-bans-huawei-scientists-reviewing-papers

- 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