New Book-Sorting Algorithm Almost Reaches Perfection: https://www.quantamagazine.org/new-book-sorting-algorithm-almost-reaches-perfection-20250124/
Quanta on the list labeling problem, based on "Nearly Optimal List Labeling" (https://arxiv.org/abs/2405.00807) by Bender, Conway, Farach-Colton, Komlós, Koucký, Kuszmaul, and Saks, from FOCS 2024.
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
Scott Aaronson on the ongoing situation at the NSF (https://scottaaronson.blog/?p=8609) or, as he calls it, "the American science funding catastrophe". He writes that, despite the executive order freezing all operations supposedly being rescinded, grant funding is still frozen and operations at a standstill.
If you thought you saw me boost a different post going into more detail about the same thing, you did, but it was taken down, presumably out of fear of consequences for making truth public. Let this be a sign to keep locally any information you want kept rather than relying on others to keep it for you.
Edit: The post I linked to earlier is now back up in a modified form: https://blog.computationalcomplexity.org/2025/01/the-situation-at-nsf.html
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
Grid bracing: https://en.wikipedia.org/wiki/Grid_bracing
This is a mathematical abstraction of problems of making a grid-like structure rigid by adding cross-bracing, of a type that should be familiar to anyone who has played with building blocks, built houses of cards, or tried to assemble a backless bookshelf. It forms a bridge between combinatorics and structural engineering in providing a solution to these problems based purely on graph connectivity analysis rather than numerical simulation.
Now a Good Article on Wikipedia.
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
My paper "What is...treewidth" has appeared in the Notices of the AMS for its February issue: https://www.ams.org/journals/notices/202502/rnoti-p172.pdf
It is a very high-level survey of the subject, necessarily limited by the format to have not much technical depth and not many references. If you already know what treewidth is and use it in your work, you might not learn much of use from it. My focus instead was on explaining to mathematicians (and computer scientists) in related fields why they might want to learn it. If you work in sparse numerical linear algebra, Bayesian inference, control theory, game theory, low dimensional topology, network science, or algebraic geometry, then this paper overviews applications of treewidth in your area, and if you don't work in those areas then you might still learn something from it about those applications.
And if you're still wondering "what is treewidth" after reading this post, then the survey does also cover the (many) ways of defining it and using it in graph structure theory and graph algorithms. But for this post, I'll try to do it in a single sentence: it's a way of describing arbitrary graphs as "thickened trees" and a measure of how much thickening is needed.
=> More informations about this toot | View the thread
What do all those different squiggly equal signs mean?
A Wikipedia discussion on the symbol (\simeq) (called "asymptotically equal to" by the Unicode consortium, unicode U+2243) led me to https://math.stackexchange.com/questions/864606/difference-between-%E2%89%88-%E2%89%83-and-%E2%89%85 where I learn that it is commonly used for homotopy equivalence or maybe equivalence of categories. In my experience the more common symbol for asymptotic equivalence is (\sim). It's unfortunate that Unicode named these by a specific (and in this case dubious) choice of semantics than by a name that could convey a wider meaning. I guess the LaTeX name "simeq" also conveys the idea of a meaning "similar or equal" but "similar" can mean a lot of things.
The stackexchange link also discusses several other such symbols.
=> More informations about this toot | View the thread
Why is zero plural? https://ell.stackexchange.com/questions/352455/why-is-zero-plural via https://news.ycombinator.com/item?id=42787651
Sadly, the answers describe that zero is grammatically plural (that is, that in English, one uses singular only when there is exactly one of something and plural when the number is different than one, including zero) without pointing to any historical linguistics scholarship on why that came to be.
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
On faith, religion, conjectures and Schubert calculus: https://igorpak.wordpress.com/2024/12/29/on-faith-religion-conjectures-and-schubert-calculus/, Igor Pak. This blog post is related to Pak's new preprint "Positivity of Schubert Coefficients" with Colleen Robichaux, https://arxiv.org/abs/2412.18984 . The preprint combines an unproved assumption from mathematical analysis (GRH) with one from complexity theory (the Miltersen–Vinodchandran Assumption on the non-existence of subexponential circuits for nondeterministic exponential time problems from https://doi.org/10.1007/s00037-005-0197-7) to prove that, under those assumptions, the positivity of Schubert coefficients can be verified in NP. The blog post explains how Pak went from a position of disbelieving in derandomization (lacking the faith in P=BPP that many complexity theorists hold) to a position where it is reasonable to make an assumption that implies the ability to derandomize interactive proofs (NP=AM).
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
New arXiv preprint, "Computational geometry with probabilistically noisy primitive operations", https://arxiv.org/abs/2501.07707, and new explanatory blog post, "Twenty questions with a random liar", https://11011110.github.io/blog/2025/01/16/twenty-questions-random.html
=> More informations about this toot | View the thread
New Calculator template brings interactivity to Wikipedia articles: https://en.wikipedia.org/wiki/Wikipedia:Wikipedia_Signpost/2025-01-15/Technology_report
The template basically allows the creation of small forms that allow readers to specify some numbers as input and use a formula to generate an output. It's even possible to simulate some simple algorithms step-by-step and expand the form after each step: see for instance an example of this at https://en.wikipedia.org/wiki/Euclidean_algorithm#Procedure
=> More informations about this toot | View the thread
Claire Voisin: Mathematics as a private space – from the unveiling of conjectures to worldwide recognition, https://euromathsoc.org/magazine/articles/206
Interesting interview with Voisin in the European Mathematical Society magazine, more about her life and philosophy than her mathematics.
=> More informations about this toot | View the thread
=> More informations about this toot | View the thread
=> This profile without reblog | Go to 11011110@mathstodon.xyz account This content has been proxied by September (3851b).Proxy Information
text/gemini