✦ LIBER ✦

Lower Bounds for Agnostic Learning via Approximate Rank

✍ Scribed by Adam R. Klivans; Alexander A. Sherstov

Publisher: Springer
Year: 2010
Tongue: English
Weight: 523 KB
Volume: 19
Category: Article
ISSN: 1016-3328
DOI: 10.1007/s00037-010-0296-y

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Lower bounds for the approximative compl

Lower bounds for the approximative complexity

✍ Bernhard Griesser 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 440 KB

Unconditional lower bounds for learning

Unconditional lower bounds for learning intersections of halfspaces

✍ Adam R. Klivans; Alexander A. Sherstov 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 444 KB

Lower bounds for approximate polygon dec

Lower bounds for approximate polygon decomposition and minimum gap

✍ Joachim Gudmundsson; Thore Husfeldt; Christos Levcopoulos 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 67 KB

We consider the problem of decomposing polygons (with holes) into various types of simpler polygons. We focus on the problem of partitioning a rectilinear polygon, with holes, into rectangles, and show an (n log n) lower bound on the timecomplexity. The result holds for any decomposition, optimal or

Lower bounds for the ranks of CM types

✍ Liem Mai 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 396 KB

Lower bound for a diophantine approximat

Lower bound for a diophantine approximation function

✍ T. W. Cusick 📂 Article 📅 1971 🏛 Springer Vienna 🌐 English ⚖ 158 KB

Lower-Bound Estimates for Poisson-Type A

Lower-Bound Estimates for Poisson-Type Approximations

✍ V. Cekanavicius; A. Elijio 📂 Article 📅 2005 🏛 Springer 🌐 English ⚖ 176 KB