Recently Ke Shi and I showed that \(\mathbb{Z}_n\) can be covered by \(O\left(\frac{n}{\ell}\log n\right)\) sets of the form \(\{ax\pmod n \mid 0\leq x \leq \ell \}\), where \(a\in \mathbb{Z}_n\).

Turns out the algorithm is related to zero forcing sets. A fun concept. I found some nice slides on it.

Show thread

For a \(n\times n\) grid, the lights out game can be considered as solving a linear system over \(n^2\) variables in mod \(2\). It takes \(O(n^6)\) time. Surprisingly, there is a \(O(n^3)\) time algorithm.


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