scientific article; zbMATH DE number 176873

MaRDI QIDQ4036704zbMATH OpenFDO

Authors David A. Mix Barrington

Publication date 18 May 1993

zbMATH Keywords

circuit complexity theorypolynomials over groupspolynomials over ringsrepresentation of Boolean functions by polynomials

Mathematics Subject Classification ID

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

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

(8)

• Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
• A note on a theorem of Barrington, Straubing and Thérien
• Representations of sets of Boolean functions by commutative rings
• Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky
• Boolean circuits versus arithmetic circuits
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• scientific article; zbMATH DE number 1072537 (Why is no real title available?)
• Counting classes: Thresholds, parity, mods, and fewness

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)