Lower Bounds on Representing Boolean Functions as Polynomials in Z_m

DOI10.1137/S0895480193255505zbMATH Open0841.68064OpenAlexW2097114401MaRDI QIDQ4875435FDOQ4875435

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 (9)

• Constructing Ramsey graphs from Boolean function representations
• Circuit complexity before the dawn of the new millennium
• Title not available (Why is that?)
• Representing Boolean functions as polynomials modulo composite numbers
• On the degree of Boolean functions as real polynomials
• 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)