New blog post: Layered pathwidth and its obstacles
11011110.github.io/blog/2018/1

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: en.wikipedia.org/wiki/Theil%E2

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, 11011110.github.io/blog/2018/1

In it, I describe my new SODA paper with Bruce Reed, “Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time”, 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...

0xDE boosted

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: spontaneous-venning.glitch.me/

An upper bound for Lebesgue’s universal covering problem
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 johncarlosbaez.wordpress.com/2 for more. But why vixra??

Balogh and Solymosi's new paper 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, en.wikipedia.org/wiki/J%C3%B3z, 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: quantamagazine.org/graduate-st

0xDE boosted

There! This is a 'proper' Delaunay Triangulation and Voronoi Diagram. I did mess up in a few places with the lines for the Voronoi part though, I was still freehanding it and not using pencil guidelines XD

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

A Problem Fit for a Princess: mathteacherscircle.org/news/mt

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): blog.computationalcomplexity.o

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 siam.org/conferences/CM/P/AP/s

0xDE boosted

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, plus.google.com/10000362860341

0xDE boosted

*very insistent voice* ANTISPAGHETTI
dev.glitch.social/media/rSp1G3

0xDE boosted

The "efficiency gap" makes sense only if you think 3--1 majorities are ideal.
fivethirtyeight.com/features/t

0xDE boosted

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. tilingpackingcovering.web.fc2.

0xDE boosted

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.

A Mastodon instance for maths people. The kind of people who make $\pi z^2 \times a$ jokes.
Use $ and $ for inline LaTeX, and $ and $ for display mode.