Some problems involving Razborov-Smolensky polynomials.

*(English)*Zbl 0769.68041Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990, Lond. Math. Lect. Note Ser. 169, 109-128 (1992).

Summary: [For the entire collection see Zbl 0754.00019.]

Several recent results in circuit complexity theory have used a representation of Boolean functions by polynomials over finite fields. Our current inability to extend these results to superficially similar situations may be related to properties of these polynomials which do not extend to polynomials over general finite rings or finite abelian groups. Here we pose a number of conjectures on the behavior of such polynomials over rings and groups, and present some partial results toward proving them.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

94C10 | Switching theory, application of Boolean algebra; Boolean functions |

06E30 | Boolean functions |