Harmonic Analysis of Polynomial Threshold Functions
From MaRDI portal
DOI10.1137/0403015zbMATH Open0695.94022OpenAlexW2097575812MaRDI QIDQ3472059FDOQ3472059
Authors: 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
Recommendations
lower boundsBoolean functionbent functionscircuit complexitypolynomial threshold functionslinear threshold functionsHarmonic analysis of Boolean functions
Numerical methods for trigonometric approximation and interpolation (65T40) Analytic circuit theory (94C05)
Cited In (51)
- Depth-efficient threshold circuits for multiplication and symmetric function computation
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
- Learning fixed-dimension linear thresholds from fragmented data
- On the computational power of depth-2 circuits with threshold and modulo gates
- A characterization of 2-threshold functions via pairs of prime segments
- Threshold circuits of small majority-depth
- Extremal properties of polynomial threshold functions
- Separation results for Boolean function classes
- Lower bounds for linear decision lists
- Sign-representation of Boolean functions using a small number of monomials
- On the power of a threshold gate at the top
- Noise sensitivity of Boolean functions and applications to percolation
- Characterization of multiple-valued threshold functions in the Vilenkin-Chrestenson basis
- Minimal sign representation of Boolean functions: algorithms and exact results for low dimensions
- Evaluating spectral norms for constant depth circuits with symmetric gates
- Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
- Existence and efficient construction of fast Fourier transforms on supersolvable groups
- A short list of equalities induces large sign-rank
- Bounds on the Fourier coefficients of the weighted sum function
- Spectral properties of threshold functions
- On XOR lemmas for the weight of polynomial threshold functions
- The expressive power of voting polynomials
- Bent functions and random Boolean formulas
- Threshold circuit lower bounds on cryptographic functions
- Title not available (Why is that?)
- Majority gates vs. general weighted threshold gates
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Nearly optimal solutions for the Chow parameters problem and low-weight approximation of halfspaces
- New degree bounds for polynomial threshold functions
- Self-predicting Boolean functions
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Asymptotics of the number of 2-threshold functions
- Geometric arguments yield better bounds for threshold circuits and distributed computing
- A review of combinatorial problems arising in feedforward neural network design
- Learning with queries corrupted by classification noise
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Degree-uniform lower bound on the weights of polynomials with given sign function
- Polynomial threshold functions and Boolean threshold circuits
- Lower bounds for modular counting by circuits with modular gates
- Polynomial threshold functions and Boolean threshold circuits
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
- On small depth threshold circuits
- A Threshold Function for Harmonic Update
- An Upper Bound on the Minimum Number of Monomials Required to Separate Dichotomies of {−1, 1}n
- Title not available (Why is that?)
- Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky
- Polynomial threshold functions, hyperplane arrangements, and random tensors
- Learning unions of \(\omega(1)\)-dimensional rectangles
- Unconditional lower bounds for learning intersections of halfspaces
- A note on the power of majority gates and modular gates
This page was built for publication: Harmonic Analysis of Polynomial Threshold Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3472059)
