A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length

DOI10.1134/S0001434610050263zbMATH Open1317.94168MaRDI QIDQ368235FDOQ368235

Authors: Vladimir V. Podolskii, Alexander A. Sherstov 

Publication date: 18 September 2013

Published in: Mathematical Notes (Search for Journal in Brave)

Recommendations

• Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
• Degree-uniform lower bound on the weights of polynomials with given sign function
• Perceptrons of large weight
• Perceptrons of Large Weight
• A Uniform Lower Bound on Weights of Perceptrons

zbMATH Keywords

complexity theoryBoolean functiondiscrete Fourier transforminteger-valued polynomialperceptronBoolean circuitexponential gapsign function

Mathematics Subject Classification ID

Boolean functions (06E30)

Cites Work

• Title not available (Why is that?)
• The expressive power of voting polynomials
• Harmonic Analysis of Polynomial Threshold Functions
• Majority gates vs. general weighted threshold gates
• On the power of a threshold gate at the top
• Threshold circuits of bounded depth
• Complexity measures and decision tree complexity: a survey.
• PP is closed under intersection
• On the Size of Weights for Threshold Gates
• Unconditional lower bounds for learning intersections of halfspaces
• On the computational power of depth-2 circuits with threshold and modulo gates
• Computing Boolean functions by polynomials and threshold circuits
• Approximating threshold circuits by rational functions
• Perceptrons, PP, and the polynomial hierarchy
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Toward attribute efficient learning of decision lists and parities
• Title not available (Why is that?)
• A Uniform Lower Bound on Weights of Perceptrons
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Power of Threshold Circuits with Small Weights
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Rational approximation techniques for analysis of neural networks
• New degree bounds for polynomial threshold functions
• Learning intersections and thresholds of halfspaces
• Perceptrons of large weight
• On the computational power of Boolean decision lists

Cited In (5)

• On XOR lemma for polynomial threshold weight and length
• On XOR lemmas for the weight of polynomial threshold functions
• A Uniform Lower Bound on Weights of Perceptrons
• Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
• Degree-uniform lower bound on the weights of polynomials with given sign function

This page was built for publication: A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length

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