scientific article; zbMATH DE number 176873

MaRDI QIDQ4036704zbMATH OpenFDO

Authors David A. Mix Barrington

Publication date 18 May 1993

zbMATH Keywords

polynomials over ringscircuit complexity theorypolynomials over groupsrepresentation of Boolean functions by polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Recommendations

• Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky
• scientific article; zbMATH DE number 2081114
• scientific article; zbMATH DE number 1072537
• Certain problems associated with Boolean polynomials
• Representing Boolean functions as polynomials modulo composite numbers

Cited in

(5)

• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• Counting classes: Thresholds, parity, mods, and fewness
• Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
• A note on a theorem of Barrington, Straubing and Thérien
• Boolean circuits versus arithmetic circuits

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036704)