Lower Bounds on Representing Boolean Functions as Polynomials in Z_m

DOI10.1137/S0895480193255505zbMATH Open0841.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

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

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)

Cited In (14)

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

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)