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

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