<p>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</p>

<p><strong>[NOTE]</strong> The result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, see Mark van Hoeij, <strong>Gröbner basis in Boolean rings is not P-SPACE</strong>, arXiv:<a href="http://arxiv.org/abs/1502.07220">1502.07220</a>, 2015.</p>

<p><strong>[NOTE]</strong> 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.</p>

CC BY-SA 3.0
2011-05-12T08:17:32.587Z
2015-02-26T10:30:23.380Z
2015-02-26T10:30:23.380Z
Martin Schwarz
<p><em>Just heard during the 8F workshop</em></p>

<p><a href="http://www.mit.edu/~medard/mpapers/An%20AlgebraicApproach.pdf?tp=&amp;arnumber=1019253">The original proof</a> that network coding can be implemented in a flow network uses Gröbner bases.</p>

CC BY-SA 3.0
2011-05-16T20:17:39.503Z
2011-05-16T20:17:39.503Z
Suresh Venkat
<p>Gröbner bases have been applied to constraint satisfaction problems (see this <a href="http://gow.epsrc.ac.uk/ViewGrant.ASPx?Grant=EP/D032636/1" rel="nofollow">grant</a>).  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 <a href="http://www-spiral.lip6.fr/MACIS2007/Papers/submission_7.pdf" rel="nofollow">Jefferson, Jeavons, Green, and van Dongen</a>, presented at MACIS 2007 (journal version: AMAI <strong>67</strong> 359–382, 2013, doi:<a href="http://dx.doi.org/10.1007/s10472-013-9365-7" rel="nofollow">10.1007/s10472-013-9365-7</a>), which discusses some of the issues.</p>

CC BY-SA 3.0
2011-05-13T17:51:10.953Z
2014-02-28T18:06:29.230Z
2014-02-28T18:06:29.230Z
András Salamon
<p>There is an interesting Springer volume on applications of Gröbner bases in coding and cryptography:</p>

<ul>
<li><a href="http://www.springer.com/mathematics/algebra/book/978-3-540-93805-7">Gröbner Bases, Coding, and Cryptography</a>, / Sala, M.; Mora, T.; Perret, L.; Sakata, S.; Traverso, C. (Eds.).</li>
</ul>

<p>Personally I'm doing my research in the algorithms for computing ideals of error locator polynomials (quite well-known concept in coding theory, especially syndrome decoding). In the case of codes from algeraic geometry error locators ideal is usually an ideal of polynomial from several variables — that's the place, where Gröbner Bases play central role. In the abovementioned volume most interesting part for me is the S. Sakata's description of BMS-algorithm and a survey of its applications for decoding algebraic geometry codes.</p>

CC BY-SA 3.0
2011-05-14T22:03:07.077Z
2011-05-14T22:03:07.077Z
Artem Pelenitsyn
<p>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 (<a href="http://arxiv.org/abs/1108.3383">arXiv version</a>).</p>

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

<p>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 <a href="http://reference.wolfram.com/mathematica/ref/GroebnerBasis.html">Mathematica's GroebnerBasis</a>).</p>

CC BY-SA 3.0
2011-09-10T21:58:51.980Z
2011-09-10T23:14:47.357Z
2011-09-10T23:14:47.357Z
Tyson Williams
<p><a href="http://homepages.inf.ed.ac.uk/s0793114/publications.html">Grant Passmore</a> and others write about them in the context of SMT solvers. I'm not an expert in Groebner bases nor in SMT solvers, so it's hard for me to evaluate how well this reference answers your question.</p>

CC BY-SA 3.0
2011-05-12T13:00:35.847Z
2011-05-12T14:59:28.653Z
2011-05-12T14:59:28.653Z
Ohad Kammar
<p>In proof complexity the use of Gröbner bases has been proposed by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2402">Clegg, Edmonds, Impagliazzo</a> to refute CNFs. There are cases in which this proof system outperforms Resolution exponentially but it does not seem to me that there is a real performance improvement for general instances. </p>

<p>It is also true that many of the lower bounds for Resolution hold for Polynomial Calculus (a proof system based on Gröbner bases).  The exceptions usually are built for the characteristic of the underlying field. This means that working in $GF(2)$ can help you on some formulas but not on others. </p>

<p>Yet Polynomial Calculus has not been studied as much as Resolution, thus well tested heuristics are not available.</p>

