Learning unions of \(\omega(1)\)-dimensional rectangles

DOI10.1016/j.tcs.2008.06.036zbMath1181.68159OpenAlexW2118550565MaRDI QIDQ950197

Alp Atıcı, Rocco A. Servedio

Publication date: 22 October 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.036

zbMATH Keywords

boostinglearning unions of rectangleslearning with membership queries

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Cites Work

• Unnamed Item
• Learning boxes in high dimension
• Computing Boolean functions by polynomials and threshold circuits
• On using the Fourier transform to learn disjoint DNF
• On-line learning of rectangles and unions of rectangles
• Efficient learning with virtual threshold gates
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Boosting a weak learning algorithm by majority
• The bounded injury priority method and the learnability of unions of rectangles
• Threshold circuits of bounded depth
• Harmonic Analysis of Polynomial Threshold Functions
• Learnability beyond AC ⁰
• On Learning Read-k-Satisfy-j DNF
• Learning Decision Trees Using the Fourier Spectrum
• 10.1162/153244304773936072

This page was built for publication: Learning unions of \(\omega(1)\)-dimensional rectangles