2009 ExplicitConstructionofaSmallEps

• (Rabani & Shpilka, 2009) ⇒ Yuval Rabani, and Amir Shpilka. (2009). “Explicit Construction of a Small Epsilon-net for Linear Threshold Functions.” In: Proceedings of the 41st annual ACM symposium on Theory of computing. doi:10.1145/1536414.1536502

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Explicit+construction+of+a+small+epsilon-net+for+linear+threshold+functions%22+2009
• http://dl.acm.org/citation.cfm?id=1536414.1536502&preflayout=flat#citedby

Quotes

Author Keywords

• epsilon-net; explicit construction; linear threshold function

Abstract

We give explicit constructions of epsilon nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments. As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c√{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c√n.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 ExplicitConstructionofaSmallEps	Yuval Rabani Amir Shpilka			Explicit Construction of a Small Epsilon-net for Linear Threshold Functions				10.1145/1536414.1536502		2009