<p>See also <a href="http://martinralbrecht.files.wordpress.com/2010/10/phd.pdf">this</a> this for application in cryptanalysyis (I don't know very much about that).</p>

CC BY-SA 3.0
2011-09-13T11:22:37.183Z
2011-09-13T11:22:37.183Z
MassimoLauria
<p>The following paper can be seen as one application.</p>
<ul>
<li>Gunnar Carlsson, Gurjeet Singh, Afra Zomorodian: Computing Multidimensional Persistence. Journal of Computational Geometry, 1(1) 2010, pages 72-100. <a href="https://doi.org/10.20382/jocg.v1i1a6" rel="nofollow noreferrer">https://doi.org/10.20382/jocg.v1i1a6</a></li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2011-05-12T07:49:10.983Z
2022-07-03T06:32:51.900Z
2022-07-03T06:32:51.900Z
Yoshio Okamoto
<p>Alekseyev and Pevzner use them in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.3719&amp;rep=rep1&amp;type=pdf">this paper</a> to compute the $k$-break distance between two genomes in linear time. Loosely speaking, that distance is defined as the minimum number of times you need to cut a given genome into $k$ pieces and rearrange them in order to transform that genome into another given one.</p>

CC BY-SA 3.0
2011-05-12T08:12:55.240Z
2011-05-12T08:12:55.240Z
Anthony Labarre
<p>Grobner bases are used for the fastest list decoding algorithms for Reed-Solomon codes:
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&amp;rep=rep1&amp;type=pdf" rel="noreferrer">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&amp;rep=rep1&amp;type=pdf</a></p>

CC BY-SA 3.0
2015-06-29T21:56:16.013Z
2015-06-29T21:56:16.013Z
Dana Moshkovitz
<p>Gröbner bases have been successfully used to solve important problems in multiple view geometry in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.9247&amp;rep=rep1&amp;type=pdf">computer vision</a>.</p>

CC BY-SA 3.0
2011-05-17T01:23:12.587Z
2011-05-17T01:23:12.587Z
Jacob
<p>Following <a href="http://arxiv.org/pdf/1502.05912.pdf" rel="nofollow">http://arxiv.org/pdf/1502.05912.pdf</a> sometimes grobner basis are used to decide isomorphism (when graphs are encoded by systems of equations). But this joins the use of grobner basis in refutating CNFS. </p>

CC BY-SA 3.0
2015-02-27T08:10:19.770Z
2015-02-27T08:10:19.770Z
M. kanté
<p>Does anyone know of interesting applications of <a href="http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis">Gröbner bases</a> to theoretical computer science?</p>

<p>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).</p>

