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.
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.