Some papers I liked #3

In my two previous “some papers I liked” posts, I featured mostly preprints from arXiv because I liked (and still kind of like) to procrastinate by browsing through documents published there. I don’t do that often anymore because:

1. I’ve realized that my understanding of a large portion of those papers is too rudimentary to call it time well spent;
2. There is a surprising amount of absolute crap on arXiv (maybe not a lot but still, surprisingly much).

I will elaborate on the second point in the last section of this post, but before I do, I’d like to recommend some articles I’ve found interesting. This time (and from now on) I’m not restricting myself to computer science / discrete mathematics papers. Still, if I (a CS & Math student) found them interesting, maybe you will too, my dear reader.

Computer Science#

• A couple of people wondered if the New York Times games are (computationally) hard and decided to write a paper about it¹.
• The Busy Beaver Challenge wrapped up a while ago, and here is a nice report from the main contributors².
• It turns out that the AGENTS.md files don’t really improve the code spat out by LLMs³.
• egg is a wonderful attempt to make Lean proofs more human-like⁴.

Math#

• Apparently, a calculator with only one special operation is sufficient for everything a calculator should do⁵.

Other#

• Sleeping well is way less important than thinking that you slept well⁶. ($)

Example of crap on arXiv#

I’ve seen dozens of articles like this, but here I’ll describe just the most recent one.

According to this paper, $\mathsf{W[1]} = \mathsf{FPT}$ (and thus the Exponential Time Hypothesis does not hold). My first thought on that statement was “hm, seems like bullshit”, but I decided to investigate the matter further. It was time well spent because now I can say that it is, indeed, bullshit.

Luckily for my time management, the error is in Lemma 1, on the second page of the paper. The author writes that the number of $k$-matchings in a graph $G$ is equal to $$ \frac{1}{k!} \cdot \frac{1}{(n-k)!} \cdot \frac{1}{2^k}\sum_{i = 1}^{n!}\sum_{\sigma \in P(n,k)} \prod_{j = 1}^{k} A_{[\sigma(j),\phi_i(\sigma(j))]} $$ where $n$ is the number of vertices, $A$ is the adjacency matrix, and $\phi_i$ is simply the $i$-th permutation of vertices. This is clearly wrong; it suffices to check $k = 2, G = K_3$ to realize as much.

Later on, the author tries to intimidate us with way too many $\Sigma$ and $\Pi$ signs, but honestly, I did not care enough to keep reading.