New blog post: Layered pathwidth and its obstacles

https://11011110.github.io/blog/2018/10/22/layered-pathwidth-obstacles.html

I describe my new preprint with Dujmović, Joret, Morin, and Wood proving that a minor-closed graph family has bounded local pathwidth, linear local pathwidth, or bounded layered pathwidth iff it excludes an apex-tree, and compare analogous results in which the structure of a forbidden minor tells you about the structure of the graphs in a minor-closed family.

Theil–Sen (median slope) estimator, now a Good Article on Wikipedia: https://en.wikipedia.org/wiki/Theil%E2%80%93Sen_estimator

This is a method for fitting a line to a set of data points by finding the median slope of lines through pairs of points. It is robust, meaning that (unlike ordinary least squares) a constant fraction of the data can be arbitrarily corrupted without affecting the goodness of fit.

New blog post: Laminar 3-separators, https://11011110.github.io/blog/2018/10/20/laminar-3-separators.html

In it, I describe my new SODA paper with Bruce Reed, “Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time”, https://arxiv.org/abs/1810.07825, and how it's possible for an algorithm that works only on planar graphs to be useful as a subroutine for a different algorithm on nonplanar graphs (hint: they're not the same graphs).

Kokichi Sugihara wins the Best Illusion of the Year (again) with an orthogonal polyhedron! Or maybe a different orthogonal polyhedron. Or maybe a third one. Or maybe it's not actually orthogonal at all...

https://www.youtube.com/watch?v=iA5zBZB2dng (via https://www.metafilter.com/177169/Accurate-perception-is-optional)

Patterns in Nature: 12 shortlisted photographers for the Royal Society of Biology Photographer of the Year – https://www.theguardian.com/environment/gallery/2018/oct/08/patterns-in-nature-2018-rsb-photographer-of-the-year-shortlist-in-pictures (via https://www.metafilter.com/177120/Patterns-in-Nature-RSB-2018-shortlist)

Inspired by a line in a textbook about imagining people standing in circles to show set membership, I've made a @glitch simulation of people spontaneously forming a Venn diagram: https://spontaneous-venning.glitch.me/

An upper bound for Lebesgue’s universal covering problem

http://vixra.org/abs/1801.0292

Philip Gibbs makes progress on the smallest area needed to cover a congruent copy of every diameter-one curve in the plane, with additional contributions from John Baez, Karine Bagdasaryan, and Greg Egan. See Baez's blog post https://johncarlosbaez.wordpress.com/2018/10/07/lebesgue-universal-covering-problem-part-3/ for more. But why vixra??

Balogh and Solymosi's new paper https://doi.org/10.19086/da.4438

constructs \(n\) points in the plane, no four in line, with max general-position subset size \(O(n^{5/6+\epsilon})\), much better than the previous \(o(n)\). I recently rescued a Wikipedia article on Solymosi, https://en.wikipedia.org/wiki/J%C3%B3zsef_Solymosi, adding book references for his results, but omitted my favorite (this one) because it wasn't published. Now it is, but the book reference would be too self-serving to add...

Graduate student Urmila Mahadev devises interactive protocols that let you test whether a supposedly-quantum computer is really doing quantum stuff: https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/

Amazon trained a sexism-fighting, resume-screening AI with sexist hiring data, so the bot became sexist: https://boingboing.net/2018/10/11/garbage-conclusions-out.html

A Problem Fit for a Princess: https://www.mathteacherscircle.org/news/mtc-magazine/sa2017/apollonian-gaskets/

A post on the history of the Apollonian Gasket, a fractal formed by tangent circles, inspired by its use as the logo of the San Joaquin Math Teachers’ Circle.

A New ACO Center (guest post by Vijay Vazirani): https://blog.computationalcomplexity.org/2018/10/a-new-aco-center-guest-post-by-vijay.html

A new blog post by Vijay Vazirani on the new "algorithms, combinatorics, and optimization" center he's been organizing at UC Irvine, connecting researchers in CS, mathematics, and the business school, and modeled after the success of similar programs at CMU and Georgia Tech.

The list of accepted papers at SODA (the annual ACM–SIAM conference on discrete algorithms, to be held next January in San Diego) is now out at https://www.siam.org/conferences/CM/P/AP/soda19-accepted-papers

Via @JukkaSuomela's retweet of https://twitter.com/hoonoseme/status/1049369274182029312

I have been playing at generating snowflakes using cellular automata.

Looks like I may soon become more active here. Impetus: the impending shutdown of Google+. I may at least start mirroring what I post there to here and see how well that goes. For more discussion on alternative social media platforms see my G+ post, https://plus.google.com/100003628603413742554/posts/frN7avVYDDv

*very insistent voice* ANTISPAGHETTI

https://dev.glitch.social/media/rSp1G3TYHz3FJDcebL4

The "efficiency gap" makes sense only if you think 3--1 majorities are ideal.

https://fivethirtyeight.com/features/the-supreme-court-is-allergic-to-math/

Teruhisa Sugimoto has a draft paper that enumerates 17 types of convex, finitely surroundable pentagons! I hope to be able to read an English translation at some point. http://tilingpackingcovering.web.fc2.com/abstract-e.html#heeschCP

A set of works in progress; this is the after the 2nd of what will be either three or four passes total, using heavily thinned-out oils on large canvases.

https://mastodon.social/media/H7oDE1ZSMwhSpLYLBMY https://mastodon.social/media/MA602UEdQrbnZkgZxeI https://mastodon.social/media/FhxTrFooagoyR1IGkCs https://mastodon.social/media/ZLFVZYzsjoFZT263oEg

D. Eppstein, Comp.Sci. prof. @ UC Irvine; https://www.ics.uci.edu/~eppstein/ https://en.wikipedia.org/wiki/User:David_Eppstein https://11011110.github.io/blog/

Joined Apr 2017