A tiny improvement sometimes makes for a big result: In a new preprint "A (Slightly) Improved Approximation Algorithm for Metric TSP" (arxiv.org/abs/2007.01409), Anna Karlin, Nathan Klein, and Shayan Oveis Gharan claim a reduction in the approximation ratio for traveling salesperson in arbitrary metric spaces from \(\tfrac{3}{2}\) to \(\tfrac{3}{2}-10^{-36}\). But it's the first such improvement since Christofides and Serdyukov in 1976, on a central problem in approximation algorithms.

I'm excited to work with Mara Grilnberger and Martin Grösbacher, two bachelor students from the University of Salzburg, over the summer. We will try to make progress on some tasks within the project "Distributed Algorithms for Fundamental Graph Problems".

Welcome to the lab, Mara and Martin!

mathematics, role model 

Dona Strauss is a mathematical role model of mine and just as amazing in person. What I didn't know was that she left South Africa in protest of Apartheid. Or that she got fired from Dartmouth after anti-war protests. So plain "role model" will do from now on.


(For me, she's also a typical example the discriminatory age limit of the Fields' medal - her research took off in her 40s, "surprisingly" right when her children were older.)

Does anyone know what's up with the Mathematics Genealogy Project? I haven't been getting any response from its servers for a week or so.

The annual ACM Symposium on Theory of Computing is happening online this week, and all the research talks are being made public on YouTube. You can find them through this playlist: youtube.com/playlist?list=PLn0

If you're interested, here's how to change the name of the default branch for your new local Git repositories, as well as some links identifying why you might want to move away from "master": leigh.net.au/writing/git-init-

The Alternative Big O notation:

O(1) = O(yeah)
O(log n) = O(nice)
O(n) = O(k)
O(n²) = O(my)
O(2ⁿ) = O(no)
O(n!) = O(mg!)

"If you are in academia, share your publications, share your teaching materials, share your code, share your data, share your time. If you have the opportunity, please help to facilitate more open exchange of talent and of knowledge."

#OpenScience #OpenData #science #data #research #share #exchange #idea

Four book publishing corporations claim that what libraries always have done (lending out copies of books they have purchased as physical objects) is illegal, because computer, and are suing the Internet Archive over it: blog.archive.org/2020/06/01/fo theverge.com/2020/6/1/21277036 torrentfreak.com/publishers-su

One of them, Wiley, is also a major publisher of academic works. Perhaps that should give some of us pause in which journals we send our papers to and referee for.

Is anyone using or similar to distribute videos for ? I'd basically like to be able to link to videos from my generated HTML and not have the students have to think about where the videos are hosted. I'm also interested in how much load running a instance would place on my server, but I guess that is pretty hard to quantify.

Tim Gowers relates the convoluted history of a mathematical announcements journal: gowers.wordpress.com/2020/05/2

Electronic Research Announcements of the AMS (founded 1995) moved to the American Inst. of Mathematical Sciences in 2007, but recent heavyhanded moves by the publisher led the editorial board to quit, and its name changed to Electronic Research Archive. In the meantime the old editorial board have a new journal: Mathematical Research Reports, mrr.centre-mersenne.org/. See link for details.

Call for nominations for new editor-in-chief of ACM Transactions on Algorithms: thmatters.wordpress.com/2020/0

Nominations are due June 8.

I'm looking for a PhD student and a postdoc to work in my project "Distributed Algorithms for Fundamental Graph Problems". The main goal of this project is to design new algorithms with theoretical guarantees for fundamental graph problems, like maximum flow and shortest paths, in distributed models of computation such as the CONGEST model.

The start date for both positions is negotiable. Please contact me to find out more.


When I did a lot of road cycling, I often heard the mantra "Cheap – lightweight – durable... pick TWO."

Preparing my class stuff lately feels like "Good pedagogy – works online – can be prepared in time... pick TWO"

New preprint on arXiv: "Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications" (arxiv.org/abs/2004.10319). This is joint work with Gramoz Goranci and Monika Henzinger.

We show how to maintain Bartal-style tree embeddings of undirected graphs undergoing edge insertions and deletions. We obtain certain trade-offs for polylogarithmic expected stretch and sublinear update-time.

Although Conway might not have been too happy with his name being eternally connected with the Game of Life, it still is fascinating that the Game's emergent patterns can be tamed to obtain a Turing complete machine. In class, I did a short "proof by video" of Turing completeness. Starting with the Gosper glider gun, one can create gadgets for logic gates. These can then be plugged together to simulate the von Neumann architecture. Detailed explanation by Nicolas Loizeau: nicolasloizeau.com/gol-compute

Show more

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!