Every linear threshold function has a low-weight approximator
From MaRDI portal
Publication:2472433
DOI10.1007/s00037-007-0228-7zbMath1128.68043OpenAlexW2179261203MaRDI QIDQ2472433
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
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 (11)
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 ⋮ 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
