Over the past four months, I’ve collected a few papers that I want to share with you now. These papers (mostly preprints) are unlikely to be the most significant ones ever written. Instead, they often have nice pictures and are short or very well-written — which is exactly the sort of thing that might interest an undergraduate student like myself.

Computational complexity theory#

  • Col is PSPACE-complete on Triangular Grids. Kyle Burke and Craig Tennenhouse, link (9 pages)
  • Slant/Gokigen Naname is NP-complete, and Some Variations are in P. Jayson Lynch and Jack Spalding-Jamieson, link (7 pages)
  • Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete. Finn Koepke, link (12 pages)
  • A Note on the Complexity of Defensive Domination. Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk, link (11 pages)

Miscellaneous#

  • Well-quasi-orderings on word languages. Nathan Lhote, Aliaume Lopez, Lia Schütze, link (26 pages)
  • Canonical for Automated Theorem Proving in Lean. Chase Norman and Jeremy Avigad, link (15 pages, but it’s more about the software)
  • Proof or Bluff? Evaluating LLMs on 2025 USA Math Olympiad. Ivo Petrov, Jasper Dekoninck, et al., link (12 pages, but it’s more about the cool website)

Other#

And finally, two articles that are not from this year but that I came across recently.

  • A Survival Guide to Presburger Arithmetic. Christoph Haase, link (12 pages)
  • Data Reduction for Graph Coloring Problems. Bart M. P. Jansen, Stefan Kratsch, link (31 pages)

Bonus: not a paper, but Mikołaj Bojańczyk’s website. The author conducts research on logic in computer science at the University of Warsaw and puts real effort into preparing good materials for his talks and courses.