Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions

DOI10.1137/090764190zbMath1209.68347OpenAlexW2153680565MaRDI QIDQ5390604

Amir Shpilka, Yuval Rabani

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090764190

zbMATH Keywords

derandomizationhitting setsexplicit construction\(\epsilon\)-net

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Theory of computing (68Q99)

Related Items (6)

Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Improved approximation of linear threshold functions ⋮ A note on stabbing convex bodies with points, lines, and flats ⋮ Paradigms for Unconditional Pseudorandom Generators

This page was built for publication: Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions