Question: Does anyone know of interesting applications of [Gröbner bases](http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis) to theoretical computer science?

Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was wondering whether some tractable special cases were used to provide efficient algorithms/constructions/proofs in TCS or TCS-related areas (combinatorics, coding theory).

Answer: 
Gröbner bases have been applied to constraint satisfaction problems (see this [grant](http://gow.epsrc.ac.uk/ViewGrant.ASPx?Grant=EP/D032636/1)). At this point Gröbner basis techniques do not appear to be useful for the applications of constraint satisfaction, since they are competing with mature search heuristics, consistency enforcement techniques, and efficient special purpose propagators -- not to mention good general-purpose SAT solvers. However, I think there are definitely theoretical uses waiting to be discovered, specifically when the Gröbner basis has reasonable size. See also the paper by [Jefferson, Jeavons, Green, and van Dongen](http://www-spiral.lip6.fr/MACIS2007/Papers/submission_7.pdf), presented at MACIS 2007 (journal version: AMAI **67** 359–382, 2013, doi:[10.1007/s10472-013-9365-7](http://dx.doi.org/10.1007/s10472-013-9365-7)), which discusses some of the issues.
I used a Gröbner basis to help find a short proof of a new dichotomy theorem for #CSP problems over 3-regular graphs with a single binary constraint function that has complex weights ([arXiv version](http://arxiv.org/abs/1108.3383)).

There is natural equivalence relation over the set of constraint functions, namely, $f \sim g$ if $\#\operatorname{CSP}(f) = \#\operatorname{CSP}(g)$ for all possible instance graphs. For 3-regular graphs, there are fewer equivalence classes than would otherwise exist over all possible graphs. Since a dichotomy theorem only needs to prove the complexity of one constrain function in each equivalence class, this leads to a shorter proof.

The Gröbner basis is used to convert from the initial four variables needed to define a binary function to six "symmetrized variables" that are invariant in each equivalence class (see section D of the paper linked above). However, the Gröbner basis is not mentioned in the paper since its only purpose was the automated transformation from the initial four variables to the six symmetrized variables in various polynomials (which was preformed by [Mathematica's GroebnerBasis](http://reference.wolfram.com/mathematica/ref/GroebnerBasis.html)).