Hilbert function and complexity lower bounds for symmetric Boolean functions

DOI10.1006/INCO.1999.2798MaRDI QIDQ1854301zbMATH OpenOpenAlexFDO

Authors A. Bernasconi, Lavinia Egidi

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/482feaaec79ee7c5dea2930ea63313cbc38f73c3

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Boolean functions (06E30) Hilbert-Samuel and Hilbert-Kunz functions; Poincaré series (13D40)

Recommendations

• On the complexity of balanced Boolean functions
• Concrete Multiplicative Complexity of Symmetric Functions
• On the annihilators of Boolean polynomials
• Tight bounds for the multiplicative complexity of symmetric functions
• scientific article; zbMATH DE number 1303958

Cited in

(5)

• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Gröbner bases for complete uniform families
• Bayer noise symmetric functions and some combinatorial algebraic structures
• Some combinatorial applications of Gröbner bases
• Algebraic properties of modulo \(q\) complete \(\ell \)-wide families

Describes a project that uses

Uses Software

• Macaulay2

This page was built for publication: Hilbert function and complexity lower bounds for symmetric Boolean functions

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