Every linear threshold function has a low-weight approximator

DOI10.1007/S00037-007-0228-7MaRDI QIDQ2472433zbMATH OpenOpenAlexFDO

Authors Rocco A. Servedio

Publication date 22 February 2008

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00037-007-0228-7

zbMATH Keywords

Boolean functionsChow parameterscomputational learning theorylinear threshold functions

Mathematics Subject Classification ID

Boolean functions (06E30) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32) Combinatorial optimization (90C27)

Recommendations

• Improved approximation of linear threshold functions
• The Chow parameters problem
• Learning from satisfying assignments

Cited in

(10)

• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• The Chow parameters problem
• Improved approximation of linear threshold functions
• Linear classifiers are nearly optimal when hidden variables have diverse effects
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Testing (Subclasses of) Halfspaces
• Superlinear Integrality Gaps for the Minimum Majority Problem
• Quantified Derandomization: How to Find Water in the Ocean
• Fooling Polytopes
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees

This page was built for publication: Every linear threshold function has a low-weight approximator

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