Covering Numbers for Semicontinuous Functions
Royset, Johannes O.
MetadataShow full item record
Considering the metric space of extended real-valued lower semicontinuous functions under the epi-distance, the paper gives an upper bound on the covering numbers of bounded subsets of such functions. No assumptions about continuity, smoothness, variation, and even niteness of the functions are needed. The bound is shown to be nearly sharp through the construction of a set of functions with covering numbers deviating from the upper bound only by a logarithmic factor. The analogy between lower and upper semicontinuous functions implies that identical covering numbers hold for bounded sets of the latter class of functions as well, but now under the hypo-distance metric.
This paper is in review.
Showing items related by title, author, creator and subject.
Bender, Edward A.; Butler, Jon T. (1989-01);While the use of programmable logic arrays in modern logic design is common, little is known about what PLA size provides reasonable coverage in typical applications. We address this question by showing upper and ...
Sasao, Tsutomu; Butler, Jon T. (2011-09);ÐIn an irredundant sum-of-products expression (ISOP), each product is a prime implicant (PI) and no product can be deleted without changing the function. Among the ISOPs for some function f, a worst ISOP (WSOP) is an ISOP ...
Maitra, Submahoy; Stanica, Pantelimon (2003);In 1999, Pieprzyk and Qu presented rotation symmetric (RotS) functions as components in the rounds of hashing algorithm. Later, in 2002, Cusick and St ̆anic ̆a presented further advancement in this area. This class of ...