CC BY-SA 3.0
2011-05-12T01:30:26.860Z
There's the obvious: they extend gaussian elimination to compute solutions to systems of multivariate polynomials (output by Buchberger's algorithm). Solving such systems are useful in certain types of cryptanalysis and in relinearization attacks.
Ross Snider
CC BY-SA 3.0
2011-05-12T01:38:04.280Z
Also, scholarpedia gives a good list of applications in TCS. They can be used to find solutions to certain linear integer optimization problems, it lists a reference to coding theory through "Gröbner Bases and Applications." They include more: in robotics and software engineering. It's really a good list.
Ross Snider
CC BY-SA 3.0
2011-05-12T01:44:52.353Z
I forgot to include the link: http://www.scholarpedia.org/article/Groebner_basis
Ross Snider
CC BY-SA 3.0
2011-05-12T03:07:16.083Z
Nice question! I'm also interested in the applications of Gröbner basis.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-12T04:25:49.757Z
@Ross, comment -> answer ?
Suresh Venkat
CC BY-SA 3.0
2011-05-12T06:25:00.127Z
Gröbner bases, 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.
Martin Schwarz
CC BY-SA 3.0
2011-05-12T07:40:34.703Z
An application is in cryptanalysis of certain algebraic ciphers, such as AES. See [Gröbner Bases, Coding, and Cryptography](http://www.amazon.com/dp/3642101003) and chapter 6 of [Algebraic Aspects of the Advanced Encryption Standard](http://www.amazon.com/dp/1441937293).
Sadeq Dousti
<cc.complexity-theory><reference-request><algebra><polynomials>
Gröbner bases in TCS?
Dana Moshkovitz
# Gröbner bases in TCS?

(Asked by: username_0 on 2011-05-12)

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

**Tags:** cc.complexity-theory, reference-request, algebra, polynomials
> **Comments:**
> **username_1**: There's the obvious: they extend gaussian elimination to compute solutions to systems of multivariate polynomials (output by Buchberger's algorithm). Solving such systems are useful in certain types of cryptanalysis and in relinearization attacks.  
> **username_1**: Also, scholarpedia gives a good list of applications in TCS. They can be used to find solutions to certain linear integer optimization problems, it lists a reference to coding theory through "Gröbner Bases and Applications." They include more: in robotics and software engineering. It's really a good list.  
> **username_1**: I forgot to include the link: http://www.scholarpedia.org/article/Groebner_basis  
> **username_2**: Nice question! I'm also interested in the applications of Gröbner basis.  
> **username_3**: @Ross, comment -> answer ?  
> **username_4**: Gröbner bases, 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.  
> **username_5**: An application is in cryptanalysis of certain algebraic ciphers, such as AES. See [Gröbner Bases, Coding, and Cryptography](http://www.amazon.com/dp/3642101003) and chapter 6 of [Algebraic Aspects of the Advanced Encryption Standard](http://www.amazon.com/dp/1441937293).  

---

## 12 answers

### Answer by username_4 on 2011-05-12. Score: 26

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.


---

### Answer by username_7 on 2011-05-14. Score: 15

There is an interesting Springer volume on applications of Gröbner bases in coding and cryptography:

* [Gröbner Bases, Coding, and Cryptography](http://www.springer.com/mathematics/algebra/book/978-3-540-93805-7), / Sala, M.; Mora, T.; Perret, L.; Sakata, S.; Traverso, C. (Eds.).

Personally I'm doing my research in the algorithms for computing ideals of error locator polynomials (quite well-known concept in coding theory, especially syndrome decoding). In the case of codes from algeraic geometry error locators ideal is usually an ideal of polynomial from several variables — that's the place, where Gröbner Bases play central role. In the abovementioned volume most interesting part for me is the S. Sakata's description of BMS-algorithm and a survey of its applications for decoding algebraic geometry codes.


---

### Answer by username_3 on 2011-05-16. Score: 14

*Just heard during the 8F workshop*

[The original proof](http://www.mit.edu/~medard/mpapers/An%20AlgebraicApproach.pdf?tp=&arnumber=1019253) that network coding can be implemented in a flow network uses Gröbner bases.


---

### Answer by username_6 on 2011-05-13. Score: 12

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.


---

### Answer by username_8 on 2011-09-10. Score: 10

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


---

### Answer by username_9 on 2011-05-12. Score: 9

[Grant Passmore](http://homepages.inf.ed.ac.uk/s0793114/publications.html) and others write about them in the context of SMT solvers. I'm not an expert in Groebner bases nor in SMT solvers, so it's hard for me to evaluate how well this reference answers your question.


---

### Answer by username_10 on 2011-09-13. Score: 9

In proof complexity the use of Gröbner bases has been proposed by [Clegg, Edmonds, Impagliazzo](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2402) to refute CNFs. There are cases in which this proof system outperforms Resolution exponentially but it does not seem to me that there is a real performance improvement for general instances.

It is also true that many of the lower bounds for Resolution hold for Polynomial Calculus (a proof system based on Gröbner bases). The exceptions usually are built for the characteristic of the underlying field. This means that working in $GF(2)$ can help you on some formulas but not on others.

Yet Polynomial Calculus has not been studied as much as Resolution, thus well tested heuristics are not available.

See also [this](http://martinralbrecht.files.wordpress.com/2010/10/phd.pdf) this for application in cryptanalysyis (I don't know very much about that).


---

### Answer by username_11 on 2011-05-12. Score: 9

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.


---

### Answer by username_12 on 2011-05-12. Score: 7

Alekseyev and Pevzner use them in [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.3719&rep=rep1&type=pdf) to compute the $k$-break distance between two genomes in linear time. Loosely speaking, that distance is defined as the minimum number of times you need to cut a given genome into $k$ pieces and rearrange them in order to transform that genome into another given one.


---

### Answer by username_0 on 2015-06-29. Score: 6

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>


---

### Answer by username_13 on 2011-05-17. Score: 5

Gröbner bases have been successfully used to solve important problems in multiple view geometry in [computer vision](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.9247&rep=rep1&type=pdf).


---

### Answer by username_14 on 2015-02-27. Score: 1

Following <http://arxiv.org/pdf/1502.05912.pdf> sometimes grobner basis are used to decide isomorphism (when graphs are encoded by systems of equations). But this joins the use of grobner basis in refutating CNFS.


---

