Jeremy Kun @j2kun@mathstodon.xyz

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. https://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. https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct/38832

Some notes math and gerrymandering.

https://jeremykun.com/2017/08/14/notes-on-math-and-gerrymandering/

A quickie to fend off writer's block: Boolean logic encoded in polynomials: https://jeremykun.com/2017/07/24/boolean-logic-in-quadratic-polynomials/

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

http://www.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...

http://www.openproblemgarden.org/

IBL for an introductory (classical) algebraic geometry class: https://www.artofmathematics.org/blogs/vecke/ibl-algebraic-geometry-focus-on-student-presentations

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?

#blogideainatoot

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

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

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: https://eccc.weizmann.ac.il/report/2017/115

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.

https://arxiv.org/abs/1707.01242

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: https://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/

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.

http://www.ams.org/notices/201501/rnoti-p46.pdf

https://mathstodon.xyz/media/skIeuDsYVrLmsgEOjf0

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

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