|Title||Computing Gröbner Bases in the Boolean Setting with Applications to Counting|
|Author(s)|| Anna Bernasconi, Bruno Codenotti, Valentino Crespi, Giovanni Resta|
|Type||Technical Report, Misc|
|Abstract||We take advantage of the special structure of computations in Z2 to|
develop algorithms for the computation of Groebner bases and of the Hilbert function in the Boolean setting. Natural sources of applications for our algorithms are the counting problems. We focus, as a case study, on the computation of the permanent. To this regard, one good feature of the Groebner approach is that, unlike other general methods for the exact
computation of the permanent, it is intrinsically sensitive to the structure of the specific input, and this makes it possible to use
it in order to recognize and solve efficiently several easy instances.
|Pages||209 - 218|