Harmonic Analysis of Polynomial Threshold Functions

DOI10.1137/0403015zbMath0695.94022OpenAlexW2097575812MaRDI QIDQ3472059

Jehoshua Bruck

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/34d02f5735184e3c18970d346ccf759795e82b08

zbMATH Keywords

bent functionslower boundsBoolean functioncircuit complexitylinear threshold functionspolynomial threshold functionsHarmonic analysis of Boolean functions

Mathematics Subject Classification ID

Related Items (47)

Separation results for Boolean function classes ⋮ Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ The expressive power of voting polynomials ⋮ A review of combinatorial problems arising in feedforward neural network design ⋮ Sign-representation of Boolean functions using a small number of monomials ⋮ On the power of a threshold gate at the top ⋮ A characterization of 2-threshold functions via pairs of prime segments ⋮ Combined weight and density bounds on the polynomial threshold function representation of Boolean functions ⋮ On small depth threshold circuits ⋮ Bounds on the Fourier coefficients of the weighted sum function ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces ⋮ Evaluating spectral norms for constant depth circuits with symmetric gates ⋮ Geometric arguments yield better bounds for threshold circuits and distributed computing ⋮ Bent functions and random Boolean formulas ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky ⋮ Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\) ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ Unnamed Item ⋮ Depth-efficient threshold circuits for multiplication and symmetric function computation ⋮ Minimal Sign Representation of Boolean Functions: Algorithms and Exact Results for Low Dimensions ⋮ Self-Predicting Boolean Functions ⋮ New degree bounds for polynomial threshold functions ⋮ A note on the power of majority gates and modular gates ⋮ Learning unions of \(\omega(1)\)-dimensional rectangles ⋮ Existence and efficient construction of fast Fourier transforms on supersolvable groups ⋮ Extremal properties of polynomial threshold functions ⋮ Noise sensitivity of Boolean functions and applications to percolation ⋮ Threshold circuit lower bounds on cryptographic functions ⋮ Majority gates vs. general weighted threshold gates ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Degree-uniform lower bound on the weights of polynomials with given sign function ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ Asymptotics of the number of 2-threshold functions ⋮ On the computational power of depth-2 circuits with threshold and modulo gates ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Threshold circuits of small majority-depth ⋮ Lower bounds for modular counting by circuits with modular gates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Upper Bound on the Minimum Number of Monomials Required to Separate Dichotomies of {−1, 1}ⁿ ⋮ Learning with queries corrupted by classification noise ⋮ Learning fixed-dimension linear thresholds from fragmented data ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors ⋮ Spectral properties of threshold functions

This page was built for publication: Harmonic Analysis of Polynomial Threshold Functions