New upper bounds on the average PTF density of Boolean functions

DOI10.1007/978-3-642-17517-6_28MaRDI QIDQ3060742zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano

Publication date 9 December 2010

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

Full work available at URL https://doi.org/10.1007/978-3-642-17517-6_28

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Boolean functions (06E30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Extremal properties of polynomial threshold functions
• Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
• New degree bounds for polynomial threshold functions
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

Cited in

(4)

• Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
• On XOR lemmas for the weight of polynomial threshold functions
• Extremal properties of polynomial threshold functions
• Minimal sign representation of Boolean functions: algorithms and exact results for low dimensions

This page was built for publication: New upper bounds on the average PTF density of Boolean functions

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