Lower Bounds on Representing Boolean Functions as Polynomials in Z_m

DOI10.1137/S0895480193255505zbMATH0841.68064OpenAlexW2097114401MaRDI QIDQ4875435FDOQ4875435

Authors Shi-Chun Tsai

Publication date 2 July 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480193255505

zbMATH Keywords

computational complexitycircuit complexityboolean function complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Representing Boolean functions as polynomials modulo composite numbers
• scientific article; zbMATH DE number 1332656
• A lower bound on the MOD 6 degree of the OR function

Cited in

(14)

• On the degree of Boolean functions as real polynomials
• Representing the Boolean OR Function by Quadratic Polynomials Modulo 6
• On the modulo degree complexity of Boolean functions
• Constructing Ramsey graphs from Boolean function representations
• Representing Boolean functions as polynomials modulo composite numbers
• On the mean evaluation of polynomially reducible Boolean functions
• Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols
• scientific article; zbMATH DE number 2081114 (Why is no real title available?)
• Polynomial Representations of Symmetric Partial Boolean Functions
• On the degree of univariate polynomials over the integers
• Circuit complexity before the dawn of the new millennium
• scientific article; zbMATH DE number 4179291 (Why is no real title available?)
• Hierarchical diagnostic classification models morphing into unidimensional `diagnostic' classification models -- a commentary
• On the modulo degree complexity of Boolean functions

This page was built for publication: Lower Bounds on Representing Boolean Functions as Polynomials in $Z_m $

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