Improved approximation of linear threshold functions
From MaRDI portal
Publication:371200
DOI10.1007/s00037-012-0045-5zbMath1273.68292OpenAlexW2172810949MaRDI QIDQ371200
Rocco A. Servedio, Ilias Diakonikolas
Publication date: 30 September 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0045-5
Boolean functions (06E30) Measures and integrals in product spaces (28A35) Discrete mathematics in relation to computer science (68R99)
Related Items (4)
On \(\alpha\)-roughly weighted games ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ A Polynomial Lower Bound for Testing Monotonicity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of learning intersections of two halfspaces
- On the hardness of approximating minimum vertex cover
- Halfspace matrices
- On Bernoulli decompositions for random variables, concentration bounds, and spectral localization
- Monotone circuits for monotone weighted threshold functions
- Linear function neurons: Structure and training
- Refinement of the upper bound of the constant in the central limit theorem
- Inequalities in Fourier analysis
- Boolean functions with low average sensitivity depend on few coordinates
- On the degree of Boolean functions as real polynomials
- Perceptrons, PP, and the polynomial hierarchy
- Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
- On the distribution of the Fourier spectrum of Boolean functions
- On specifying Boolean functions by labelled examples
- On the hardness of approximating Multicut and Sparsest-Cut
- Every linear threshold function has a low-weight approximator
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The Littlewood-Offord problem and invertibility of random matrices
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Theory of majority decision elements
- The Chow Parameters Problem
- Testing Halfspaces
- A Bound on the Precision Required to Estimate a Boolean Perceptron from Its Average Satisfying Assignment
- Learning Monotone Decision Trees in Polynomial Time
- Agnostically Learning Halfspaces
- On Agnostic Learning of Parities, Monomials, and Halfspaces
- A Structural Approach to Subset-Sum Problems
- Improved Lower Bounds for Embeddings into $L_1$
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- Logarithmic Sobolev Inequalities
- fast viscous convection
- On the Size of Weights for Threshold Gates
- On the Fourier spectrum of monotone functions
- Every monotone graph property has a sharp threshold
- From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
- Über ein Problem von Erdös und Moser
- Bounded Independence Fools Halfspaces
- Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions
- Learning Nested Halfspaces and Uphill Decision Trees
- Algorithmic Learning Theory
- An Approach to Single-Threshold-Element Synthesis
- On the concentration function of a sum of independent random variables
- On a lemma of Littlewood and Offord
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Improved approximation of linear threshold functions
