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.
The following paper can be seen as one application.

* Gunnar Carlsson, Gurjeet Singh, Afra Zomorodian: Computing Multidimensional Persistence. Journal of Computational Geometry, 1(1) 2010, pages 72-100. <https://doi.org/10.20382/jocg.v1i1a6>

I see the authors use Buchberger's algorithm as a subroutine, and exploit the structure of their problem to prove that the running time is polynomially bounded.