๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The complexity of approximating a nonlinear program

โœ Scribed by Mihir Bellare; Phillip Rogaway

Book ID
105250213
Publisher
Springer-Verlag
Year
1995
Tongue
English
Weight
940 KB
Volume
69
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

The Complexity of Approximating the Entr
The Complexity of Approximating the Entropy
โœ Batu, Tugkan; Dasgupta, Sanjoy; Kumar, Ravi; Rubinfeld, Ronitt ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 236 KB
On the complexity of approximating the V
On the complexity of approximating the VC dimension
โœ Elchanan Mossel; Christopher Umans ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 181 KB

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: 3 -hard to approximate to within a factor 2 ร€ e for all e > 0; \* approximable in AM to within a factor 2; and \* AM-hard to appr

The Space Complexity of Approximating th
The Space Complexity of Approximating the Frequency Moments
โœ Noga Alon; Yossi Matias; Mario Szegedy ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 172 KB

The frequency moments of a sequence containing m i elements of type i, 1 i n, are the numbers F k = n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers F k , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it