\relax 
\bibstyle{plainnat}
\bibstyle{alpha}
\citation{km91}
\citation{gl89}
\citation{ja94}
\citation{ak91}
\citation{kea93}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction and Overview}{360}}
\newlabel{sec-intro}{{1}{360}}
\citation{ad93}
\citation{sv88}
\citation{gs95}
\citation{dg95}
\citation{bjt99}
\citation{bkw00}
\citation{shsh95}
\citation{jss97}
\citation{kea93}
\citation{bfjkmr94}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Relation to Other Works}{362}}
\newlabel{sec-relation}{{1.1}{362}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Organization}{362}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Definitions and Notation}{363}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}General Notation}{363}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Learning Models}{363}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1}The PAC Model}{363}}
\citation{al88}
\citation{al88}
\citation{lai88}
\citation{sl88}
\citation{gks94}
\newlabel{bounded}{{1}{364}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2}Noise Models}{364}}
\citation{kea93}
\citation{kea93}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.3}The Statistical Query Learning Model}{365}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Estimating Expected Values}{365}}
\newlabel{subsec-eev}{{2.3}{365}}
\newlabel{lem-hoeffding}{{2}{366}}
\newlabel{cor-amean}{{3}{366}}
\newlabel{rem-est-sq}{{4}{366}}
\newlabel{RV-SQ}{{5}{366}}
\citation{lmn89}
\citation{mansour}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}The Fourier Transform}{367}}
\newlabel{sec-def-fourier}{{2.4}{367}}
\citation{km91}
\newlabel{fact-fourier-app}{{6}{368}}
\citation{km91}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.5}The {\tt  KM} Algorithm}{369}}
\newlabel{sec-km}{{2.5}{369}}
\newlabel{rem-km-real}{{7}{369}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Learning by Extended Statistical Queries}{369}}
\newlabel{sec-sqd-model}{{3}{369}}
\citation{kea93}
\citation{jss97}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Extending the SQ Model}{370}}
\newlabel{convert2noise}{{8}{371}}
\newlabel{equ-mqnoise}{{1}{371}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Learning with Respect to the Uniform Distribution Using Product Distributions}{371}}
\newlabel{sec-bs}{{3.2}{371}}
\newlabel{subsec-bs-def}{{3.2}{372}}
\newlabel{lem-degree-control}{{9}{372}}
\newlabel{eq-simsqd}{{2}{372}}
\newlabel{rem-non-uniform-d}{{10}{372}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}An Analogue to the {\tt  KM} Algorithm}{373}}
\newlabel{lem-p1}{{11}{373}}
\newlabel{eq-pi}{{3}{373}}
\newlabel{eq-pi-proof}{{4}{374}}
\newlabel{BS}{{12}{374}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces  Procedure {\tt  P1}}}{375}}
\newlabel{fig-p1}{{1}{375}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces  Procedure {\tt  P2}}}{376}}
\newlabel{fig-p2}{{2}{376}}
\newlabel{modifiedBS}{{13}{376}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Learning Decision Trees}{377}}
\newlabel{lem-dt-transform}{{14}{377}}
\newlabel{equ-term}{{6}{377}}
\newlabel{lem-dt-cut}{{15}{378}}
\newlabel{dt}{{16}{378}}
\newlabel{eq-dt-terms}{{7}{378}}
\citation{bfjkmr94}
\citation{ja97}
\citation{ja97}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.5}Weak DNF Learning}{379}}
\newlabel{weakparity}{{18}{379}}
\newlabel{uweakdnf}{{19}{380}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.6}Boosting the Weak \textsf  {DNF} Learner}{380}}
\newlabel{sec-DNF}{{3.6}{380}}
\newlabel{weakdnf}{{20}{380}}
\citation{fr90}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces  Freund's algorithm for boosting a weak learner in the PAC model. EX$(D_i,f)$ is a simulated example oracle.}}{382}}
\newlabel{boost}{{3}{382}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces  Learning \textsf  {DNF} in the SQ--${\@mathcal D}_{\frac  {1}{4}}$ model}}{383}}
\newlabel{sqdboost}{{4}{383}}
\citation{ks99}
\citation{bg01}
\citation{sv88}
\citation{gs95}
\citation{bjt99}
\@writefile{toc}{\contentsline {section}{\numberline {4}Learning with Attribute Noise in Membership Queries}{384}}
\newlabel{sec-att-noise}{{4}{384}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}The Noise Model and Its Properties}{384}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Offsetting Attribute Noise in the Bounded Sieve}{385}}
\newlabel{th-anbs}{{23}{385}}
\citation{gs95}
\citation{gs95}
\citation{dg95}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Coping with Attribute Noise of Unknown Rate}{386}}
\newlabel{th-an-dt}{{26}{386}}
\newlabel{eq2e}{{8}{387}}
\newlabel{eqe}{{9}{387}}
\newlabel{eq3e}{{10}{387}}
\newlabel{th-an-wdnf}{{28}{387}}
\citation{bfjkmr94}
\@writefile{toc}{\contentsline {section}{\numberline {5}Limitations of the SQ-${\@mathcal D}$ Model}{388}}
\newlabel{sec-char}{{5}{388}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Properties of Statistical Queries}{388}}
\newlabel{sec-sq-prop}{{5.1}{388}}
\newlabel{lem-sq-simple}{{30}{388}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}The Characterization}{389}}
\newlabel{th-sq-char}{{31}{389}}
\citation{bfjkmr94}
\newlabel{sqdchar}{{32}{390}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Applications}{390}}
\newlabel{sqapp}{{33}{390}}
\newlabel{par-k}{{34}{390}}
\citation{bkw00}
\newlabel{e1}{{11}{391}}
\newlabel{eq-i1}{{12}{391}}
\newlabel{e2}{{13}{391}}
\newlabel{bias}{{36}{392}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Conclusions and Open Problems}{392}}
\bibcite{ad93}{{AD93}{}{{}}{{}}}
\bibcite{al88}{{AL88}{}{{}}{{}}}
\bibcite{ak91}{{AK91}{}{{}}{{}}}
\bibcite{bs93}{{Bs93}{}{{}}{{}}}
\bibcite{bfjkmr94}{{BFJ$^+$94}{}{{}}{{}}}
\bibcite{bf01}{{BF01}{}{{}}{{}}}
\bibcite{bg01}{{BG01}{}{{}}{{}}}
\bibcite{bjt99}{{BJT99}{}{{}}{{}}}
\bibcite{bkw00}{{BKW00}{}{{}}{{}}}
\bibcite{dg95}{{DG95}{}{{}}{{}}}
\bibcite{fr90}{{Fr90}{}{{}}{{}}}
\bibcite{fs94}{{FS94}{}{{}}{{}}}
\bibcite{gks94}{{GKS94}{}{{}}{{}}}
\bibcite{gl89}{{GL89}{}{{}}{{}}}
\bibcite{gs95}{{GS95}{}{{}}{{}}}
\bibcite{ja94}{{Ja94}{}{{}}{{}}}
\bibcite{ja97}{{Ja97}{}{{}}{{}}}
\bibcite{jss97}{{JSS97}{}{{}}{{}}}
\bibcite{kea93}{{Kea93}{}{{}}{{}}}
\bibcite{km91}{{KM91}{}{{}}{{}}}
\bibcite{ks99}{{KS99}{}{{}}{{}}}
\bibcite{kss92}{{KSS92}{}{{}}{{}}}
\bibcite{lai88}{{Lai88}{}{{}}{{}}}
\bibcite{lmn89}{{LMN89}{}{{}}{{}}}
\bibcite{mansour}{{Man94}{}{{}}{{}}}
\bibcite{shsh95}{{ShSh95}{}{{}}{{}}}
\bibcite{sch90}{{Sch90}{}{{}}{{}}}
\bibcite{sl88}{{Sl88}{}{{}}{{}}}
\bibcite{sv88}{{SV88}{}{{}}{{}}}
\bibcite{v84}{{V84}{}{{}}{{}}}
\global\NAT@numberstrue