Every linear threshold function has a low-weight approximator

DOI10.1007/S00037-007-0228-7zbMath1128.68043OpenAlexW2179261203MaRDI QIDQ2472433

Rocco A. Servedio

Publication date: 22 February 2008

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

computational learning theoryBoolean functionslinear threshold functionsChow parameters

Mathematics Subject Classification ID

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

Related Items (12)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Fooling Polytopes ⋮ Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Improved approximation of linear threshold functions ⋮ The inverse Shapley value problem ⋮ Linear classifiers are nearly optimal when hidden variables have diverse effects ⋮ Testing (Subclasses of) Halfspaces ⋮ Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees ⋮ A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

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