An interesting tidbit. Let n, k be integers with k < n. If you want to write the majority function on n bits as a "majority of majorities," where the base majorities only inspect k bits, you need k to be at least n^(4/5).

This is a cool, short paper giving an intuitive proof of the correctness of Strassen's matrix multiplication algorithm. arxiv.org/pdf/1708.08083.pdf

It boils down to combining a rotation matrix with an associated non-eigenvector to construct two bases whose multiplication table only involves 7 matrices, due to the symmetries of the rotation. Hence the "7 multiplications suffice" trick.

It seems the recent attempt at P vs. NP has been deemed incorrect. Not surprising, but interesting how the discussion went. cstheory.stackexchange.com/que

This is cool: "Spliddit" is a website that performs fair division mechanisms from math, game theory, economics literature. So if you want to split rent, or divide some goods, there's an app for that

spliddit.org/

Today I learned there is an "Open Problem Garden", which appears to be a mostly derelict wiki listing open problems and progress on them. I wish something like this were more user friendly and actively maintained, and I have half a mind to do it myself...

openproblemgarden.org/

Turns out, hard to visualize 1M polygonal lines with d3. Got something working, but now sorta not as interested in this particular representation. Maybe something more like a heatmap of random walks?

Show thread

Recreate this collatz conjecture diagram, but with an interactive visualization that allows one to modify the parameters involved, up to 1M points mathstodon.xyz/media/YCfwHRXKt

Like, doing this just feels weird: \( \bigcirc_{i=1}^nf_i := f_1 \circ f_2 \circ \dots \circ f_n \)

Show thread

Idle thought: with the exception of \( \sum \) and \( \prod \), transforming an associative binary operation into an agglomerative "summation notation" is just making the symbol big and adding sub/superscripts. E.g., \( \bigotimes_{i=0}^n v_i \). It's strange to me that this applies to non-commutative operators ( \( \wedge \) ), but also that there are many binary operations where this rule can't be applied due to limitations of the syntax (bracket operators, function composition, modulo).

The restrictions to "tame distributions" generating the data is, of course, because even weakly learning threshold functions under adversarial noise is known to be NP-hard, and this recent paper extends this to all constant-degree polynomial threshold functions: eccc.weizmann.ac.il/report/201

Show thread

This looks like a really interesting paper for learning under tame distributions with "nasty noise." The core idea is that you can estimate a bounded function's low-degree (binary) Fourier coefficients, sometimes called "Chow Parameters," by identifying and removing outliers that disagree with the approximation of the data provided by the top eigenvector of a particular matrix.

arxiv.org/abs/1707.01242

Jeremy Kun boosted

I recently read Michèle Audin's book Remembering Sofya Kovalevskaya. It was a really interesting book. Not exactly biography, not exactly memoir, not exactly math. Has anyone here read it? I'd be interested in your reactions. This is my review: blogs.scientificamerican.com/r

TIL that the Weil Pairing of algebraic geometry has a concrete application to so-called Identity Based Encryption (IBE), discovered in 2001 by Boneh and Franklin, solving a 17 year old problem posed by Shamir. Matthew Green gives a great introduction to what IBE (and related techniques) can do: blog.cryptographyengineering.c

Jeremy Kun boosted

A graphon is a limit sequence of (adjacency matrices of) finite graphs, pictured as a function on the unit square. This also works for graph distributions, such as Erdos-Renyi and preferential attachment graphs (pictured below).

Problems in extremal graph theory (eg. find the minimum number of 4 cycles occurring in a graph with \( \Omega(n^2) \) edges) translate nicely to graphons, and vice versa.

ams.org/notices/201501/rnoti-p

mathstodon.xyz/media/skIeuDsYV

Jeremy Kun boosted

Time to justify my presence here...

The Heesch number of a shape is the maximum number of layers of copies of that shape by which you can surround it. Heesch's Problem asks which positive integers can be Heesch numbers. I'll show a few fun new results over a series of blog posts; today, I offer a basic introduction to the topic. isohedral.ca/heesch-numbers-pa

mathstodon.xyz/media/qc0LaKFTr

Math genealogy visualizer now supports finding the closest common ancestor of two mathematicians.

j2kun.github.io/math-genealogy/index.html

Show more
Mathstodon

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