A long time ago I tried to do research in (noncommutative) ring theory. Although I have not worked in the area this millennium, I am always glad to see algebraic methods used in novel ways. One of the most interesting authors to me is Jesus de Loera, who has been involved in LattE (lattice point enumeration program that implements Barvinok’s algorithm), Groebner basis approaches to integer programming, and now using Hilbert’s Nullstellensatz to show that, for example, certain graphs are not 3-colorable.

The idea is that for a graph with $latex n$ vertices and $latex e$ edges, the property of being 3-colorable is equivalent to the solvability over $latex mathbb{C}$ of a certain set of polynomial equations in $latex n + e$ variables. The Nullstellensatz (constructive form) says that if the set is not solvable, then a certificate can be found. The worst-case upper bounds on certificate degree are doubly exponential, but for this particular problem it appears that the degree is low rather often. The paper above has lots of clever tricks to reduce the computational effort. Great stuff!