Extremal properties of polynomial threshold functions

DOI10.1016/j.jcss.2007.06.021zbMath1131.94035OpenAlexW2097287345MaRDI QIDQ2475403

Ryan O'Donnell, Rocco A. Servedio

Publication date: 11 March 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.021

zbMATH Keywords

Boolean functionssign-representationpolynomial threshold functionspolynomial threshold function degreepolynomial threshold function density

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (9)

Expander-based cryptography meets natural proofs ⋮ Combined weight and density bounds on the polynomial threshold function representation of Boolean functions ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Unbounded-error quantum query complexity ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unnamed Item ⋮ On neuronal capacity ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The threshold order of a Boolean function
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• The expressive power of voting polynomials
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• A note on quantum black-box complexity of almost all Boolean functions
• PP is closed under intersection
• Classification by polynomial surfaces
• Ramsey's theorem for a class of categories
• An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
• Harmonic Analysis of Polynomial Threshold Functions
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• SeparatingPH fromPP by relativization
• Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
• Learning DNF in time
• Probability Inequalities for Sums of Bounded Random Variables
• Quantum lower bounds by polynomials
• Enumeration of Seven-Argument Threshold Functions
• New degree bounds for polynomial threshold functions
• Natural proofs

This page was built for publication: Extremal properties of polynomial threshold functions