On the complexity of balanced Boolean functions

DOI10.1016/S0020-0190(99)00061-7MaRDI QIDQ1606934zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 25 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(99)00061-7

zbMATH Keywords

balanced Boolean functions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the complexity of restrictions of Boolean functions
• On complexity of a particular Boolean functions class
• scientific article; zbMATH DE number 4035741
• On the multiplicative complexity of Boolean functions
• scientific article; zbMATH DE number 5504485
• On estimates on the complexity of restrictions of Boolean functions
• On the combinational complexity of certain symmetric Boolean functions
• scientific article; zbMATH DE number 4012495
• On the complexity of Boolean functions with small number of ones
• On the multiplicative complexity of some Boolean functions

Cited in

(10)

• On the computational complexity of some classical equivalence relations on boolean functions
• scientific article; zbMATH DE number 4218320 (Why is no real title available?)
• scientific article; zbMATH DE number 919283 (Why is no real title available?)
• On the positive and the inversion complexity of Boolean functions
• scientific article; zbMATH DE number 5504485 (Why is no real title available?)
• On the parity complexity measures of Boolean functions
• Hilbert function and complexity lower bounds for symmetric Boolean functions
• Bounds on the Fourier coefficients of the weighted sum function
• On the nonlinearity of the sequence of signs of Kloosterman sums
• Balancedness of MSO transductions in polynomial time

This page was built for publication: On the complexity of balanced Boolean functions

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