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 basis computation, while EXPSPACE-complete in general, are in PSPACE over Boolean rings. This has applications in model-checking to replace BDDs: Quoc-Nam Tran, "A PSPACE Algorithm for Groebner Bases Computation in Boolean Rings", Proc. WASET, Vol. 35, Nov. 2008, ISSN 2070-3740

**[NOTE]** The result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, see Mark van Hoeij, **Gröbner basis in Boolean rings is not P-SPACE**, arXiv:[1502.07220](http://arxiv.org/abs/1502.07220), 2015.

**[NOTE]** The claim that the result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, is wrong. The author confuses PSPACE-computability with having a polynomial size. A PSPACE function may well have exponentially long output.
Grobner bases are used for the fastest list decoding algorithms for Reed-Solomon codes:
<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&rep=rep1&type=pdf>