There was some coverage of my work on dynamic algorithms in Austrian media over the long weekend. I'm not used to doing "popular science", but I'm quite happy with the results.
Kleiner Tipp für einen quasi serverfreien Jitsi-Ersatz:
Einfach alle teilnehmenden in Chrome oder Firefox die URL https://obs.ninja/?room=<hoppla> öffnen. Nur wichtig, dass alle das gleiche <hoppla> verwenden.
Kein Login, kein Account. Die Browser schicken sich Audio und Video direkt, dadurch super niedrige Latenz.
Für mehr Sicherheit alle hinten an die URL noch &password anhängen und dann natürlich das gleiche eintippen.
🖥️ Threats of a Replication Crisis in Empirical Computer Science
"While computer science research has increased its use of experimental methods, the scientific community's faith in these methods has been eroded in several areas, leading to a 'replication crisis' in which experimental results cannot be reproduced and published findings are mistrusted. [...]"
I'm currently teaching max flow in our advanced algorithms class and need to decide whether I want to exclude anti-parallel edges in the input graph.
This has implications on how to define the residual capacities and is connected to the question how to precisely formulate the problem. Should the flow function represent a nonnegative flow or a, possibly negative, net flow? I found an interesting blog post by Bo Waggoner discussing this issue!
Lots of stuff going on these days: (1) My teaching has started ("Advanced Algorithms and Data Structures" and "Problem Solving and Algorithmic Thinking") (2) Tijn de Vos has started as a PhD student in our group (Welcome, Tijn!) (3) DISC is happening this afternoon; the videos are already online and late registrations are still possible: https://www.youtube.com/channel/UCrgSwDN9zoYlP_UFuOSynmg
From Tim Gowers on Twitter:
A while ago, I tweeted that I hoped Cambridge would allow us to post our online lectures publicly. I'm delighted to say that they do indeed allow this, so I shall be posting my course Topics in Combinatorics on YouTube as I give it.
The first two videos (equivalent to one lecture) are now up on my fledgling YouTube channel. They are not particularly polished, but that wasn't the idea.
Retraction of "a proof of soundness of the Raz-Safra low-degree test against entangled-player strategies, a key ingredient in the proof of the quantum low-degree test, itself a key ingredient in the MIP*=RE paper": https://mycqstate.wordpress.com/2020/09/29/it-happens-to-everyonebut-its-not-fun/
MIP*=RE is patched and remains believed true but not fully refereed. This post provides a lot more than the standard we-found-a-bug notice: a good description of what happened, what it implies technically, and how it affects the authors and community.
For academic publishing to be trans-inclusive, authors must be allowed to retroactively change their names: https://blogs.lse.ac.uk/impactofsocialsciences/2020/09/30/for-academic-publishing-to-be-trans-inclusive-authors-must-be-allowed-to-retroactively-change-their-names/, via https://retractionwatch.com/2020/10/03/weekend-reads-unicorn-poo-and-other-fraudulent-covid-19-treatments-disgraced-researchers-and-drug-company-payouts-a-fictional-account-of-real-fraud/
I agree — more than once in researching Wikipedia bios I found past publications under deadnames. If the authors prefer this to be better hidden, while continuing to be credited for their past work, we should try to honor that preference.
Our paper "Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications" was accepted to SODA '21. Joint work with Gramoz Goranci and Monika Henzinger.
Michael Wehar posted a nice algorithms / fine grained complexity question on the CS theory stack exchange: how quickly can we test whether a 2d matrix has a square of four non-zero entries, https://cstheory.stackexchange.com/q/47588/95 ?
The obvious method, looping over nonzeros and testing the squares each might be part of, is cubic when there are many nonzeros. And there can be many nonzeros without forcing a square to exist. Is there a standard hardness assumption under which strongly subcubic is impossible?
European Women in Mathematics have written an open letter advocating proactive support of temporary employees, applicants, women, and parents in academia, to forestall disproportionate losses in diversity in the wake of the covid pandemic: https://www.europeanwomeninmaths.org/ewm-open-letter-on-the-covid-19-pandemic/
It's addressed to European authorities but most of the same concerns apply more globally. Via https://twitter.com/hollykrieger/status/1308375574285606913
Dynamic graph planarity testing, in Quanta: https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/
New Combinatorics journal to watch
Intended to be a successor to JCTA. I hope they sort out a TLS certificate soon.
Alle sind sich einig, dass es um unsere #DigitaleSouveränität nicht gut bestellt ist. Aber wer tut etwas dafür?
Wir haben uns einem Bündnis angeschlossen, das einen konkreten Schritt vorwärts gehen möchte mit einer rechtssicheren Open-Source-Plattform.
I am deeply honored by the ERC's decision to fund my project "Dynamic Algorithms Against Strong Adversaries" (DynASoAr) with a Starting Grant. #ERCStG
ESA 2020 (European Symposium on Algorithms) will take place next week. As usual, ESA is part of ALGO and takes place with other conferences and workshops as well.
Registration is free, but mandatory. Registration deadline: September 5.
Our department is now offering a mini-curriculum that gives non-CS students the opportunity to gain computer science competences. We're opening some of our courses to all students at University of Salzburg. The official name is "Studienergänzung Informatikkompetenz für alle", see https://informatik.uni-salzburg.at/de/studium/ifa
I would like to thank my colleagues Bernhard Collini-Nocker and Christoph Kirsch who helped me with the design of this curriculum.
Computer scientist at University of Salzburg, Austria, working on graph algorithms
The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!