Extremal properties of polynomial threshold functions
From MaRDI portal
Publication:2475403
Recommendations
- Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
- New upper bounds on the average PTF density of Boolean functions
- Polynomial threshold functions and Boolean threshold circuits
- Polynomial threshold functions and Boolean threshold circuits
- New degree bounds for polynomial threshold functions
Cites work
- A note on quantum black-box complexity of almost all Boolean functions
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
- Classification by polynomial surfaces
- Enumeration of Seven-Argument Threshold Functions
- Harmonic Analysis of Polynomial Threshold Functions
- scientific article; zbMATH DE number 446494 (Why is no real title available?)
- scientific article; zbMATH DE number 46958 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1405932 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- Learning DNF in time
- Natural proofs
- New degree bounds for polynomial threshold functions
- On the degree of Boolean functions as real polynomials
- Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
- Perceptrons, PP, and the polynomial hierarchy
- Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
- PP is closed under intersection
- Probability Inequalities for Sums of Bounded Random Variables
- Quantum lower bounds by polynomials
- Ramsey's theorem for a class of categories
- Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
- SeparatingPH fromPP by relativization
- The expressive power of voting polynomials
- The threshold order of a Boolean function
Cited in
(22)- On the degree of Boolean functions as real polynomials
- Expander-based cryptography meets natural proofs
- Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
- On XOR lemmas for the weight of polynomial threshold functions
- Polynomial threshold functions and Boolean threshold circuits
- Polynomial threshold functions and Boolean threshold circuits
- Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
- New upper bounds on the average PTF density of Boolean functions
- A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
- Harmonic Analysis of Polynomial Threshold Functions
- Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
- The power of asymmetry in constant-depth circuits
- Specifying a positive threshold function via extremal points
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
- Polynomial threshold functions, hyperplane arrangements, and random tensors
- scientific article; zbMATH DE number 7250146 (Why is no real title available?)
- scientific article; zbMATH DE number 7297102 (Why is no real title available?)
- On neuronal capacity
- New degree bounds for polynomial threshold functions
- New degree bounds for polynomial threshold functions
- Unbounded-error quantum query complexity
- Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
This page was built for publication: Extremal properties of polynomial threshold functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2475403)
