(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: monotone.dvi %%Pages: 8 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentFonts: Times-Bold Times-Roman Times-Italic Courier %%EndComments %DVIPSCommandLine: dvips monotone -o %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1998.09.10:1054 %%BeginProcSet: texc.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{ statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{ pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get} B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{ rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv} B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail} B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{ 3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{ 3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginFont: Times-Bold % @psencodingfile{ % author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry", % version = "0.6", % date = "14 April 1995", % filename = "8r.enc", % email = "kb@cs.umb.edu", % address = "135 Center Hill Rd. // Plymouth, MA 02360", % codetable = "ISO/ASCII", % checksum = "xx", % docstring = "Encoding for TrueType or Type 1 fonts to be used with TeX." % } % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are almost all in their Windows ANSI % positions, because some Windows users cannot easily reencode the % fonts, and it makes no difference on other systems. The only Windows % ANSI characters not available are those that make no sense for % typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen % (173). quotesingle and grave are moved just because it's such an % irritation not having them in TeX positions. % % (2) Remaining characters are assigned arbitrarily to the lower part % of the range, avoiding 0, 10 and 13 in case we meet dumb software. % % (3) Y&Y Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x12. % % (4) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available. % % (5) hyphen appears twice for compatibility with both ASCII and Windows. % /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /.notdef /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /.notdef /breve /minus /.notdef % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron % 0x10 /caron /dotlessi % (unusual TeX characters available in, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % very contentious; it's so painful not having quoteleft and quoteright % at 96 and 145 that we move the things normally found there down to here. /grave /quotesingle % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /.notdef /.notdef /.notdef % 0x90 /.notdef /.notdef /.notdef /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe /.notdef /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndFont %%BeginProcSet: texps.pro TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont /setfont load]cvx def}def /ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def /ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (monotone.dvi) @start /Fa 134[17 4[10 15 15 2[19 19 27 10 2[10 19 19 10 17 19 17 19 19 12[21 19 3[27 1[31 21 1[17 3[23 23 27 25 1[23 62[19 2[{TeXBase1Encoding ReEncodeFont}29 37.500000 /Times-Italic rf /Fb 75[12 29[19 27[17 19 19 1[19 19 10 15 12 1[19 19 19 29 10 19 1[10 19 19 12 17 19 17 19 17 3[12 1[12 4[27 27 23 21 25 1[21 27 27 33 23 27 15 12 1[27 21 1[27 25 25 27 6[10 19 19 19 19 19 19 19 19 19 19 1[9 12 9 2[12 12 36[21 3[{TeXBase1Encoding ReEncodeFont} 63 37.500000 /Times-Roman rf /Fc 133[20 4[25 15 18 20 2[23 25 38 13 2[13 1[23 15 20 1[20 1[23 20[30 4[36 19[23 23 23 2[11 46[{TeXBase1Encoding ReEncodeFont}21 45.833332 /Times-Bold rf /Fd 2 113 df0 D<1404140C14181430A214 6014C0A2EB0180EB0300A2EA600612B0EA300C6C5A120C5B6C5AA26C5A5B120116167E81 17>112 D E /Fe 7 121 df<134013C0EA0180A3EA0300A21206A25AA35AA25AA25AA35A A20A157E8F0F>61 D99 D110 D112 D<123E124312421270123C120612C21284127808097D880E>115 D<120CA3121812FE1218A21230A3123212341238070D7E8C0C>I120 D E /Ff 9 111 df<120412081210123012201260124012C0A8124012601220123012101208120406167D 8F0B>40 D<1280124012201230121012181208120CA81208121812101230122012401280 06167E8F0B>I<13C0A8B51280A23800C000A811127E8D15>43 D<121812F81218AA12FF 080D7D8C0E>49 D<123EEA4180EA80C012C01200A2EA0180EA03001204EA08401230EA7F 8012FF0A0D7E8C0E>I53 D<120FEA31801261EA60005A12DEEAE180EAC0C0A31260EA21 80EA1E000A0D7E8C0E>I<12E01260AC12F0040E7E8D08>108 D110 D E /Fg 134[21 3[23 14 16 18 2[21 23 35 12 23 1[12 23 1[14 18 3[21 3[14 1[14 6[28 1[30 1[25 3[28 32 7[30 9[21 21 21 21 21 21 21 21 21 21 1[10 14 3[14 14 40[{TeXBase1Encoding ReEncodeFont}37 41.666668 /Times-Bold rf /Fh 9 113 df0 D<1204120EA2121CA31238 A212301270A21260A212C0A2070F7F8F0A>48 D<000F131E393BC0618039606080403840 3100D8801A1320130EA3130B3940118040903820C0C03930C07B80390F001E001B0D7E8C 21>I<124012C0B3A912FF127F081E7B950F>98 D<12011203B3A912FFA2081E80950F>I< 127F12FF12C0B3A91240081E7B950F>I<12FFA21203B3A91201081E80950F>I<12C0B3AB 021D7D950A>106 D<154015C0EC0180A2EC0300A21406A25C5CA25CA25CA200305B12D8 38180180120C49C7FC120613066C5AA2EA0198A2EA00F0A21360A21A1E7F811B>112 D E /Fi 25 115 df<132013401380EA01005A1206A25AA25AA212381230A21270A31260 12E0AD12601270A31230A212381218A27EA27EA27E7EEA0080134013200B317A8113>0 D<7E12407E7E12187EA27EA27EA213801201A213C0A3120013E0AD13C01201A31380A212 031300A21206A25AA25A12105A5A5A0B317F8113>I<1430146014C0EB0180EB03005B13 0E130C5B1338133013705B5B12015B1203A290C7FC5A1206120EA2120C121CA312181238 A45AA75AB3A31270A77EA41218121CA3120C120EA2120612077E7FA212017F12007F1370 1330133813187F130E7F7FEB0180EB00C014601430146377811F>18 D<12C012607E7E7E120E7E7E6C7E7F12007F1370133013381318131CA2130C130E130613 07A27F1480A3130114C0A4EB00E0A71470B3A314E0A7EB01C0A414801303A314005BA213 06130E130C131CA213181338133013705B5B12015B48C7FC5A120E120C5A5A5A5A14637F 811F>III<12E0B3B3B3B3B3A6EAFFF8A30D63768118>I<1338B3B3B3 B3B3A6EAFFF8A30D63808118>III<1470EB01F0EB03C0EB0780EB0E005B5B5BA213 F05BB3AC485AA3485A48C7FC1206120E12385A12C012707E120E120612076C7E6C7EA36C 7EB3AC7F1370A27F7F7FEB0780EB03C0EB01F0EB007014637B811F>I<14181430146014 E014C0EB01801303EB07001306130E130C131C5BA25BA25BA212015BA2485AA3120790C7 FCA25A120EA2121EA3121CA2123CA412381278A8127012F0B3A812701278A81238123CA4 121CA2121EA3120EA2120F7EA27F1203A36C7EA27F1200A21370A27FA27F130C130E1306 1307EB03801301EB00C014E0146014301418157C768121>32 D<12C012607E123812187E 120E7E7E7F12017F6C7EA21370A27FA2133C131CA27FA3130F7FA214801303A214C0A313 01A214E0A4130014F0A814701478B3A8147014F0A814E01301A414C0A21303A31480A213 071400A25B130EA35BA2133C1338A25BA25BA2485A5B120390C7FC5A120E120C5A123812 305A5A157C7F8121>III<140C141814381430146014E014 C01301EB0380A2EB0700A2130EA25BA25BA21378137013F0A25B1201A2485AA4485AA312 0F90C7FCA35AA2121EA3123EA4123CA3127CA81278A212F8B1164B748024>48 D<12C01260127012307E121C120C120E7EA26C7EA26C7EA26C7EA21370A213781338133C A2131C131EA27FA4EB0780A314C01303A314E0A21301A314F0A41300A314F8A81478A214 7CB1164B7F8024>I<12F8B11278A2127CA8123CA3123EA4121EA3121FA27EA37F1207A3 6C7EA46C7EA212007FA2137013781338A27FA27FA27FA2EB0380A2EB01C0130014E01460 143014381418140C164B748224>64 D<147CB11478A214F8A814F0A31301A414E0A31303 A214C0A313071480A3EB0F00A4131EA2131C133CA2133813781370A25BA2485AA2485AA2 48C7FCA2120E120C121C12185A127012605A164B7F8224>I80 D88 D104 DI<16021606160CA21618A21630A21660 A216C0A2ED0180A2ED0300A21506A25DA25DA25DA25D1208001C5C123C00CE495A120E4A C7FC7E1406EA03805CEA01C05C13E000005BA2EB7060A26D5AA2EB1D80A2011FC8FC7F13 0E130627327C812A>112 D<16021606A2160CA41618A41630A41660A416C0A4ED0180A5 ED0300A41506A45DA45DA45DA45DA31208001C5CA2123C125C4A5A128E120EA24AC7FC7E A31406A2EA0380A25CA2EA01C0A25CA3EA00E0A25CA313705CA313385CA4EB1D80A4010F C8FCA4130E1306A227647C812A>114 D E /Fj 8 84 df<1418A21438A21478A214B8EB 0138A2EB023C141C1304130C13081310A21320A2EB7FFCEBC01C1380EA0100141E000213 0EA25A120C001C131EB4EBFFC01A1D7E9C1F>65 D<48B5FC39003C038090383801C0EC00 E0A35B1401A2EC03C001E01380EC0F00141EEBFFFC3801C00E801580A2EA0380A4390700 0F00140E141E5C000E13F0B512C01B1C7E9B1D>I<48B512F038003C00013813301520A3 5BA214081500495AA21430EBFFF03801C020A439038040801400A2EC0100EA07005C1402 1406000E133CB512FC1C1C7E9B1C>69 D<3801FFC038003C001338A45BA45BA4485AA438 038002A31404EA0700140C14181438000E13F0B5FC171C7E9B1A>76 DI<3801FFFE39003C038090383801C0EC00 E0A3EB7001A315C0EBE0031580EC0700141C3801FFF001C0C7FCA3485AA448C8FCA45AEA FFE01B1C7E9B1C>80 D<3801FFFE39003C078090383801C015E01400A2EB7001A3EC03C0 01E01380EC0700141CEBFFE03801C03080141CA2EA0380A43807003C1520A348144039FF E01E80C7EA0F001B1D7E9B1E>82 DI E /Fk 137[20 20 1[20 20 4[20 20 1[20 20 20 2[20 20 20 20 20 32[20 17[20 2[20 43[{TeXBase1Encoding ReEncodeFont}17 33.333332 /Courier rf /Fl 134[17 1[24 17 17 9 13 11 1[17 17 17 26 9 2[9 17 17 1[15 17 15 17 15 7[24 3[24 1[18 22 3[24 30 3[11 1[24 18 20 1[22 8[9 17 1[17 1[17 1[17 4[8 11 45[{ TeXBase1Encoding ReEncodeFont}38 33.333332 /Times-Roman rf /Fm 3 123 df<120CA2EACCC012EDEA7F80EA0C00EA7F80EAEDC012CCEA0C00A20A0B 7D8B10>3 D<1218A512FFA21218AF08167D900E>121 D<1218A512FF1218A512001218A4 12FFA21218A408167D900E>I E /Fn 104[42 2[18 18 24[18 21 21 30 21 21 12 16 14 21 21 21 21 32 12 21 12 12 21 21 14 18 21 18 21 18 3[14 1[14 3[39 30 1[25 23 28 2[30 30 37 25 30 1[14 30 30 23 25 30 28 28 30 1[18 3[12 12 21 21 21 21 21 21 21 21 21 21 1[10 14 10 2[14 14 14 35[23 23 2[{TeXBase1Encoding ReEncodeFont}71 41.666668 /Times-Roman rf /Fo 12 111 df<120212041208121812101230122012601240A212C0AA1240A21260 1220123012101218120812041202071E7D950D>40 D<1280124012201230121012181208 120C1204A21206AA1204A2120C1208121812101230122012401280071E7E950D>I<1360 AAB512F0A238006000AA14167E9119>43 D<120FEA30C0EA6060A2EA4020EAC030A9EA40 20EA6060A2EA30C0EA0F000C137E9211>48 D<120C121C12EC120CAFEAFFC00A137D9211 >I<121FEA60C01360EAF07013301260EA0070A2136013C012011380EA02005AEA081012 10EA2020EA7FE012FF0C137E9211>II<136013E0A2EA 016012021206120C120812101220126012C0EAFFFCEA0060A5EA03FC0E137F9211>I56 D<387FFFE0B512F0C8FCA6B512F06C13E0140A7E 8B19>61 D<12F01230B212FC06147F9309>108 D110 D E /Fp 11 121 df<124012E0124003037D820A>58 D<13201360A213C0A3EA0180A3EA0300A31206A25AA35AA35AA35AA35AA30B1D7E9511> 61 D83 D99 D<1206120712061200A4 1238124CA2128C12981218A212301232A21264A2123808147F930C>105 D<1330133813301300A4EA01C0EA0260EA0430136012081200A213C0A4EA0180A4EA6300 12E312C612780D1A81930E>I<121E12065AA45A1338135C139CEA3118EA36001238EA3F 80EA61C0EA60C8A3EAC0D013600E147F9312>I110 D<1207EA1880EA19C0EA3180EA380012 1E7EEA0380124112E1EAC1001282127C0A0D7E8C10>115 D<1204120CA35AEAFF80EA18 00A25AA45A1261A212621264123809127F910D>I120 D E /Fq 34 122 df<13F8EA030C380E0604EA1C07383803080030138800701390A200E013A0 A214C01480A3EA6007EB0B8838307190380F80E016127E911B>11 D<38078010EA1FC0383FE020EA7FF038603040EAC0183880088012001304EB0500A21306 A31304A3130CA35BA45BA21320141B7F9115>13 D<1338137FEB87803801030090C7FC7F A27F12007FA2137013F8EA03B8EA063CEA0C1C121812381270A212E0A413181338EA6030 EA70606C5AEA0F80111E7F9D12>II<3801803000031370A3380700E0A4380E01C0 A4381C0388A3EA1E07383E1990383BE0E00038C7FCA25AA45AA25A151B7F9119>22 D<380FFFF85A5A386084001241EA81041201EA030CA212021206A2120E120CEA1C0EA212 38EA180615127E9118>25 D<0008130648130EA248130614025A1308131800801304A2EB 300C140800C01318EBF030B512F0387F9FE0EB1FC0383E0F00171280911A>33 D<126012F0A2126004047C830C>58 D<126012F0A212701210A41220A212401280040C7C 830C>II<13 0113031306A3130CA31318A31330A31360A213C0A3EA0180A3EA0300A31206A25AA35AA3 5AA35AA35AA210297E9E15>I<12E01278121EEA0780EA01E0EA0078131EEB0780EB01E0 EB0078141EEC0780A2EC1E001478EB01E0EB0780011EC7FC1378EA01E0EA0780001EC8FC 127812E019187D9520>I<140CA2141CA2143C145CA2149E148EEB010E1302A21304A213 081310A2497EEB3FFFEB40071380A2EA0100A212025AA2001C148039FF803FF01C1D7F9C 1F>65 D79 D<48B5FC39003C03C090383800E015F01570A2 4913F0A315E0EBE001EC03C0EC0700141E3801FFF001C0C7FCA3485AA448C8FCA45AEAFF E01C1C7E9B1B>I83 D<39FFC00FF0391C00038015001402A25C5C121E 000E5B143014205CA25C49C7FC120FEA07025BA25BA25B5BEA03A013C05BA290C8FCA21C 1D7D9B18>86 D<3A01FFC0FF803A001E003C00011C13306D13205D010F5B6D48C7FC1482 EB038414CCEB01D814F05C130080EB0170EB0278EB04381308EB103CEB201CEB401EEB80 0E3801000F00027F1206001E497E39FF803FF0211C7F9B22>88 D99 D101 DI104 DI< 1307130FA213061300A61378139CEA010C1202131C12041200A21338A41370A413E0A4EA 01C01261EAF180EAF30012E6127C1024809B11>III110 D<13F8EA030CEA0E06487E1218123000701380A238E00700A3130EA25BEA60185BEA30E0 EA0F8011127E9114>I<380787803809C8603808D03013E0EA11C014381201A238038070 A31460380700E014C0EB0180EB8300EA0E86137890C7FCA25AA4123CB4FC151A819115> I114 DI<13C01201A3EA0380A4EAFFF0EA 0700A3120EA45AA4EA3820A21340A2EA1880EA0F000C1A80990F>I<380787803808C840 3810F0C03820F1E0EBE3C03840E1803800E000A2485AA43863808012F3EB810012E5EA84 C6EA787813127E9118>120 D<001C13C0EA27011247A238870380A2120EA2381C0700A4 EA180EA3EA1C1EEA0C3CEA07DCEA001C1318EA6038EAF0305B485AEA4180003EC7FC121A 7E9114>I E /Fr 28 127 df2 D<137F3803C1E038070070001C131C003C131E0038130E0078130F00707F00F014 80A50070140000785BA20038130E6C5BA26C5B00061330A20083EB608000811340A23941 80C100007F13FFA3191D7E9C1E>10 D<1380EA0100120212065AA25AA25AA35AA412E0AC 1260A47EA37EA27EA27E12027EEA0080092A7C9E10>40 D<7E12407E12307EA27EA27EA3 7EA41380AC1300A41206A35AA25AA25A12205A5A092A7E9E10>I<1306ADB612E0A2D800 06C7FCAD1B1C7E9720>43 D48 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>III<130CA2131C133CA2135C13DC139CEA011C12 0312021204120C1208121012301220124012C0B512C038001C00A73801FFC0121C7F9B15 >II<13F0EA030CEA0404 EA0C0EEA181E1230130CEA7000A21260EAE3E0EAE430EAE818EAF00C130EEAE0061307A5 1260A2EA7006EA300E130CEA1818EA0C30EA03E0101D7E9B15>I<1240387FFF801400A2 EA4002485AA25B485AA25B1360134013C0A212015BA21203A41207A66CC7FC111D7E9B15 >II<126012F0A212601200AA126012F0A2126004127C910C>58 D<007FB512C0B612E0C9FCA8B612E06C14C01B0C7E8F20>61 D80 D<12FEA212C0B3B312FEA207297C9E0C>91 D<12FEA21206B3B312FEA20729809E0C>93 D<120C12121221EA4080EA80400A057B9B15>I103 D<1218123CA21218C7FCA712FC121CB0EAFF80091D7F9C0C>105 D<12FC121CB3A9EAFF80091D7F9C0C>108 D<39FC7E07E0391C838838391D019018001E EBE01C001C13C0AD3AFF8FF8FF8021127F9124>III114 D126 D E /Fs 19 113 df0 D<126012F0A2126004047C8B0C>I< 13041306ACB612E0A2D80006C7FCABB612E0A21B1C7E9A20>6 D8 D14 D20 D<12C012F0123C120FEA 03C0EA00F0133C130FEB03C0EB00F0143C140FEC0380EC0F00143C14F0EB03C0010FC7FC 133C13F0EA03C0000FC8FC123C127012C0C9FCA7007FB5FCB6128019227D9920>I25 D<153081A381A281811680ED00C0B712F8A2C912C0ED0380160015 065DA25DA35D25167E942A>33 D50 D<1460A214C0A2EB0180A3EB0300A21306A25BA25BA35BA25BA25BA2485AA248C7FCA312 06A25AA25AA25AA35AA25A124013287A9D00>54 D69 D100 DI<133C13E0EA01C013801203AD13005A121C12F0121C12077E1380AD120113C0 EA00E0133C0E297D9E15>I<12F0121C12077E1380AD120113C0EA00E0133C13E0EA01C0 13801203AD13005A121C12F00E297D9E15>I<12C0B3B3A502297B9E0C>106 DI<164016C0ED0180A2ED0300A21506A25D A25DA25DA25DA25DA24A5AA24AC7FC120C003C1306124E008E5B12075CEA03805CA26C6C 5AA26C6C5AA2EB7180A2013BC8FCA2131EA2130CA2222A7E8123>112 D E /Ft 133[16 18 18 28 18 21 12 16 16 21 21 21 21 30 12 18 12 12 21 21 12 18 21 18 21 21 9[35 2[23 21 9[14 2[25 2[28 25 25 6[14 8[21 21 1[10 14 10 2[14 14 37[21 2[{TeXBase1Encoding ReEncodeFont}43 41.666668 /Times-Italic rf /Fu 135[25 2[28 17 19 22 1[28 25 28 41 14 2[14 1[25 17 22 28 22 28 25 14[36 5[33 2[19 39 4[36 1[36 11[25 25 25 25 25 2[12 46[{TeXBase1Encoding ReEncodeFont}30 50.000000 /Times-Bold rf /Fv 3 123 df<1202A3EAC218EAF278EA3AE0EA0F80A2EA 3AE0EAF278EAC218EA0200A30D0E7E8E12>3 D<1206A8EAFFF0A2EA0600B30C1D7E9611> 121 D<1206A6EAFFF0A2EA0600A6C7FC1206A6EAFFF0A2EA0600A60C1D7E9611>I E /Fw 137[25 25 2[17 2[25 25 39 14 2[14 25 25 17 1[25 22 1[22 20[30 1[19 6[33 33 36 65[{TeXBase1Encoding ReEncodeFont}19 50.000000 /Times-Roman rf /Fx 138[33 20 23 27 2[30 33 1[17 2[17 1[30 1[27 1[27 1[30 17[47 1[56 40 5[37 3[40 66[{TeXBase1Encoding ReEncodeFont}17 59.999973 /Times-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 394 187 a Fx(On)15 b(Lear)o(ning)f(Monotone)h(Boolean)f (Functions)383 345 y Fw(A)l(vrim)e(Blum)633 327 y Fv(\003)809 345 y Fw(Carl)g(Burch)1029 327 y Fv(y)1205 345 y Fw(John)g(Langford) 1497 327 y Fv(z)308 557 y Fu(Abstract)-41 657 y Ft(W)l(e)f(consider)h (the)f(pr)n(oblem)g(of)g(learning)f(monotone)g(Boolean)-91 706 y(functions)23 b(over)j Fs(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)288 691 y Fp(n)335 706 y Ft(under)25 b(the)g(uniform)f(distrib)o (ution.)-91 756 y(Speci\002cally)n(,)19 b(given)e(a)h(polynomial)e (number)h(of)g(uniform)f(r)o(an-)-91 806 y(dom)21 b(samples)g(for)h(an) f(unknown)f(monotone)h(Boolean)g(func-)-91 856 y(tion)16 b Fq(f)t Ft(,)k(and)c(given)h(polynomial)e(computing)h(time,)i(we)g (would)-91 906 y(like)f(to)h(appr)n(oximate)f Fq(f)23 b Ft(as)18 b(well)f(as)h(possible)o(.)36 b(W)l(e)19 b(describe)-91 955 y(a)d(simple)g(algorithm)f(that)g(we)i(pr)n(ove)g(ac)o(hie)o(ves)h (err)n(or)g(at)e(most)-91 1005 y Fr(1)p Fq(=)p Fr(2)10 b Fs(\000)h Fr(\012\(1)p Fq(=)113 975 y Fs(p)p 148 975 25 2 v 30 x Fq(n)o Fr(\))p Ft(,)j(impr)n(oving)d(on)i(the)f(pr)n(e)o (vious)i(best)e(bound)g(of)-91 1055 y Fr(1)p Fq(=)p Fr(2)h Fs(\000)h Fr(\012\(\(log)147 1037 y Fo(2)173 1055 y Fq(n)p Fr(\))p Fq(=n)p Fr(\))p Ft(.)32 b(W)l(e)17 b(also)f(pr)n(ove)h(that)f (no)g(algorithm,)-91 1105 y(given)8 b(a)h(polynomial)d(number)j(of)f (samples,)h(can)g(guar)o(antee)f(err)n(or)-91 1155 y Fr(1)p Fq(=)p Fr(2)t Fs(\000)t Fq(!)q Fr(\(\(log)f Fq(n)p Fr(\))p Fq(=)194 1125 y Fs(p)p 228 1125 V 228 1155 a Fq(n)p Fr(\))p Ft(,)j(impr)n(oving)d(on)i(the)g(pr)n(e)o(vious)h(best)e (har)n(d-)-91 1205 y(ness)16 b(bound)f(of)g Fq(O)q Fr(\(1)p Fq(=)255 1175 y Fs(p)p 289 1175 V 289 1205 a Fq(n)p Fr(\))p Ft(.)29 b(These)17 b(lower)e(bounds)g(hold)g(e)o(ven)-91 1254 y(if)g(the)h(learning)e(algorithm)g(is)i(allowed)e(membership)i (queries.)-91 1304 y(Thus)9 b(this)g(paper)g(settles)g(to)g(an)g Fq(O)q Fr(\(log)e Fq(n)p Fr(\))j Ft(factor)e(the)i(question)e(of)-91 1354 y(the)h(best)g(ac)o(hie)o(vable)h(err)n(or)g(for)f(learning)f(the) h(class)g(of)f(monotone)-91 1404 y(Boolean)i(functions)e(with)h(r)n (espect)j(to)d(the)i(uniform)d(distrib)o(ution.)-91 1571 y Fu(1.)13 b(Intr)o(oduction)-41 1679 y Fn(A)8 b Ft(monotone)f(Boolean) h(function)e Fq(f)13 b Fn(maps)c(bit)e(v)o(ectors)i Fs(f)p Fr(0)p Fq(;)e Fr(1)p Fs(g)872 1664 y Fp(n)-91 1729 y Fn(to)12 b Fs(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)p Fn(,)12 b(such)g(that)g(if)g Fq(f)t Fr(\()p Fq(x)p Fr(\))k(=)g(1)p Fn(,)d(then)f(\003ipping)f(an)o(y)i(bit)e(of)h Fq(x)-91 1779 y Fn(from)j Fr(0)h Fn(to)f Fr(1)h Fn(keeps)g Fq(f)t Fr(\()p Fq(x)p Fr(\))22 b(=)g(1)p Fn(.)30 b(\(This)15 b(is)h(sometimes)g(called)-91 1829 y(a)d Ft(positive)f(Boolean)h (function)p Fn(,)f(or)n(,)i(in)e(combinatorics,)i(a)f Ft(mono-)-91 1879 y(tone)h(incr)n(easing)g(set)h(system)p Fn(.\))27 b(Because)16 b(monotone)e(functions)-91 1928 y(encompass)19 b(a)g(v)o(ery)f(broad)g(class)h(of)f(Boolean)g(e)o (xpressions\227)-91 1978 y(speci\002cally)11 b(all)g(circuits)f (including)f(no)i(ne)o(gations\227algorithms)-91 2028 y(to)e(learn)i(them)f(are)h(of)f(special)h(interest.)-41 2078 y(F)o(or)20 b(a)g(particular)f(Boolean)h(tar)o(get)g(concept)g Fq(f)25 b Fn(and)20 b(a)g(hy-)-91 2128 y(pothesis)14 b(function)f Fq(h)p Fn(,)k(we)e(de\002ne)h(the)e Ft(err)n(or)j Fn(of)e Fq(h)g Fn(as)g(the)g(frac-)-91 2178 y(tion)e(of)i(points)f Fq(x)g Fn(where)i Fq(h)p Fr(\()p Fq(x)p Fr(\))k Fs(6)p Fr(=)h Fq(f)t Fr(\()p Fq(x)p Fr(\))p Fn(;)c(that)e(is,)h(the)f(error)f (is)-91 2228 y Fr(Pr)7 b([)p Fq(h)p Fr(\()p Fq(x)p Fr(\))k Fs(6)p Fr(=)h Fq(f)t Fr(\()p Fq(x)p Fr(\))q(])h Fn(for)g(bit)g(v)o (ectors)h Fq(x)g Fn(chosen)g(uniformly)d(from)-91 2277 y Fs(f)p Fr(0)p Fq(;)c Fr(1)p Fs(g)12 2262 y Fp(n)33 2277 y Fn(.)28 b(\(All)14 b(probabilities)f(in)i(this)f(paper)h(are)h (o)o(v)o(er)g(the)f(uni-)-91 2327 y(form)d(distrib)o(ution.\))18 b(Because)c(of)f(the)g(generality)f(of)g(monotone)-91 2377 y(functions,)d(this)h(paper)h(usually)e(discusses)j(errors)e(of)g (nearly)h Fr(1)p Fq(=)p Fr(2)p Fn(.)-91 2427 y(T)m(o)k(simplify)f (discussion,)i(we)f(sometimes)h(use)g(the)f(closely)g(re-)p -91 2464 394 2 v -49 2490 a Fm(\003)-31 2502 y Fl(Carnegie)7 b(Mellon)h(Uni)o(versity)n(.)k(E-mail:)g Fk(avrim+@cs.cmu.edu)p Fl(.)f(Sup-)-91 2541 y(ported)c(in)h(part)g(by)g(NSF)h(National)e(Y)l (oung)g(In)o(vestigator)f(grant)i(CCR-9357793.)-48 2570 y Fm(y)-31 2582 y Fl(Carnegie)15 b(Mellon)h(Uni)o(versity)n(.)35 b(E-mail:)28 b Fk(cburch+@cs.cmu.edu)p Fl(.)-91 2622 y(Supported)7 b(in)h(part)g(by)f(a)h(National)g(Science)g(Foundation)e (Graduate)h(Fello)o(wship.)-48 2651 y Fm(z)-31 2662 y Fl(Carnegie)f(Mellon)i(Uni)o(versity)n(.)h(E-mail:)i Fk(jcl+@cs.cmu.edu)p Fl(.)987 557 y Fn(lated)f(concept)h(of)f Ft(corr)n(elation)p Fn(,)g(which)g(for)g(error)g Fq(\015)k Fn(is)c(de\002ned)h(as)987 606 y Fr(1)e Fs(\000)g Fr(2)p Fq(\015)r Fn(.)1037 661 y(The)18 b(algorithms)e(we)i(discuss)f(are)i (for)e(learning)f(monotone)987 711 y(functions)21 b(with)h(respect)h (to)f(the)g(uniform)g(distrib)o(ution)o(.)48 b(In)987 760 y(other)16 b(words,)i(the)f(algorithm)f(has)h(access)i(to)e(an)g Ft(e)o(xample)g(or)o(-)987 810 y(acle)i Fj(SAMPLE)25 b Fn(for)18 b(a)i(hidden)e(monotone)g(function)g Fq(f)t Fn(,)k(that)987 860 y(when)16 b(in)n(v)o(oked)g(produces)g(a)h(pair)f Fr(\()p Fq(x;)7 b(f)t Fr(\()p Fq(x)p Fr(\)\))17 b Fn(where)g Fq(x)f Fn(is)h(cho-)987 910 y(sen)g(uniformly)e(at)j(random)e(from)h Fs(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)1634 895 y Fp(n)1655 910 y Fn(.)34 b(The)17 b(goal)g(of)g(the)987 960 y(learning)d (algorithm)f(is)h(to)g(produce)g(a)i(good)d(approximation)g(to)987 1010 y Fq(f)20 b Fn(\(a)c(hypothesis)d(with)h(lo)o(w)h(error)g(o)o(v)o (er)g(the)g(uniform)f(distrib)o(u-)987 1059 y(tion\))g(using)g (polynomial)g(time)h(and)h(a)g(polynomial)d(number)j(of)987 1109 y(samples.)37 b(Achie)o(ving)16 b(error)i Fr(1)p Fq(=)p Fr(2)f Fn(is)h(tri)o(vial;)h(achie)o(ving)f(error)987 1159 y Fr(1)p Fq(=)p Fr(2)10 b Fs(\000)h Fr(1)p Fq(=pol)q(y)q Fr(\()p Fq(n)p Fr(\))i Fn(is)f(called)g(\223weak)h(learning\224;)g(and) f(achie)o(ving)987 1209 y(arbitrarily)h(lo)o(w)h(error)g Fq(\017)g Fn(in)g(time)h(polynomial)e(in)h Fr(1)p Fq(=\017)g Fn(is)g(called)987 1259 y(\223strong)c(learning\224.)15 b(A)c(more)h(po)o(werful)d(oracle)j(than)f Fj(SAMPLE)987 1308 y Fn(is)g(the)g Ft(membership)g(query)h(or)o(acle)g Fj(MEMBER)i Fn(that)d(allo)o(ws)g(the)987 1358 y(algorithm)16 b(to)i(query)f Fq(f)23 b Fn(at)18 b(arbitrary)f(points)g(of)h(its)f (choosing.)987 1408 y(Our)10 b(upper)g(bounds)g(\(algorithms\))e(use)j (only)f Fj(SAMPLE)16 b Fn(b)o(ut)10 b(our)987 1458 y(lo)o(wer)i(bounds) g(\(hardness)h(results\))e(hold)h(e)o(v)o(en)h(if)f(the)h(algorithm)987 1508 y(has)e(access)h(to)e Fj(MEMBER)j Fn(as)e(well.)1037 1562 y(One)g(reason)g(the)g(problem)f(of)h(learning)f(monotone)g (functions)987 1612 y(from)h(random)h(e)o(xamples)h(is)e(interesting)f (is)i(that)f(for)g(se)o(v)o(eral)i(im-)987 1662 y(portant)8 b(subclasses)h(of)g(monotone)f(functions,)g(the)h(upper)f(bounds)987 1711 y(for)17 b(the)g(general)h(class)h(of)e(monotone)g(functions)f (are)i(the)f(best)987 1761 y(kno)o(wn.)27 b(The)16 b(most)f(prominent)f (such)i(subclass,)h(to)e(which)g(the)987 1811 y(algorithm)e(of)h(this)f (paper)i(is)f(an)g(impro)o(v)o(ement,)i(is)e(the)h(class)g(of)987 1861 y(monotone)g(DNF)g(formulas.)29 b(\(Some)16 b(restricted)f (subclasses)i(of)987 1911 y(monotone)f(DNF)m(,)i(such)f(as)h Fq(\026)p Fn(DNF)m(,)g(where)g(each)g(v)o(ariable)f(ap-)987 1961 y(pears)12 b(at)f(most)f(once,)i(ha)o(v)o(e)g(kno)o(wn)e (strong-learning)f(algorithms)987 2010 y([6,)16 b(7].\))29 b(The)16 b(study)f(of)h(learning)e(monotone)h(functions)g(under)987 2060 y(the)9 b(uniform)f(distrib)o(ution)e(is)j(also)g(inspired)g(by)f (the)i(fact)f(that)f(the)o(y)987 2110 y(stand)j(at)h(the)f(threshold)f (of)h(what)h(is)f(weakly)g(learnable.)17 b(K)o(earns,)987 2160 y(Li,)e(and)g(V)-5 b(aliant)14 b(observ)o(e)g(on)g(proposing)e (the)i(problem:)20 b(\223Gen-)987 2210 y(eralization)e(in)f(an)o(y)i (direction\227unifor)o(m)d(distrib)o(utions)f(to)j(ar)o(-)987 2259 y(bitrary)d(distrib)o(ution)o(s,)g(weak)i(learning)e(to)h(strong)f (learning,)i(or)987 2309 y(monotone)g(functions)f(to)h(arbitrary)f (functions\227results)f(in)i(in-)987 2359 y(tractability\224)9 b([6)o(].)1037 2413 y(The)h(\002rst)f(results)g(on)g(learning)f (monotone)h(functions)f(o)o(v)o(er)i(the)987 2463 y(uniform)i(distrib)o (ution)e(were)k(by)e(K)o(earns)i(et)f(al)h([6)o(].)22 b(Their)13 b(algo-)987 2513 y(rithm)i(be)o(gins)g(by)g(dra)o(wing)h(a)g (sample)g(of)f(data)h(and)g(producing)987 2563 y(the)d(constant-one)f (function)g(\()p Fq(h)p Fr(\()p Fq(x)p Fr(\))17 b(=)g(1)p Fn(\))c(or)g(the)g(constant-zero)987 2613 y(function)i(\()p Fq(h)p Fr(\()p Fq(x)p Fr(\))23 b(=)g(0)p Fn(\))16 b(if)g(the)g(number)h (of)f(positi)o(v)o(e)f(e)o(xamples)987 2662 y(seen)9 b(dif)o(fers)f(signi\002cantly)e(from)i(the)g(number)h(of)f(ne)o(gati)o (v)o(es)g(seen.)p eop %%Page: 2 2 2 1 bop -91 42 a Fn(Otherwise,)10 b(their)f(algorithm)f(outputs)g(the)i (single-v)o(ariable)f(func-)-91 91 y(tion)g(\()p Fq(f)t Fr(\()p Fq(x)p Fr(\))k(=)g Fq(x)160 97 y Fp(i)174 91 y Fn(\))d(that)h(has)g(highest)f(observ)o(ed)h(correlation)e(with)-91 141 y(the)15 b(data.)28 b(By)15 b(results)f(of)h(Aldous)f([1])h(there)g (must)g(e)o(xist)h(some)-91 191 y(v)o(ariable)h(with)g(correlation)g Fr(\012\(1)p Fq(=n)p Fr(\))p Fn(,)j(and)e(thus)f(their)g(error)g(is)-91 241 y Fr(1)p Fq(=)p Fr(2)12 b Fs(\000)i Fr(\012\(1)p Fq(=n)p Fr(\))p Fn(.)29 b(Bshouty)15 b(and)g(T)m(amon)i([4)o(])f(impro) o(v)o(e)g(on)f(this)-91 291 y(guarantee)9 b(using)g(results)f(of)h (Kahn,)h(Kalai,)g(and)f(Linial)f([5].)k(The)o(y)-91 340 y(demonstrate)19 b(an)g(algorithm)e(which)i(outputs)e(linear)o (-threshold)-91 390 y(functions)7 b(and)h(guarantees)g(error)g(at)g (most)g Fr(1)p Fq(=)p Fr(2)q Fs(\000)q Fr(\012\(\(log)754 372 y Fo(2)780 390 y Fq(n)p Fr(\))p Fq(=n)p Fr(\))p Fn(.)-91 440 y(Bshouty)16 b(and)h(T)m(amon)h(also)f(describe)h(super)o (-polynomial-ti)o(me)-91 490 y(algorithms)9 b(with)g(better)h (guarantees.)-41 550 y(In)k(this)f(paper)i(we)g(present)f(an)h (algorithm)d(that)i(achie)o(v)o(es)i(er)o(-)-91 600 y(ror)f(at)g(most)g Fr(1)p Fq(=)p Fr(2)d Fs(\000)i Fr(\012\(1)p Fq(=)323 570 y Fs(p)p 357 570 25 2 v 357 600 a Fq(n)p Fr(\))p Fn(.)28 b(The)16 b(approach)g(is)f(especially)-91 650 y(simple.)42 b(In)19 b(brief,)j(we)f(pro)o(v)o(e)f(that)f(one)h(of)g (three)g(functions)-91 700 y(achie)o(v)o(es)g(this)f(correlation:)29 b(the)19 b(constant-one)f(function,)i(the)-91 749 y(constant-zero)11 b(function,)g(or)h(the)g(majority)e(function)h(\()p Fq(h)p Fr(\()p Fq(x)p Fr(\))j(=)g(1)-91 799 y Fn(if)o(f)-42 768 y Fi(P)2 812 y Fp(i)23 799 y Fq(x)47 805 y Fp(i)74 799 y Fq(>)f(n=)p Fr(2)p Fn(\).)i(By)c(sampling)g(enough)f(times)i(to)e (determine)-91 849 y(which)j(of)g(these)i(three)e(is)h (best-correlated,)g(we)h(achie)o(v)o(e)g(the)e(re-)-91 899 y(sult.)-41 959 y(W)m(e)k(complement)f(this)g(result)g(with)f(a)i (lo)o(wer)f(bound)g(sho)o(w-)-91 1009 y(ing)f(that)g(this)f(simple)i (algorithm)e(is)h(nearly)h(the)f(best)h(possible.)-91 1059 y(Speci\002cally)m(,)h(no)d(algorithm,)h(gi)o(v)o(en)g(only)f(a)h (polynomial)f(num-)-91 1109 y(ber)g(of)g(accesses)j(to)d(the)g(tar)o (get)g(function,)h(can)g(guarantee)g(error)-91 1158 y Fr(1)p Fq(=)p Fr(2)t Fs(\000)t Fq(!)q Fr(\(\(log)7 b Fq(n)p Fr(\))p Fq(=)194 1129 y Fs(p)p 228 1129 V 228 1158 a Fq(n)p Fr(\))p Fn(,)j(e)o(v)o(en)g(if)e(it)g(can)i(use)f(both)f (the)g Fj(SAMPLE)-91 1208 y Fn(and)k Fj(MEMBER)j Fn(oracles.)k(The)12 b(best)g(pre)o(vious)f(ne)o(gati)o(v)o(e)i(result,)-91 1258 y(using)7 b(\223slice\224)j(functions,)e(is)h(that)f(no)g(sube)o (xponential-time)f(algo-)-91 1308 y(rithm)i(can)i(guarantee)g(error)f Fq(O)q Fr(\(1)p Fq(=)431 1278 y Fs(p)p 465 1278 V 465 1308 a Fq(n)p Fr(\))g Fn([6].)-41 1368 y(In)f(this)f(paper)n(,)i Fs(k)p Fq(x)p Fs(k)f Fn(represents)h(the)f(number)g(of)g Fr(1)g Fn(bits)f(in)h Fq(x)p Fn(;)g(in)-91 1418 y(other)h(words,)h Fs(k)p Fq(x)p Fs(k)i Fr(=)252 1387 y Fi(P)296 1431 y Fp(i)317 1418 y Fq(x)341 1424 y Fp(i)354 1418 y Fn(.)j(W)m(e)c(use)f Fq(X)546 1424 y Fp(k)578 1418 y Fn(to)g(represent)g(the)g(set)-91 1468 y(of)f(size-)p Fq(k)h Fn(bit)f(v)o(ectors:)i Fq(X)297 1474 y Fp(k)330 1468 y Fr(=)f Fs(f)p Fq(x)g Fs(j)h(k)o Fq(x)p Fs(k)f Fr(=)h Fq(k)q Fs(g)p Fn(.)-91 1616 y Fu(2.)h(Lear)o(ning) f(a)g(fair)g(monotone)g(function)-41 1755 y Fn(A)j Ft(fair)g(Boolean)g (function)f Fn(is)h(a)h(Boolean)f(function)f(that)h(la-)-91 1805 y(bels)k(e)o(xactly)h(half)f(the)g(points)f(with)g Fr(1)p Fn(;)23 b(that)c(is,)j Fq(f)i Fn(is)19 b(fair)g(if)-91 1855 y Fr(Pr)7 b([)p Fq(f)t Fr(\()p Fq(x)p Fr(\))12 b(=)g(1])17 b(=)h(1)p Fq(=)p Fr(2)p Fn(.)k(In)13 b(Section)h(3)f(\(Lemma)i(7\),)g (we)f(pro)o(v)o(e)-91 1905 y(that)g(a)i(learning)e(algorithm)g(for)h (fair)f(monotone)h(functions)f(im-)-91 1955 y(plies)f(a)i(learning)e (algorithm)g(for)g(general)h(monotone)g(functions)-91 2004 y(with)f(only)f(a)j(small)f(loss)f(in)h(error;)g(thus,)h(it)e(suf) o(\002ces)i(to)e(assume)-91 2054 y(that)e(the)h(tar)o(get)f(function)g (is)g(fair)n(.)17 b(In)12 b(this)f(section)g(we)h(sho)o(w)g(that)-91 2104 y(an)e(especially)g(simple)g(algorithm\227namely)m(,)f(the)h (algorithm)f(that)-91 2154 y(blindly)14 b(returns)i(the)h(majority)e (function)g(o)o(v)o(er)j(all)e(v)o(ariables\227)-91 2204 y(learns)h(fair)f(monotone)f(functions)h(with)f(error)i(at)f(most)h Fr(1)p Fq(=)p Fr(2)c Fs(\000)-91 2253 y Fr(\012\(1)p Fq(=)-3 2224 y Fs(p)p 31 2224 V 31 2253 a Fq(n)p Fr(\))p Fn(.)i(That)d(is,)f(we)g(sho)o(w)g(that)f(the)h(majority)f(function)f (cor)o(-)-91 2303 y(relates)i(weakly)f(with)f(e)o(v)o(ery)i(fair)e (monotone)h(function.)-41 2364 y(The)i(intuition)d(moti)o(v)o(ating)g (this)i(proposition)e(is)j(that)f(the)g(best)-91 2413 y(fair)18 b(monotone)g(function)g(for)g(foiling)f(the)i(majority)f (function)-91 2463 y(would)7 b(be)i(the)g(most)g(lopsided)f(function)f (imaginable,)i(the)g(single-)-91 2513 y(v)o(ariable)14 b(function)f Fq(f)t Fr(\()p Fq(x)p Fr(\))21 b(=)e Fq(x)385 2519 y Fo(1)404 2513 y Fn(.)26 b(\(Surprisingly)m(,)14 b(the)g(con)n(v)o(erse)-91 2563 y(is)j(not)f(true:)25 b(Ben-Or)17 b(and)g(Linial)f(demonstrate)h(that)g(the)g(ma-)-91 2613 y(jority)10 b(function)h(does)h(not)g(minimize)g(correlation)f (with)g(the)h(best)-91 2663 y(single-v)o(ariable)g(function)h([2)o (].\))24 b(The)14 b(single-v)o(ariable)f(function)987 42 y(disagrees)e(with)e(the)h(majority)f(function)g(on)h(a)1099 139 y Fr(1)p 1099 158 21 2 v 1099 196 a(2)1133 167 y Fs(\000)1180 139 y Fr(1)p 1180 158 V 1180 196 a(2)1215 167 y Fs(\001)1241 96 y Fi(\000)1289 111 y Fp(n)p Fh(\000)p Fo(1)1260 144 y(\()p Fp(n)p Fh(\000)p Fo(1\))p Fp(=)p Fo(2)1382 96 y Fi(\001)p 1241 158 161 2 v 1299 196 a Fr(2)1320 184 y Fp(n)1418 167 y Fs(\031)1467 139 y Fr(1)p 1467 158 21 2 v 1467 196 a(2)1502 167 y Fs(\000)1590 139 y Fr(1)p 1548 158 106 2 v 1548 166 a Fs(p)p 1583 166 71 2 v 35 x Fr(2)p Fq(\031)q(n)1670 167 y Fs(\031)1719 139 y Fr(1)p 1719 158 21 2 v 1719 196 a(2)1754 167 y Fs(\000)1803 139 y Fr(0)p Fq(:)p Fr(4)p 1800 158 60 2 v 1800 166 a Fs(p)p 1835 166 25 2 v 30 x Fq(n)987 276 y Fn(fraction)17 b(of)i(the)f(points.)36 b(Although)16 b(we)j(belie)o(v)o(e)f(that)g(this)g(is)987 326 y(the)12 b(true)f(worst-case)h(error)g(of)f(the)h(majority)e(function,)h(what)h (we)987 376 y(pro)o(v)o(e)f(is)f(a)g(slightly)e(worse)i(approximation)f (guarantee.)987 464 y Fg(Theor)o(em)i(1)20 b Ft(Say)14 b Fq(f)22 b Fr(:)17 b Fs(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)1447 449 y Fp(n)1485 464 y Fs(!)17 b(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)12 b Ft(is)h(a)g(fair)g(monotone)987 513 y(function.)e(Then)g(the) f(majority)f(function)1231 624 y Fq(h)p Fr(\()p Fq(x)p Fr(\))j(=)1367 566 y Fi(\032)1418 599 y Fr(1)42 b Ft(if)9 b Fs(k)p Fq(x)p Fs(k)i Fq(>)h(n=)p Fr(2)1418 649 y(0)42 b Ft(otherwise)987 739 y(has)10 b(err)n(or)h(at)f(most)g Fr(1)p Fq(=)p Fr(2)e Fs(\000)i Fr(0)p Fq(:)p Fr(1)p Fq(=)1471 709 y Fs(p)p 1504 709 V 1504 739 a Fq(n)p Ft(.)1037 827 y Fn(W)m(e)15 b(assume)g(for)f(simplicity)f(in)h(this)f(section)h(that) g Fq(n)g Fn(is)g(odd;)987 876 y(this)9 b(assumption)h(is)g(remo)o(v)o (ed)h(in)f(Section)g(3)g(\(Lemma)i(6\).)1037 926 y(T)m(o)20 b(pro)o(v)o(e)g(the)g(theorem,)i(we)f(analyze)f(the)g(quantities)f Fq(p)1941 932 y Fp(k)1961 926 y Fn(,)987 976 y(which)11 b(we)i(de\002ne)f(as)h(the)f(fraction)f(of)g(the)h(points)f Fq(x)j Fs(2)g Fq(X)1862 982 y Fp(k)1895 976 y Fn(such)987 1026 y(that)c Fq(f)t Fr(\()p Fq(x)p Fr(\))i(=)g(1)p Fn(:)1191 1114 y Fq(p)1212 1120 y Fp(k)1274 1114 y Fr(=)42 b(Pr)7 b([)p Fq(f)t Fr(\()p Fq(x)p Fr(\))12 b(=)g(1)i Fs(j)6 b Fq(x)11 b Fs(2)h Fq(X)1709 1120 y Fp(k)1734 1114 y Fr(])1274 1200 y(=)1353 1172 y Fs(jf)p Fq(x)f Fs(2)g Fq(X)1494 1178 y Fp(k)1528 1172 y Fs(j)c Fq(f)t Fr(\()p Fq(x)p Fr(\))12 b(=)g(1)5 b Fs(gj)p 1353 1190 389 2 v 1518 1197 a Fi(\000)1537 1212 y Fp(n)1538 1245 y(k)1557 1197 y Fi(\001)1755 1200 y Fq(:)987 1318 y Fn(\(Recall)11 b(that)f(we)i(de\002ned)f Fq(X)1418 1324 y Fp(k)1450 1318 y Fn(as)g Fs(f)p Fq(x)j Fs(j)6 b(k)p Fq(x)p Fs(k)11 b Fr(=)h Fq(k)6 b Fs(g)p Fn(,)11 b(the)g(set)g(of)f(bit)987 1368 y(v)o(ectors)h(with)e(e)o(xactly)h Fq(k)i Fn(ones.\))1037 1418 y(It)h(is)h(easy)h(to)e(see)j(that)d(the)h Fq(p)1482 1424 y Fp(k)1516 1418 y Fn(are)h(non-decreasing)f(with)f Fq(k)q Fn(:)987 1468 y(Imagine)c(placing)g(1')n(s)g(at)h(random)f(into) f(an)i(e)o(xample)g(that)f(initially)987 1517 y(is)15 b(all)f(0')n(s;)j(the)e(probability)d(that)j(the)g(e)o(xample)h(is)f (positi)o(v)o(e)f(can)987 1567 y(only)e(increase)j(as)f(more)f(1')n(s)g (are)i(added.)22 b(The)14 b(Kruskal-Katona)987 1617 y(Theorem)c(\(page) g(39,)f([3]\))g(implies)f(that)h(in)g(fact)g(these)g Fq(p)1812 1623 y Fp(k)1842 1617 y Fn(must)g(be)987 1667 y(increasing)h(at)g(a)h(reasonable)g(rate.)987 1754 y Fg(Lemma)e(2)h(\(Cor)o(ollary)g(to)g(Kruskal-Katona)g([3)o(]\))21 b Ft(F)l(or)103 b(a)987 1804 y(monotone)9 b(incr)n(easing)h(function)f Fq(f)15 b Ft(and)10 b(for)f Fr(0)j Fs(\024)g Fq(i)g(<)f(j)k Fs(\024)c Fq(n)p Ft(,)g(we)987 1854 y(have)g Fq(p)1097 1839 y Fp(i)1097 1865 y(i)1122 1854 y Fs(\024)h Fq(p)1187 1834 y Fp(j)1187 1866 y(j)1204 1854 y Ft(.)1037 1942 y Fn(W)m(e)17 b(break)h(the)f(proof)f(of)h(Theorem)h(1)f(into)f(three)h (lemmas.)987 1992 y(These)f(lemmas,)h(pro)o(v)o(en)e(belo)o(w)m(,)g(e)o (xamine)h Fq(p)1684 1998 y Fp(s)1716 1992 y Fn(for)e(a)h(particular)987 2041 y Fq(s)p Fn(.)e(De\002ne)d Fq(s)g Fn(as)g(the)f(smallest)g(number) g(so)g(that)g(at)g(least)g Fr(1)p Fq(=)p Fr(4)g Fn(of)g(the)987 2091 y(points)f(ha)o(v)o(e)i(size)g(at)f(most)h Fq(s)p Fn(;)f(that)g(is,)h Fq(s)f Fn(is)h(the)f(minimum)f(number)987 2141 y(so)i(that)1107 2110 y Fi(P)1151 2120 y Fp(s)1151 2153 y(j)r Fo(=0)1217 2107 y Fi(\000)1236 2123 y Fp(n)1239 2155 y(j)1257 2107 y Fi(\001)1287 2141 y Fs(\025)i Fr(\(1)p Fq(=)p Fr(4\)2)1447 2126 y Fp(n)1469 2141 y Fn(.)987 2227 y Fg(Lemma)d(3)21 b Ft(If)10 b Fq(p)1232 2233 y Fp(s)1261 2227 y Fs(\024)i Fr(1)p Fq(=)p Fr(4)p Ft(,)e(then)f(Theor)n (em)j(1)e(is)g(true)o(.)987 2314 y Fg(Lemma)f(4)21 b Ft(If)8 b Fq(p)1230 2320 y Fp(s)1259 2314 y Fq(>)k Fr(1)p Fq(=)p Fr(4)p Ft(,)d(then)g(we)g(have)g Fq(p)1629 2320 y Fp(n)p Fh(\000)p Fp(s)1705 2314 y Fs(\025)i Fq(p)1769 2320 y Fp(s)1791 2314 y Fr(+)t(0)p Fq(:)p Fr(4)p Fq(=)1902 2284 y Fs(p)p 1936 2284 25 2 v 1936 2314 a Fq(n)p Ft(.)987 2402 y Fg(Lemma)e(5)21 b Ft(If)9 b Fq(p)1231 2408 y Fp(n)p Fh(\000)p Fp(s)1307 2402 y Fs(\025)i Fq(p)1371 2408 y Fp(s)1396 2402 y Fr(+)d(0)p Fq(:)p Fr(4)p Fq(=)1511 2372 y Fs(p)p 1544 2372 V 1544 2402 a Fq(n)p Ft(,)i(then)g(Theor)n(em)h(1)e (is)h(true)o(.)987 2490 y Fg(Pr)o(oof)k(of)g(Theor)o(em)g(1.)47 b Fn(The)15 b(abo)o(v)o(e)g(three)f(lemmas)h(immedi-)987 2539 y(ately)10 b(imply)f(the)h(theorem.)p 1953 2534 19 19 v 987 2613 a Fg(Pr)o(oof)g(of)g(Lemma)f(3.)25 b Fn(Let)11 b Fq(\013)e Fn(denote)h(the)g(fraction)f(of)g(the)h(points) 987 2663 y Fq(x)15 b Fn(with)g Fs(k)p Fq(x)p Fs(k)21 b(\024)g Fq(s)c Fn(for)e(which)g Fq(f)t Fr(\()p Fq(x)p Fr(\))22 b(=)g(1)p Fn(.)29 b(Since)16 b(the)g Fq(p)1885 2669 y Fp(k)1921 2663 y Fn(are)p eop %%Page: 3 3 3 2 bop -91 42 a Fn(increasing)11 b(and)g Fq(p)183 48 y Fp(s)213 42 y Fs(\024)j Fr(1)p Fq(=)p Fr(4)p Fn(,)d(we)g(kno)o(w)g (that)f Fq(\013)j Fs(\024)g Fr(1)p Fq(=)p Fr(4)p Fn(.)i(Also,)d(by)-91 91 y(de\002nition)e(of)h Fq(s)p Fn(,)i(we)f(ha)o(v)o(e)h(that)d(at)i (most)g(an)f Fq(\013=)p Fr(4)g Fn(fraction)g(of)g(the)-91 141 y(points)e Fq(x)i Fs(2)g(f)p Fr(0)p Fq(;)c Fr(1)p Fs(g)198 126 y Fp(n)230 141 y Fn(satisfy)i(both)h Fs(k)o Fq(x)p Fs(k)h(\024)h Fq(s)f Fn(and)f Fq(f)t Fr(\()p Fq(x)p Fr(\))j(=)e(1)p Fn(.)-41 191 y(Because)j Fq(f)k Fn(is)12 b(fair)n(,)i(this)e(means)i(that)e(a)h Fr(1)p Fq(=)p Fr(2)e Fs(\000)g Fq(\013=)p Fr(4)h Fn(fraction)-91 241 y(of)i(the)h(points)e Fq(x)20 b Fs(2)g(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)335 226 y Fp(n)371 241 y Fn(ha)o(v)o(e)15 b Fq(f)t Fr(\()p Fq(x)p Fr(\))21 b(=)f(1)15 b Fn(and)g Fs(k)p Fq(x)p Fs(k)k Fq(>)h(s)p Fn(.)-91 291 y(So)11 b Fr(\(1)p Fq(=)p Fr(2)e Fs(\000)h Fq(\013=)p Fr(4\))p Fq(=)p Fr(\(3)p Fq(=)p Fr(4\))i(=)h(\(2)d Fs(\000)g Fq(\013)p Fr(\))p Fq(=)p Fr(3)h Fn(of)f(the)h(points)f Fq(x)h Fn(where)-91 340 y Fs(k)p Fq(x)p Fs(k)g Fq(>)g(s)f Fn(must)g(ha)o(v)o(e)g Fq(f)t Fr(\()p Fq(x)p Fr(\))i(=)g(1)p Fn(.)h(Because)e(the)e Fq(p)644 346 y Fp(k)674 340 y Fn(increase)h(with)-91 390 y Fq(k)q Fn(,)k(the)g(proportion)d(of)i(points)f Fq(x)h Fn(with)f Fq(f)t Fr(\()p Fq(x)p Fr(\))19 b(=)e(1)d Fn(is)f(less)h(in)e(the)-91 440 y(range)e Fq(s)i(<)g Fs(k)o Fq(x)p Fs(k)f Fq(<)h(n=)p Fr(2)d Fn(than)h(in)f(the)g(range)h Fq(n=)p Fr(2)h Fs(\024)h(k)p Fq(x)p Fs(k)f(\024)h Fq(n)p Fn(.)h(In)-91 490 y(the)f(range)h Fq(s)i(<)h Fs(k)p Fq(x)p Fs(k)e Fq(<)i(n=)p Fr(2)p Fn(,)d(then,)g(where)f Fq(h)p Fr(\()p Fq(x)p Fr(\))k(=)f(0)p Fn(,)e Fq(f)t Fr(\()p Fq(x)p Fr(\))g Fn(is)-91 540 y(also)d Fr(0)g Fn(for)f(at)h(least)g Fr(1)e Fs(\000)h Fr(\(2)f Fs(\000)g Fq(\013)p Fr(\))p Fq(=)p Fr(3)j(=)h(\(1)c(+)g Fq(\013)p Fr(\))p Fq(=)p Fr(3)i Fn(of)f(the)h(points.)-91 589 y(In)g(the)g(range)h Fq(n=)p Fr(2)g Fs(\024)h(k)p Fq(x)p Fs(k)f(\024)h Fq(n)p Fn(,)f(where)g Fq(h)p Fr(\()p Fq(x)p Fr(\))h(=)g(1)p Fn(,)f Fq(f)t Fr(\()p Fq(x)p Fr(\))g Fn(is)f(also)-91 639 y Fr(1)g Fn(for)g(at)g(least)h Fr(\(2)e Fs(\000)g Fq(\013)p Fr(\))p Fq(=)p Fr(3)h Fn(of)g(the)g(points.)-41 689 y(The)g(total)f(fraction)g(of)g(points)g(where)h Fq(f)t Fr(\()p Fq(x)p Fr(\))h Fn(agrees)g(with)d Fq(h)p Fr(\()p Fq(x)p Fr(\))-91 739 y Fn(is)i(at)g(least)-45 815 y Fr(1)p -45 833 21 2 v -45 871 a(4)-10 843 y Fs(\001)f Fr(\(1)g Fs(\000)g Fq(\013)p Fr(\))g(+)197 815 y(1)p 197 833 V 197 871 a(4)232 843 y Fs(\001)257 815 y Fr(\(1)h(+)f Fq(\013)p Fr(\))p 257 833 131 2 v 312 871 a(3)402 843 y(+)449 815 y(1)p 449 833 21 2 v 449 871 a(2)484 843 y Fs(\001)509 815 y Fr(\(2)g Fs(\000)h Fq(\013)p Fr(\))p 509 833 131 2 v 564 871 a(3)656 843 y(=)705 815 y(\(2)f Fs(\000)h Fq(\013)p Fr(\))p 705 833 V 760 871 a(3)841 843 y Fq(:)-91 947 y Fn(The)i(\002rst)g(term)g(represents)h(the)e (points)g(with)g Fs(k)p Fq(x)p Fs(k)j(\024)h Fq(s)p Fn(;)e(the)e(sec-) -91 997 y(ond)d(the)h(points)e(with)h Fq(s)k(<)g Fs(k)p Fq(x)p Fs(k)f Fq(<)g(n=)p Fr(2)p Fn(;)e(and)g(the)g(third)e(the)i (points)-91 1047 y(with)e Fs(k)p Fq(x)p Fs(k)k(\025)h Fq(n=)p Fr(2)p Fn(.)g(This)c Fr(\(2)r Fs(\000)r Fq(\013)p Fr(\))p Fq(=)p Fr(3)h Fn(fraction)f(is)g(certainly)g(greater)-91 1096 y(than)-4 1080 y Fo(1)p -4 1087 17 2 v -4 1111 a(2)26 1096 y Fr(+)75 1080 y Fo(0)p Fp(:)p Fo(1)p 73 1087 48 2 v 73 1091 a Fh(p)p 100 1091 21 2 v 21 x Fp(n)136 1096 y Fn(for)i(suf)o(\002ciently)f(lar)o(ge)i Fq(n)f Fn(since)h Fq(\013)g Fs(\024)h Fr(1)p Fq(=)p Fr(4)p Fn(.)p 874 1091 19 19 v -91 1181 a Fg(Pr)o(oof)g(of)g(Lemma)f(4.)36 b Fn(De\002ne)13 b Fq(c)f Fn(so)g(that)f Fq(s)k Fr(=)g Fq(n=)p Fr(2)10 b Fs(\000)g Fq(c)775 1151 y Fs(p)p 810 1151 25 2 v 30 x Fq(n)p Fn(.)18 b(A)-91 1231 y(straightforward)8 b(calculation)i(sho)o(ws)h(that)f Fq(c)j Fs(\025)g Fr(5)p Fq(=)p Fr(16)p Fn(.)h(In)d(partic-)-91 1280 y(ular)n(,)12 1357 y Fh(b)q Fp(n=)p Fo(2)o Fh(c)25 1373 y Fi(X)-67 1470 y Fp(j)r Fo(=)-26 1473 y Fs(d)-8 1470 y Fp(n=)p Fo(2)p Fh(\000)84 1459 y Ff(5)p 77 1464 29 2 v 77 1480 a(16)110 1449 y Fh(p)p 138 1449 21 2 v 138 1470 a Fp(n)158 1473 y Fs(e)184 1353 y Fi(\022)214 1384 y Fq(n)217 1440 y(j)239 1353 y Fi(\023)311 1412 y Fq(<)385 1353 y Fi(\030)424 1384 y Fr(5)p 414 1402 42 2 v 414 1440 a(16)461 1380 y Fs(p)p 495 1380 25 2 v 495 1412 a Fq(n)520 1353 y Fi(\031)c(\026\022) 627 1384 y Fq(n)606 1440 y(n=)p Fr(2)672 1353 y Fi(\023\027)311 1564 y Fs(\024)400 1536 y Fr(5)p 390 1555 42 2 v 390 1593 a(16)436 1532 y Fs(p)p 471 1532 25 2 v 32 x Fq(n)503 1506 y Fi(\022)542 1536 y Fr(0)p Fq(:)p Fr(8)p 538 1555 60 2 v 538 1563 a Fs(p)p 573 1563 25 2 v 30 x Fq(n)603 1506 y Fi(\023)640 1564 y Fr(2)661 1547 y Fp(n)385 1649 y Fn(\(by)j(Stirling')n(s)d(approximation\))311 1711 y Fr(=)42 b(1)p Fq(=)p Fr(4)p Fq(;)-91 1801 y Fn(which)10 b(implies)f Fq(c)j Fs(\025)g Fr(5)p Fq(=)p Fr(16)d Fn(by)h (de\002nition)e(of)i Fq(s)p Fn(.)-41 1859 y(By)k(Lemma)k(2,)e(we)g(kno) o(w)f(that)f Fq(p)481 1865 y Fp(n)p Fh(\000)p Fp(s)566 1859 y Fs(\025)21 b Fq(p)640 1837 y Fp(s=)p Fo(\()p Fp(n)p Fh(\000)p Fp(s)p Fo(\))640 1864 y Fp(s)763 1859 y Fn(.)28 b(Since)-91 1909 y Fq(s=)p Fr(\()p Fq(n)9 b Fs(\000)h Fq(s)p Fr(\))i(=)g(1)d Fs(\000)g Fr(2)p Fq(c)242 1879 y Fs(p)p 277 1879 V 30 x Fq(n)o(=)p Fr(\()p Fq(n=)p Fr(2)g(+)h Fq(c)474 1879 y Fs(p)p 508 1879 V 508 1909 a Fq(n)p Fr(\))p Fn(,)h(we)g(ha)o(v)o(e)-4 2027 y Fq(p)17 2033 y Fp(n)p Fh(\000)p Fp(s)122 2027 y Fs(\025)42 b Fq(p)217 2033 y Fp(s)244 2027 y Fs(\001)9 b Fq(p)286 1995 y Fh(\000)344 1981 y Ff(2)p Fe(c)371 1966 y Fd(p)p 394 1966 19 2 v 15 x Fe(n)p 316 1989 124 2 v 316 2008 a(n=)p Ff(2+)p Fe(c)397 1993 y Fd(p)p 422 1993 19 2 v 422 2008 a Fe(n)286 2032 y Fp(s)459 2027 y Fr(=)i Fq(p)523 2033 y Fp(s)550 2027 y Fs(\001)e Fq(e)623 1991 y Ff(2)p Fe(c)650 1975 y Fd(p)p 673 1975 V 16 x Fe(n)p 595 1998 124 2 v 595 2018 a(n=)p Ff(2+)p Fe(c)676 2002 y Fd(p)p 701 2002 19 2 v 701 2018 a Fe(n)730 2005 y Fo(ln)777 1994 y Ff(1)p 768 1999 32 2 v 768 2015 a Fe(p)783 2019 y(s)122 2115 y Fs(\025)42 b Fq(p)217 2121 y Fp(s)242 2056 y Fi(\022)272 2115 y Fr(1)9 b(+)397 2087 y(2)p Fq(c)436 2057 y Fs(p)p 470 2057 25 2 v 470 2087 a Fq(n)p 349 2105 195 2 v 349 2144 a(n=)p Fr(2)f(+)i Fq(c)484 2114 y Fs(p)p 518 2114 25 2 v 518 2144 a Fq(n)555 2115 y Fr(ln)611 2087 y(1)p 602 2105 39 2 v 602 2143 a Fq(p)623 2149 y Fp(s)645 2056 y Fi(\023)122 2226 y Fs(\025)42 b Fq(p)217 2232 y Fp(s)244 2226 y Fr(+)290 2198 y(3)p Fq(:)p Fr(7)p Fq(c)p 290 2216 72 2 v 296 2225 a Fs(p)p 331 2225 25 2 v 29 x Fq(n)366 2226 y(p)387 2232 y Fp(s)412 2226 y Fr(ln)467 2198 y(1)p 458 2216 39 2 v 458 2254 a Fq(p)479 2260 y Fp(s)511 2226 y Fq(:)-91 2340 y Fn(The)15 b(lemma')n(s)h(hypothesis)d(requires)h Fq(p)505 2346 y Fp(s)543 2340 y Fq(>)20 b Fr(1)p Fq(=)p Fr(4)p Fn(,)15 b(and)g(for)f Fq(f)20 b Fn(to)-91 2390 y(be)13 b(fair)f(we)h(must)g(ha)o(v)o(e)h Fq(p)297 2396 y Fp(s)330 2390 y Fq(<)j Fr(1)p Fq(=)p Fr(2)p Fn(.)j(So)12 b Fq(p)549 2396 y Fp(s)574 2390 y Fr(ln)o(\(1)p Fq(=p)687 2396 y Fp(s)705 2390 y Fr(\))h Fn(is)f(at)h(least)-91 2440 y Fr(\(1)p Fq(=)p Fr(2\))7 b(ln)f(2)p Fn(.)13 b(This)d(gi)o(v)o (es)g(us)94 2551 y Fq(p)115 2557 y Fp(n)p Fh(\000)p Fp(s)190 2551 y Fs(\025)i Fq(p)255 2557 y Fp(s)282 2551 y Fr(+)328 2523 y(3)p Fq(:)p Fr(7)p Fq(c)7 b Fr(ln)f(2)p 328 2542 141 2 v 358 2580 a(2)379 2550 y Fs(p)p 414 2550 25 2 v 30 x Fq(n)485 2551 y Fs(\025)12 b Fq(p)550 2557 y Fp(s)577 2551 y Fr(+)626 2523 y(0)p Fq(:)p Fr(4)p 623 2542 60 2 v 623 2550 a Fs(p)p 658 2550 25 2 v 30 x Fq(n)697 2551 y(;)-91 2663 y Fn(which)e(is)g(what)g(we)h(want.)p 874 2658 19 19 v 987 42 a Fg(Pr)o(oof)g(of)f(Lemma)f(5.)26 b Fn(Note)10 b(that)g(for)f Fq(i)j(<)g(s)p Fn(,)f(we)g(ha)o(v)o(e)1082 122 y Fq(p)1103 128 y Fp(n)p Fh(\000)p Fp(i)1175 122 y Fs(\025)g Fq(p)1239 128 y Fp(n)p Fh(\000)p Fp(s)1315 122 y Fs(\025)h Fq(p)1380 128 y Fp(s)1407 122 y Fr(+)d(0)p Fq(:)p Fr(4)p Fq(=)1523 90 y Fs(p)p 1557 90 25 2 v 1557 122 a Fq(n)i Fs(\025)h Fq(p)1658 128 y Fp(i)1681 122 y Fr(+)d(0)p Fq(:)p Fr(4)p Fq(=)1797 90 y Fs(p)p 1831 90 V 1831 122 a Fq(n)g(;)987 202 y Fn(by)f(our)g(hypothesis)e(and)j (the)f(fact)g(that)g Fq(p)1576 208 y Fp(k)1605 202 y Fn(increases)h(with)e Fq(k)q Fn(.)13 b(Also)987 252 y(note)i(that)1152 221 y Fi(P)1196 231 y Fp(n)1196 264 y(i)p Fo(=0)1258 252 y Fq(p)1279 258 y Fp(i)1293 218 y Fi(\000)1312 233 y Fp(n)1316 266 y(i)1333 218 y Fi(\001)1373 252 y Fr(=)21 b(\(1)p Fq(=)p Fr(2\))13 b Fs(\001)f Fr(2)1579 237 y Fp(n)1602 252 y Fn(,)17 b(since)f Fq(f)k Fn(is)15 b(fair)n(.)28 b(The)987 302 y(number)10 b(of)g(points)f Fq(x)h Fn(where)h Fq(h)p Fr(\()p Fq(x)p Fr(\))g(=)h(1)e Fn(and)h Fq(f)t Fr(\()p Fq(x)p Fr(\))h(=)g(1)e Fn(is)1136 363 y Fp(n)1116 376 y Fi(X)1085 467 y Fp(i)p Fo(=)p Fh(d)q Fp(n=)p Fo(2)o Fh(e)1214 415 y Fq(p)1235 421 y Fp(i)1249 356 y Fi(\022)1279 387 y Fq(n)1285 443 y(i)1304 356 y Fi(\023)1127 580 y Fr(=)1206 552 y(1)p 1206 570 21 2 v 1206 608 a(2)1238 496 y Fi(0)1238 571 y(@)1297 528 y Fp(s)1275 540 y Fi(X)1278 629 y Fp(i)p Fo(=0)1341 580 y Fq(p)1362 586 y Fp(n)p Fh(\000)p Fp(i)1423 521 y Fi(\022)1453 552 y Fq(n)1459 608 y(i)1478 521 y Fi(\023)1518 580 y Fr(+)1559 524 y Fh(d)q Fp(n=)p Fo(2)o Fh(e\000)p Fo(1)1593 540 y Fi(X)1575 629 y Fp(i)p Fo(=)p Fp(s)p Fo(+1)1693 580 y Fq(p)1714 586 y Fp(n)p Fh(\000)p Fp(i)1775 521 y Fi(\022)1805 552 y Fq(n)1810 608 y(i)1830 521 y Fi(\023)1236 746 y Fr(+)1325 694 y Fp(n)1306 706 y Fi(X)1275 797 y Fp(i)p Fo(=)p Fh(d)p Fp(n=)p Fo(2)o Fh(e)1404 746 y Fq(p)1425 752 y Fp(i)1438 687 y Fi(\022)1469 718 y Fq(n)1474 774 y(i)1494 687 y Fi(\023)1524 662 y(1)1524 737 y(A)1127 899 y Fs(\025)1206 871 y Fr(1)p 1206 890 V 1206 928 a(2)1238 828 y Fi( )1293 847 y Fp(s)1271 860 y Fi(X)1274 948 y Fp(i)p Fo(=0)1338 841 y Fi(\022)1369 899 y Fq(p)1390 905 y Fp(i)1413 899 y Fr(+)1462 871 y(0)p Fq(:)p Fr(4)p 1459 890 60 2 v 1459 898 a Fs(p)p 1494 898 25 2 v 30 x Fq(n)1524 841 y Fi(\023)c(\022)1592 871 y Fq(n)1597 928 y(i)1616 841 y Fi(\023)1236 1054 y Fr(+)1275 999 y Fh(d)p Fp(n=)p Fo(2)o Fh(e\000)p Fo(1)1308 1015 y Fi(X)1291 1103 y Fp(i)p Fo(=)p Fp(s)p Fo(+1)1409 1054 y Fq(p)1430 1060 y Fp(i)1443 996 y Fi(\022)1474 1026 y Fq(n)1479 1083 y(i)1499 996 y Fi(\023)1539 1054 y Fr(+)1631 1002 y Fp(n)1611 1015 y Fi(X)1580 1106 y Fp(i)p Fo(=)p Fh(d)q Fp(n=)p Fo(2)o Fh(e)1709 1054 y Fq(p)1730 1060 y Fp(i)1744 996 y Fi(\022)1774 1026 y Fq(n)1779 1083 y(i)1799 996 y Fi(\023)1830 971 y(1)1830 1045 y(A)1127 1204 y Fr(=)1206 1176 y(1)p 1206 1194 21 2 v 1206 1232 a(4)1241 1204 y Fs(\001)i Fr(2)1282 1186 y Fp(n)1314 1204 y Fr(+)1374 1176 y(0)p Fq(:)p Fr(4)p 1360 1194 81 2 v 1360 1232 a(2)1381 1202 y Fs(p)p 1416 1202 25 2 v 30 x Fq(n)1475 1152 y Fp(s)1453 1164 y Fi(X)1456 1253 y Fp(i)p Fo(=0)1519 1145 y Fi(\022)1550 1176 y Fq(n)1555 1232 y(i)1575 1145 y Fi(\023)1127 1328 y Fs(\025)1206 1300 y Fr(1)p 1206 1319 21 2 v 1206 1357 a(4)1241 1328 y Fs(\001)g Fr(2)1282 1311 y Fp(n)1314 1328 y Fr(+)1374 1300 y(0)p Fq(:)p Fr(4)p 1360 1319 81 2 v 1360 1357 a(8)1381 1327 y Fs(p)p 1416 1327 25 2 v 30 x Fq(n)1455 1328 y Fs(\001)h Fr(2)1497 1311 y Fp(n)1528 1328 y Fq(:)987 1430 y Fn(Since)f Fq(h)h Fn(and)f Fq(f)13 b Fn(are)c(both)e(fair)g (functions,)h(the)g(number)g(of)g(points)f Fq(x)987 1480 y Fn(for)h(which)g Fq(h)p Fr(\()p Fq(x)p Fr(\))j(=)h(0)d Fn(and)f Fq(f)t Fr(\()p Fq(x)p Fr(\))k(=)g(1)d Fn(is)f(the)g(same)i(as) f(the)f(number)987 1530 y(of)k(points)e Fq(x)i Fn(for)g(which)g Fq(h)p Fr(\()p Fq(x)p Fr(\))i(=)i(1)c Fn(and)g Fq(f)t Fr(\()p Fq(x)p Fr(\))k(=)f(0)p Fn(.)j(Therefore,)987 1580 y(the)13 b(number)h(of)f(points)f Fq(x)h Fn(where)h Fq(h)p Fr(\()p Fq(x)p Fr(\))j(=)h(0)13 b Fn(and)h Fq(f)t Fr(\()p Fq(x)p Fr(\))k(=)f(0)d Fn(is)987 1629 y(also)c(at)h(least)1315 1661 y Fr(1)p 1315 1679 21 2 v 1315 1717 a(4)1350 1689 y Fs(\001)d Fr(2)1391 1672 y Fp(n)1423 1689 y Fr(+)1483 1661 y(0)p Fq(:)p Fr(4)p 1469 1679 81 2 v 1469 1718 a(8)1490 1688 y Fs(p)p 1525 1688 25 2 v 30 x Fq(n)1564 1689 y Fs(\001)h Fr(2)1606 1672 y Fp(n)1637 1689 y Fq(:)1037 1781 y Fn(Thus)h(the)f(total)g(number)h(of)f(points)f(where)j Fq(h)p Fr(\()p Fq(x)p Fr(\))g(=)h Fq(f)t Fr(\()p Fq(x)p Fr(\))f Fn(is)e(at)987 1831 y(least)1141 1898 y Fr(1)p 1141 1916 21 2 v 1141 1954 a(2)1175 1926 y Fs(\001)g Fr(2)1217 1909 y Fp(n)1249 1926 y Fr(+)1295 1898 y(2)g Fs(\001)g Fr(0)p Fq(:)p Fr(4)p 1295 1916 104 2 v 1307 1955 a(8)1328 1925 y Fs(p)p 1362 1925 25 2 v 1362 1955 a Fq(n)1413 1926 y Fs(\001)g Fr(2)1455 1909 y Fp(n)1489 1926 y Fr(=)j(2)1554 1909 y Fp(n)1583 1867 y Fi(\022)1619 1898 y Fr(1)p 1619 1916 21 2 v 1619 1954 a(2)1653 1926 y(+)1703 1898 y(0)p Fq(:)p Fr(1)p 1700 1916 60 2 v 1700 1925 a Fs(p)p 1735 1925 25 2 v 30 x Fq(n)1764 1867 y Fi(\023)1811 1926 y Fq(:)987 2028 y Fn(Therefore)20 b(the)e(majority)g (function)f(has)i(an)h(error)e(of)h(at)g(most)987 2078 y Fr(1)p Fq(=)p Fr(2)8 b Fs(\000)i Fr(0)p Fq(:)p Fr(1)p Fq(=)1175 2048 y Fs(p)p 1208 2048 V 1208 2078 a Fq(n)p Fn(.)p 1953 2073 19 19 v 987 2210 a Fu(3.)j(Lear)o(ning)f(monotone)g (and)f(unate)h(functions)1037 2314 y Fn(In)g(this)g(section)g(we)h(sho) o(w)f(ho)o(w)h(the)f(pre)o(vious)g(algorithm)f(for)987 2364 y(learning)17 b(fair)g(monotone)f(functions)g(can)j(be)f(e)o (xtended)g(to)f(the)987 2413 y(class)9 b(of)f(general)g(monotone)f (functions)g(and)h(the)g(broader)g(class)h(of)987 2463 y(\223unate\224)j(Boolean)g(functions,)e(with)h(essentially)g(the)g (same)j(guar)o(-)987 2513 y(antees.)32 b(This)17 b(implies)f(our)g (main)g(positi)o(v)o(e)g(result,)h(a)g(learning)987 2563 y(algorithm)9 b(achie)o(ving)g(error)i Fr(1)p Fq(=)p Fr(2)d Fs(\000)i Fr(\012\(1)p Fq(=)1622 2533 y Fs(p)p 1656 2533 25 2 v 1656 2563 a Fq(n)p Fr(\))p Fn(.)1037 2613 y(First)i(we)i(sho)o(w)f(ho)o(w)g(to)g(work)f(around)h(our)g (earlier)g(assump-)987 2663 y(tion)c(that)h Fq(n)g Fn(is)g(odd.)p eop %%Page: 4 4 4 3 bop -91 42 a Fg(Lemma)9 b(6)21 b Ft(If)13 b Fq(f)19 b Ft(is)14 b(a)f(fair)g(monotone)g(tar)n(get)g(function)f(over)j(an)-91 91 y(e)o(ven)e(number)e(of)g(variables,)h(then)f(the)g(majority)f (function)g Fq(h)i Ft(has)-91 141 y(err)n(or)f(at)f(most)f Fr(1)p Fq(=)p Fr(2)g Fs(\000)g Fr(0)p Fq(:)p Fr(1)p Fq(=)324 109 y Fs(p)p 358 109 97 2 v 358 141 a Fq(n)g Fr(+)g(1)p Ft(.)-91 217 y Fg(Pr)o(oof)o(.)19 b Fn(F)o(or)12 b(each)h Fr(\()p Fq(n)d Fr(+)h(1\))p Fn(-bit)g(v)o(ector)h Fq(x)532 202 y Fh(0)543 217 y Fn(,)h(de\002ne)g Fq(f)704 202 y Fh(0)716 217 y Fr(\()p Fq(x)756 202 y Fh(0)768 217 y Fr(\))f Fn(as)g(the)-91 267 y(v)o(alue)h(of)f Fq(f)18 b Fn(on)13 b Fq(x)175 252 y Fh(0)199 267 y Fn(with)f(the)h(last)f(bit)g (remo)o(v)o(ed.)22 b(Since)13 b Fq(f)18 b Fn(is)13 b(fair)-91 317 y(and)d(monotone,)g Fq(f)190 301 y Fh(0)213 317 y Fn(is)g(fair)f(and)i(monotone.)-41 366 y(Say)k(we)g(ha)o(v)o(e)g(a)g (random)g Fq(n)p Fn(-bit)e(v)o(ector)i Fq(x)f Fn(with)g(label)g Fq(f)t Fr(\()p Fq(x)p Fr(\))p Fn(.)-91 416 y(Let)d Fq(x)-1 401 y Fh(0)22 416 y Fn(be)g Fq(x)f Fn(with)g(a)i(random)f(bit)e (appended,)j(and)f(predict)f Fq(h)p Fr(\()p Fq(x)855 401 y Fh(0)867 416 y Fr(\))p Fn(.)-91 466 y(\(This)i(is)g(equi)o(v)o (alent)f(to)g(the)h(majority)f(function)g(on)h Fq(n)g Fn(v)o(ariables,)-91 516 y(with)17 b(the)h(label)g(chosen)h(randomly)e (if)h Fs(k)o Fq(x)p Fs(k)26 b Fr(=)h Fq(n=)p Fr(2)p Fn(.\))36 b(Since)-91 566 y Fq(f)-67 551 y Fh(0)-55 566 y Fr(\()p Fq(x)-15 551 y Fh(0)-3 566 y Fr(\))13 b(=)g Fq(f)t Fr(\()p Fq(x)p Fr(\))p Fn(,)f(by)e(Theorem)i(1,)f(the)g(probability)d(that)j Fq(h)p Fr(\()p Fq(x)821 551 y Fh(0)832 566 y Fr(\))i Fs(6)p Fr(=)-91 615 y Fq(f)t Fr(\()p Fq(x)p Fr(\))e Fn(is)f(at)g(most)h Fr(1)p Fq(=)p Fr(2)d Fs(\000)i Fr(0)p Fq(:)p Fr(1)p Fq(=)358 583 y Fs(p)p 391 583 V 391 615 a Fq(n)f Fr(+)h(1)o Fn(.)p 874 610 19 19 v -91 737 a Fc(3.1.)i(Lear)o(ning)h(monotone)f(functions) -41 837 y Fn(T)m(o)17 b(transform)g(an)g(algorithm)f(for)h(learning)f (fair)h(monotone)-91 887 y(functions)f(into)h(an)h(algorithm)f(for)g (learning)g(monotone)h(func-)-91 937 y(tions,)f(we)g(do)f(the)g(follo)o (wing.)30 b(W)m(e)16 b(sample)i(enough)d(times)i(to)-91 986 y(determine)11 b(whether)g(the)g(tar)o(get)g(concept)g(is)g (approximately)f(fair)n(.)-91 1036 y(If)k(it)f(is)h(far)g(enough)g(a)o (way)h(from)f(fair)20 b(then)14 b(we)h(can)g(output)d(the)-91 1086 y(constant-zero)e(or)g(constant-one)g(function.)i(If)e(not,)g (then)g(we)h(out-)-91 1136 y(put)i(what)h(the)g(fair)o(-function)e (algorithm)h(does)i(for)f(the)g(concept.)-91 1186 y(The)d(follo)o(wing) d(lemma)j(makes)g(this)e(ar)o(gument)i(concrete.)-91 1268 y Fg(Lemma)e(7)21 b Ft(Say)15 b(we)h(have)h(an)e(algorithm)e Fq(A)j Ft(for)g(learning)e(fair)-91 1318 y(monotone)e(functions,)h (whic)o(h)f(uses)i(no)f(samples)g(and)g(outputs)e(a)-91 1368 y(hypothesis)d(with)f(err)n(or)i(at)f(most)g Fr(1)p Fq(=)p Fr(2)s Fs(\000)s Fq(\017)p Ft(.)k(Then)c(for)g(any)h Fq(\013;)e(\016)13 b(>)e Fr(0)-91 1417 y Ft(we)e(can)f(construct)h(an)f (algorithm)f Fq(A)450 1402 y Fh(0)470 1417 y Ft(for)h(learning)g(all)f (monotone)-91 1467 y(functions,)17 b(\002nding)d(a)j(hypothesis)f(with) f(err)n(or)i(at)f(most)g Fr(1)p Fq(=)p Fr(2)d Fs(\000)-91 1517 y Fq(\017=)p Fr(\(2)d(+)i Fq(\013)p Fr(\))g Ft(with)f(pr)n (obability)g Fr(1)g Fs(\000)g Fq(\016)r Ft(.)20 b(This)13 b(algorithm)d Fq(A)790 1502 y Fh(0)815 1517 y Ft(calls)-91 1567 y Fj(SAMPLE)276 1605 y Fr(2\(2)f(+)h Fq(\013)p Fr(\))428 1590 y Fo(2)p 276 1623 170 2 v 321 1661 a Fq(\013)348 1649 y Fo(2)366 1661 y Fq(\017)383 1649 y Fo(2)458 1633 y Fr(ln)505 1605 y(1)p 505 1623 21 2 v 505 1661 a Fq(\016)-91 1712 y Ft(times.)-91 1794 y Fg(Remark.)66 b Fn(F)o(or)17 b(simplicity)e(we)j(e)o(xamine)g(a)f(se)o(v)o(erely)h(hand-)-91 1844 y(icapped)f(algorithm)f Fq(A)i Fn(which)f(uses)h(no)f(samples)h (and)g(has)g(no)-91 1894 y(chance)11 b(of)e(failure,)g(since)h(the)f (particular)g(algorithm)f(we)i(are)g(con-)-91 1944 y(sidering)j(has)i (these)g(properties.)25 b(The)15 b(theorem)g(also)f(holds)g(for)-91 1994 y(more)d(general)g(algorithms,)e(at)i(the)f(e)o(xpense)i(of)e (added)h(comple)o(x-)-91 2043 y(ity)e(and)h(slightly)e(worse)i(bounds.) -91 2115 y Fg(Pr)o(oof)o(.)22 b Fn(Say)13 b(that)f(the)h(tar)o(get)g (concept)g Fq(f)k Fn(labels)c(a)h Fq(\015)i Fn(fraction)c(of)-91 2164 y(the)c(points)g(with)g Fr(1)p Fn(.)k(The)e(ne)o(w)f(algorithm)e Fq(A)557 2149 y Fh(0)578 2164 y Fn(uses)i(the)g(samples)h(to)-91 2214 y(obtain)e(an)i(estimate)h Fr(~)-22 b Fq(\015)12 b Fn(of)d Fq(\015)r Fn(.)14 b(By)9 b(Hoef)o(fding)f(bounds,)h(with)f (prob-)-91 2264 y(ability)e(at)i(least)h Fr(1)r Fs(\000)r Fq(\016)g Fn(our)f(estimate)i Fr(~)-22 b Fq(\015)11 b Fn(is)d(within)e Fq(\015)t Fs(\006)r Fq(\013\017=)p Fr(2\(2)r(+)r Fq(\013)p Fr(\))p Fn(.)-91 2314 y(Assume)13 b(that)e(this)g(happens.)19 b(If)13 b Fr(~)-23 b Fq(\015)18 b Fs(\025)d Fr(1)p Fq(=)p Fr(2)10 b(+)h Fq(\017=)p Fr(2)p Fn(,)h(then)f Fq(A)802 2299 y Fh(0)826 2314 y Fn(out-)-91 2364 y(puts)f(the)g(constant-one)g (function)f Fq(h)p Fr(\()p Fq(x)p Fr(\))k(=)f(1)p Fn(.)j(Since)c(in)f (this)g(case)-91 2413 y Fq(\015)k Fs(\025)e Fr(1)p Fq(=)p Fr(2)6 b(+)g Fq(\017=)p Fr(2)g Fs(\000)g Fq(\013\017=)p Fr(2\(2)g(+)g Fq(\013)p Fr(\))11 b(=)h(1)p Fq(=)p Fr(2)6 b(+)g Fq(\017=)p Fr(\(2)g(+)g Fq(\013)p Fr(\))p Fn(,)k(the)g(error)-91 2463 y(is)i(at)h(most)g Fr(1)p Fq(=)p Fr(2)d Fs(\000)i Fq(\017=)p Fr(\(2)e(+)i Fq(\013)p Fr(\))p Fn(.)20 b(Similarly)m(,)13 b(if)h Fr(~)-23 b Fq(\015)19 b Fs(\024)e Fr(1)p Fq(=)p Fr(2)10 b Fs(\000)h Fq(\017=)p Fr(2)p Fn(,)-91 2513 y(then)i Fq(A)25 2498 y Fh(0)50 2513 y Fn(outputs)f(the)h(constant-zero)g (function)f Fq(h)p Fr(\()p Fq(x)p Fr(\))17 b(=)g(0)c Fn(with)-91 2563 y(error)d(at)g(most)g Fr(1)p Fq(=)p Fr(2)f Fs(\000)g Fq(\017=)p Fr(\(2)g(+)h Fq(\013)p Fr(\))p Fn(.)-41 2613 y(Otherwise,)18 b(if)f Fr(~)-23 b Fq(\015)20 b Fn(is)c(within)e Fr(1)p Fq(=)p Fr(2)f Fs(\006)h Fq(\017=)p Fr(2)p Fn(,)k(then)e Fq(\015)j Fn(is)d(within)-91 2663 y Fr(1)p Fq(=)p Fr(2)t Fs(\006)t Fr(\(1)t(+)t Fq(\013)p Fr(\))p Fq(\017=)p Fr(\(2)t(+)t Fq(\013)p Fr(\))p Fn(,)9 b(and)g Fq(A)409 2647 y Fh(0)430 2663 y Fn(outputs)e(whate)o(v)o(er)i Fq(A)h Fn(outputs.)987 42 y(This)j(hypothesis)e(may)j(err)f(on)g(the)f (points)g(of)h(the)f(fair)h(function,)987 91 y(plus)e(it)f(may)i(err)g (on)f(that)g Fr(\(1)f(+)g Fq(\013)p Fr(\))p Fq(\017=)p Fr(\(2)f(+)i Fq(\013)p Fr(\))g Fn(fraction)g(of)g(points)987 141 y(that)d(must)g(be)g(relabeled)h(in)e(order)h(to)g(make)h Fq(f)k Fn(fair)n(.)e(Thus)e(the)f(error)987 191 y(of)i(this)f (hypothesis)f(is)i(at)g(most)g Fr(1)p Fq(=)p Fr(2)d Fs(\000)h Fq(\017)g Fr(+)h(\(1)f(+)g Fq(\013)p Fr(\))p Fq(\017=)p Fr(\(2)f(+)i Fq(\013)p Fr(\))i(=)987 241 y(1)p Fq(=)p Fr(2)d Fs(\000)i Fq(\017=)p Fr(\(2)f(+)g Fq(\013)p Fr(\))p Fn(.)1037 291 y(The)h(only)f(possibility)e(that)i(leads)h(to)f(an)h (incorrect)g(hypothesis)987 340 y(is)h(if)g(we)h(misestimate)i Fr(~)-23 b Fq(\015)14 b Fn(by)e(a)g(wide)f(mar)o(gin.)17 b(Since)11 b(this)g(occurs)987 390 y(with)f(probability)e(at)k(most)f Fq(\016)r Fn(,)g(we)h(ha)o(v)o(e)g(the)f(required)g(guarantee.)p 987 435 19 19 v 1037 514 a(As)f(a)h(corollary)e(we)i(no)o(w)f(ha)o(v)o (e)h(our)f(learning)f(algorithm.)987 602 y Fg(Theor)o(em)i(8)20 b Ft(In)g(polynomial)e(time)i(we)g(can)h(learn)f(monotone)987 652 y(functions)9 b(guar)o(anteeing)g(err)n(or)i(at)e(most)h Fr(1)p Fq(=)p Fr(2)f Fs(\000)g Fr(0)p Fq(:)p Fr(04)p Fq(=)1817 622 y Fs(p)p 1850 622 25 2 v 1850 652 a Fq(n)p Ft(.)987 740 y Fg(Pr)o(oof)o(.)24 b Fn(Let)14 b Fq(A)g Fn(be)g(the)f(algorithm)f(that)h(performs)h(no)f(sampling)987 790 y(or)h(computation)f(and)i(blindly)d(outputs)h(the)h(majority)g (function.)987 840 y(By)k(Theorem)i(1,)h(this)d(algorithm)f(always)i (has)g(error)g(at)g(most)987 889 y Fr(1)p Fq(=)p Fr(2)11 b Fs(\000)i Fr(0)p Fq(:)p Fr(1)p Fq(=)1181 860 y Fs(p)p 1214 860 V 1214 889 a Fq(n)h Fn(on)g(fair)g(monotone)f(tar)o(get)h (concepts.)26 b(W)m(e)14 b(ap-)987 939 y(ply)9 b(Lemma)k(7)d(with)f Fq(\013)i Fr(=)h(1)p Fq(=)p Fr(2)e Fn(to)f(get)h(our)g(algorithm.)p 1953 934 19 19 v 1037 1013 a(This)17 b(algorithm)g(is)g(particularly)f (simple:)27 b(The)18 b(amount)g(of)987 1063 y(time)e(it)f(requires)h (in)f(linear)h(in)f Fq(n)p Fn(;)k(it)c(uses)i(only)d(the)i(labels)g (re-)987 1112 y(turned)9 b(by)g Fj(SAMPLE)16 b Fn(and)10 b(not)f(the)h(actual)g(bit)e(v)o(ectors;)i(and,)h(the)987 1162 y(algorithm)e(has)i(only)f(three)h(possible)f(outputs)f(\(the)h (constant-one)987 1212 y(function,)f(the)h(constant-zero)h(function,)e (and)h(the)h(majority)e(func-)987 1262 y(tion\).)987 1364 y Fc(3.2.)j(Generalizations)1037 1467 y Fn(Another)18 b(transformation)f(generalizes)j(the)e(class)i(of)f(func-)987 1517 y(tions)12 b(further)h(to)g(encompass)i Ft(unate)e Fn(functions)g(\(in)g(some)h(com-)987 1567 y(munities,)e(these)h(are)h (called)e(monotone)g(functions\).)18 b(Say)13 b(that)f(a)987 1616 y(v)o(ariable)h(is)f(a)i Ft(positive)e(indicator)g Fn(for)g(a)i(Boolean)e(function)f Fq(f)18 b Fn(if)987 1666 y(\003ipping)13 b(the)i(v)o(ariable)f(from)h(zero)g(to)f(one)h(ne) o(v)o(er)g(turns)f Fq(f)20 b Fn(from)987 1716 y(one)13 b(to)g(zero,)h(and)g(say)f(that)g(it)f(is)h(a)h Ft(ne)n(gative)f (indicator)f Fn(for)h Fq(f)18 b Fn(if)987 1766 y(\003ipping)13 b(the)i(v)o(ariable)f(from)h(one)f(to)g(zero)i(ne)o(v)o(er)f(turns)f Fq(f)20 b Fn(from)987 1816 y(one)12 b(to)g(zero.)21 b(In)12 b(monotone)f(functions,)h(all)h(v)o(ariables)f(are)h(posi-)987 1865 y(ti)o(v)o(e)f(indicators;)g(in)g(a)g(unate)h(function,)f(e)o(v)o (ery)g(v)o(ariable)h(is)f(either)987 1915 y(a)f(positi)o(v)o(e)e (indicator)g(or)h(a)h(ne)o(gati)o(v)o(e)f(indicator)n(.)1037 1965 y(If)e(we)g(ha)o(v)o(e)h(an)g(algorithm)d(for)i(learning)f (monotone)g(functions,)987 2015 y(then)j(we)g(can)h(construct)f(an)g (algorithm)f(for)g(learning)h(unate)g(func-)987 2065 y(tions.)17 b(The)12 b(technique)f(is)h(similar)f(to)h(that)f(of)g (Lemma)j(7.)k(In)11 b(this)987 2115 y(case,)17 b(we)e(determine)f(for)g (each)i(v)o(ariable)e(whether)g(it)f(is)h(a)h(posi-)987 2164 y(ti)o(v)o(e)f(or)g(a)h(ne)o(gati)o(v)o(e)f(indicator)n(.)24 b(W)m(e)14 b(then)g(use)h(this)e(information)987 2214 y(to)f(transform)g(the)g(unate)g(tar)o(get)h(concept)f(into)f(a)i (concept)g(that)f(is)987 2264 y(probably)d(a)i(\223mostly\224)f (monotone)f(function.)1037 2314 y(All)h(that)g(remains)h(is)g(to)f(sho) o(w)h(that)f(v)o(ariables)h(which)f(indi)o(vid-)987 2364 y(ually)15 b(do)g(not)g(e)o(xhibit)f(much)i(correlation)e(do)h(not)g (cause)i(much)987 2413 y(harm)c(if)f(the)o(y)g(are)i(wrongly)d(cate)o (gorized.)21 b(Since)12 b(the)h(algorithm)987 2463 y(miscate)o(gorizes) 20 b(v)o(ariables)f(only)f(if)g(their)g(correlation)g(is)h(v)o(ery)987 2513 y(weak,)13 b(the)e(fraction)g(of)g(points)f(that)h(must)g(be)h (relabeled)g(in)f(order)987 2563 y(to)h(make)i(the)f(transformed)g (function)e(monotone)i(is)g(v)o(ery)g(small.)987 2613 y(By)e(estimating)g(the)h(correlations)f(accurately)h(enough,)g(the)g (frac-)987 2662 y(tion)i(becomes)j(so)e(small)h(that)f(with)f(high)h (probability)d(none)k(of)p eop %%Page: 5 5 5 4 bop -91 42 a Fn(the)8 b(labeled)g(e)o(xamples)h(that)f Fj(SAMPLE)14 b Fn(returns)7 b(in)h(a)h(subsequent)-91 91 y(dra)o(w)j(are)g(points)e(that)h(must)h(be)f(relabeled.)18 b(Thus)11 b(the)h(algorithm)-91 141 y(pro)o(vides)f(an)i(good)e (estimate)i(to)e(this)h(function.)17 b(Though)11 b(it)h(may)-91 191 y(err)f(on)f(the)h(small)g(fraction)f(that)h(are)g(relabeled,)h(it) e(is)h(also)g(a)g(good)-91 241 y(estimate)g(to)e(the)h(original)f (function.)-41 291 y(The)j(follo)o(wing)e(lemma)j(gi)o(v)o(es)f(the)g (precise)h(statement)g(of)e(the)-91 340 y(result;)e(the)h(proof)f (appears)i(in)f(the)g(appendix.)-91 428 y Fg(Lemma)f(9)21 b Ft(Say)13 b(we)h(have)h(an)e(algorithm)e Fq(A)j Ft(for)g(weakly)g (learn-)-91 478 y(ing)e(monotone)f(incr)n(easing)i(Boolean)f (functions,)g(whic)o(h)h(uses)g(at)-91 528 y(most)d Fq(s)h Ft(calls)f(to)g Fj(SAMPLE)16 b Ft(to)10 b(output)e(a)j(hypothesis)e (with)g(err)n(or)-91 578 y(at)g(most)g Fr(1)p Fq(=)p Fr(2)e Fs(\000)g Fq(\017)j Ft(with)e(pr)n(obability)g Fr(1)f Fs(\000)g Fq(\016)r(=)p Fr(4)p Ft(.)13 b(Then)d(we)g(can)f(con-) -91 628 y(struct)h(an)g(algorithm)e Fq(A)271 612 y Fh(0)293 628 y Ft(for)h(weakly)i(learning)e(unate)h(functions,)-91 677 y(\002nding)d(a)i(hypothesis)f(with)g(err)n(or)i(at)e(most)h Fr(1)p Fq(=)p Fr(2)t Fs(\000)t Fq(\017=)p Fr(2)f Ft(with)g(pr)n(ob-)-91 727 y(ability)g Fr(1)h Fs(\000)h Fq(\016)r Ft(.)j(This)d(algorithm)e Fq(A)427 712 y Fh(0)449 727 y Ft(calls)i Fj(SAMPLE)16 b Ft(at)10 b(most)291 833 y Fq(s)g Fr(+)374 805 y(2)p 366 823 36 2 v 366 861 a(^)-21 b Fq(\017)383 849 y Fo(2)414 833 y Fr(ln)460 805 y(8)p Fq(n)p 460 823 46 2 v 473 861 a(\016)-91 932 y Ft(times,)10 b(wher)n(e)i Fr(^)-22 b Fq(\017)11 b Ft(is)f(de\002ned)g(as)201 1042 y Fr(^)-22 b Fq(\017)12 b Fr(=)313 1014 y(min)n Fs(f)p Fq(\017;)7 b(\016)r(=)p Fr(2)p Fq(s)p Fs(g)p 278 1033 299 2 v 278 1077 a Fq(n)i Fr(+)353 1041 y Fi(p)p 395 1041 182 2 v 36 x Fr(2)p Fq(n)e Fr(ln)o(\(4)p Fq(=\016)r Fr(\))590 1042 y Fq(:)-91 1185 y Fu(4.)13 b(Hardness)f(of)g(lear)o(ning)-41 1291 y Fn(W)m(e)19 b(no)o(w)f(pro)o(v)o(e)h(that)f(no)g(algorithm,)i (gi)o(v)o(en)e(only)f(a)j(poly-)-91 1341 y(nomial)15 b(number)g(of)g(calls)h(to)f Fj(SAMPLE)21 b Fn(or)15 b Fj(MEMBER)s Fn(,)j(can)-91 1391 y(achie)o(v)o(e)10 b(correlation)d(more)i(than)g(an)g Fq(O)q Fr(\(log)d Fq(n)p Fr(\))j Fn(factor)f(better)h(than)-91 1441 y(the)14 b(algorithm)f(of)i(Theorem)g(8.)26 b(This)14 b(proof)g(does)h(not)e (rely)i(on)-91 1490 y(computational)e(hardness;)j(e)o(v)o(en)f(if)f (the)g(algorithm)f(has)i(in\002nite)-91 1540 y(computation)d(time,)k (the)e(information)e(a)o(v)o(ailable)i(from)g(the)f(ora-)-91 1590 y(cles)e(does)f(not)g(permit)f(a)i(better)f(correlation.)-91 1678 y Fg(Theor)o(em)h(10)20 b Ft(F)l(or)12 b(suf)o(\002ciently)f(lar)n (ge)h Fq(n)p Ft(,)g(for)g(any)g Fq(s)j Fs(\025)g Fq(n)p Ft(,)d(ther)n(e)-91 1728 y(e)o(xists)k(a)f(distrib)o(ution)d Fq(P)287 1734 y Fp(s)320 1728 y Ft(over)j(monotone)f(Boolean)h (functions)-91 1778 y(with)d(the)h(following)e(pr)n(operty:)19 b(F)l(or)14 b(any)g(algorithm)d Fq(A)j Ft(making)-91 1827 y(at)d(most)h Fq(s)g Ft(calls)f(to)h Fj(MEMBER)s Ft(,)g(the)g(e)o(xpected)h(err)n(or)g(of)e Fq(A)i Ft(\(the)-91 1877 y(pr)n(obability)7 b(over)i Fq(P)210 1883 y Fp(s)228 1877 y Ft(,)g(over)h(any)f(internal)f(r)o(andom)g(c)o(hoices)i(of)f Fq(A)p Ft(,)-91 1927 y(and)g(over)i(the)f(c)o(hoice)g(of)g(a)g(r)o (andom)g(test)f(e)o(xample)i Fq(x)p Ft(,)f(that)f(A)i(pr)n(e-)-91 1977 y(dicts)j(incorr)n(ectly)h(on)f Fq(x)p Ft(\))g(is)h(at)f(least)g Fr(1)p Fq(=)p Fr(2)d Fs(\000)i Fq(O)q Fr(\(log\()p Fq(sn)p Fr(\))p Fq(=)807 1947 y Fs(p)p 842 1947 25 2 v 30 x Fq(n)p Fr(\))p Ft(.)-91 2027 y(Thus,)19 b(no)d(algorithm)f(can)i(guar)o(antee) g(e)o(xpected)i(err)n(or)e Fr(1)p Fq(=)p Fr(2)d Fs(\000)-91 2076 y Fq(!)q Fr(\(\(log)7 b Fq(n)p Fr(\))p Fq(=)91 2047 y Fs(p)p 125 2047 V 125 2076 a Fq(n)p Fr(\))k Ft(given)f(a)g (polynomial)e(number)j(of)e(queries.)-41 2164 y Fn(Notice)14 b(that)f(gi)o(v)o(en)h(access)i(to)e Fj(MEMBER)s Fn(,)h(the)f Fj(SAMPLE)-91 2214 y Fn(oracle)g(is)f(redundant)f(because)j(a)f (\(randomized\))f(learning)g(algo-)-91 2264 y(rithm)7 b(can)i(simply)f(call)h Fj(MEMBER)i Fn(on)d(uniform)f(random)i(inputs) -91 2314 y(if)f(it)h(so)g(chooses;)g(thus,)g(we)h(need)g(only)e (consider)g(the)h Fj(MEMBER)-91 2364 y Fn(oracle.)26 b(Also,)15 b(Theorem)g(10)f(is)g(written)f(in)h(terms)g(of)g(e)o (xpected)-91 2413 y(error)n(,)d(b)o(ut)f(it)g(can)h(easily)g(be)g (transformed)f(into)f(the)i Fr(\()p Fq(\017;)c(\016)r Fr(\))j Fn(formu-)-91 2463 y(lation.)-91 2513 y Fg(Pr)o(oof)o(.)j Fn(W)m(e)d(be)o(gin)f(by)g(describing)f(the)h(distrib)o(ution)d Fq(P)714 2519 y Fp(s)731 2513 y Fn(.)13 b(Gi)o(v)o(en)c Fq(s)p Fn(,)-91 2563 y(let)j Fq(t)j Fr(=)g(lg\(3)p Fq(sn)p Fr(\))p Fn(.)k(The)13 b(tar)o(get)f(function)e(is)i(a)h(monotone)e Fq(t)p Fn(-DNF)-91 2613 y(formula)k(in)f(which)h(each)h(possible)f (conjunct)f(of)h Fq(t)g Fn(v)o(ariables)g(is)-91 2662 y(placed)10 b(in)f(the)g(tar)o(get)h Ft(independently)e Fn(with)h(probability)e Fq(p)p Fn(,)j(where)987 42 y Fq(p)15 b Fn(is)h(de\002ned)g(such)f(that)g(an)h(e)o(xample)g(of)g (weight)e Fq(n=)p Fr(2)h Fn(\(ha)o(ving)987 91 y(e)o(xactly)f Fq(n=)p Fr(2)f Fn(1')n(s)f(in)h(it\))g(has)g(probability)e Fr(1)p Fq(=)p Fr(2)i Fn(of)g(being)f(labeled)987 141 y(positi)o(v)o(e.)g(That)e(is,)h Fq(p)f Fn(is)g(the)g(solution)e(to)i (the)g(equation)1307 236 y Fr(\(1)f Fs(\000)g Fq(p)p Fr(\))1431 222 y(\()1447 205 y Fe(n=)p Ff(2)1465 229 y Fe(t)1495 222 y Fr(\))1525 236 y(=)j(1)p Fq(=)p Fr(2)c Fq(:)987 321 y Fn(Note)j(that)g(we)g(ha)o(v)o(e)i(de\002ned)e Fq(P)1461 327 y Fp(s)1490 321 y Fn(so)g(that)g(each)i(term)e(appears)h (in-)987 371 y(dependently)e(with)h(some)h(\002x)o(ed)f(probability)m (,)f(as)i(opposed)f(to)g(the)987 421 y(more)h(common)g(distrib)o(ution) d(on)j(formulas)f(in)g(which)h(the)g(tar)o(get)987 471 y(is)e(random)g(subject)g(to)g(ha)o(ving)f(a)i(\002x)o(ed)g(number)f (of)g(terms.)1037 521 y(T)m(o)e(analyze)h(the)g(learning)e(algorithm)g Fq(A)p Fn(,)j(we)e(want)g(to)g(keep)h(the)987 570 y(conditional)h (distrib)o(ution)e Fq(P)1415 576 y Fp(s)1433 570 y Fn(,)k(gi)o(v)o(en)g (the)g(information)e(gathered)987 620 y(by)g Fq(A)h Fn(so)g(far)n(,)h (as)f(\223clean\224)h(as)g(possible.)i(T)m(o)c(do)h(this,)f(we)h (augment)987 670 y(the)h Fj(MEMBER)j Fn(oracle)d(so)g(that)f(it)g(pro)o (vides)h Ft(mor)n(e)g Fn(information)987 720 y(to)h(the)h(learning)f (algorithm)f(than)i(the)g(standard)f(oracle.)25 b(Lo)o(wer)987 770 y(bounds)13 b(for)h(algorithms)f(using)h(the)g(augmented)g(oracle)h (clearly)987 819 y(imply)9 b(at)i(least)f(the)g(same)i(bound)d(for)h (the)g(standard)g(oracle.)1037 869 y(Speci\002cally)m(,)20 b(we)e(de\002ne)h(the)e(augmented)h Fj(MEMBER)j Fn(or)o(-)987 919 y(acle)e(as)h(follo)o(ws.)36 b(Gi)o(v)o(en)19 b(a)g(query)f(e)o (xample)i Fq(x)p Fn(,)g(with)e(1')n(s)g(in)987 969 y(bit)c(positions)f (inde)o(x)o(ed)j(by)e(some)i(set)g Fq(S)1603 975 y Fp(x)1624 969 y Fn(,)h(let)e(us)g(imagine)g(that)987 1019 y Fj(MEMBER)d Fn(looks)c(at)h(all)g(of)g(the)1480 985 y Fi(\000)1500 1000 y Fh(j)p Fp(S)1530 1004 y Fe(x)1548 1000 y Fh(j)1523 1033 y Fp(t)1558 985 y Fi(\001)1586 1019 y Fn(conjuncts)g(of)f Fq(t)h Fn(v)o(ariables)987 1068 y(in)i Fq(S)1056 1074 y Fp(x)1090 1068 y Fn(in)g(le)o(xicographic)g(order)h(and)g(returns)f (the)h(\002rst)f(such)i(con-)987 1118 y(junct)h(that)h(appears)h(in)e (the)h(tar)o(get)g(function)f(\(if)g Fq(x)h Fn(is)g(positi)o(v)o(e\),) 987 1168 y(or)f(\2230\224)h(if)f Fq(x)g Fn(is)h(ne)o(gati)o(v)o(e.)26 b(In)14 b(other)g(words,)h(for)f(a)h(positi)o(v)o(e)e(e)o(x-)987 1218 y(ample,)h(the)e(oracle)h(returns)f(a)h(witness)f(\(the)g(\002rst) g(one)h(in)f(le)o(xico-)987 1268 y(graphic)f(order\))g(to)f(the)i(fact) f(that)g(the)g(e)o(xample)h(is)f(positi)o(v)o(e.)k(This)987 1318 y(augmented)e(oracle)h(is)f(con)n(v)o(enient)g(because)h(in)f(the) g(conditional)987 1367 y(distrib)o(ution)8 b Fq(P)1216 1373 y Fp(s)1246 1367 y Fn(gi)o(v)o(en)j(some)h(set)g(of)g(oracle)g (queries,)g(each)h(term)987 1417 y(is)c(either)f(kno)o(wn)g(to)h(be)g (present)g(in)g(the)f(tar)o(get)h(formula,)h(is)e(kno)o(wn)987 1467 y(to)j(be)g(absent)h(from)f(the)g(tar)o(get)h(formula,)f(or)g(is)h (still)d(in)i(the)h(tar)o(get)987 1517 y(formula)e(independently)e (with)h(probability)f Fq(p)p Fn(.)1037 1567 y(One)i(way)g(to)f(think)f (of)i(this)f(conditional)f(distrib)o(ution)f Fq(P)1872 1573 y Fp(s)1899 1567 y Fn(is)j(as)987 1616 y(a)h(v)o(ector)g Fq(V)1154 1622 y Fp(s)1182 1616 y Fn(of)1228 1583 y Fi(\000)1247 1598 y Fp(n)1251 1631 y(t)1267 1583 y Fi(\001)1297 1616 y Fn(elements,)g(one)g(for)f(each)i(possible)d(conjunct)987 1666 y(of)i(size)h Fq(t)p Fn(,)g(in)f(which)g(each)i(element)f(of)f (the)g(v)o(ector)h(initially)d(con-)987 1716 y(tains)j(the)g(number)g Fq(p)p Fn(,)h(indicating)d(the)i(probability)e(that)h(the)i(con-)987 1766 y(junct)d(is)g(in)g(the)h(tar)o(get)g(function.)i(When)e(a)g (query)f Fq(x)h Fn(is)f(made,)j(the)987 1816 y(oracle)f(e)o(xamines)g (one)g(by)f(one)g(the)h(entries)f(rele)o(v)o(ant)g(to)g Fq(x)g Fn(\(those)987 1865 y(corresponding)e(to)i(terms)g(that)g(if)f (present)h(in)f(the)h(tar)o(get)g(function)987 1915 y(would)e(make)j Fq(x)f Fn(positi)o(v)o(e\).)j(F)o(or)d(each)h(entry)e(ha)o(ving)g(v)o (alue)h Fq(p)p Fn(,)h(we)987 1965 y(can)h(think)d(of)h(the)h(oracle)h (as)f(\003ipping)e(a)j(coin,)f(replacing)g(the)f(en-)987 2015 y(try)i(by)h(0)g(with)g(probability)d Fr(1)h Fs(\000)g Fq(p)j Fn(and)f(by)g(1)g(with)f(probability)987 2065 y Fq(p)p Fn(.)25 b(The)15 b(oracle)g(announces)f(each)h(result)f(to)g (the)g(learning)f(algo-)987 2115 y(rithm)h(and)g(halts)h(when)f(either) h(a)g(1)f(is)h(observ)o(ed)g(\(meaning)g(the)987 2164 y(e)o(xample)c(is)g(positi)o(v)o(e\))e(or)h(when)g(the)g(number)h(of)f (rele)o(v)o(ant)g(entries)987 2214 y(is)g(e)o(xhausted)h(\(for)e(a)i (ne)o(gati)o(v)o(e)g(e)o(xample\).)1037 2264 y(At)f(an)o(y)h(point)e (in)i(the)f(learning)g(process,)i(by)e(de\002nition)f(of)i(the)987 2314 y(augmented)j Fj(MEMBER)i Fn(oracle,)f(the)f(v)o(ector)f Fq(V)1719 2320 y Fp(s)1751 2314 y Fn(describes)h(e)o(x-)987 2364 y(actly)f(the)g(conditional)e(distrib)o(ution)f Fq(P)1576 2370 y Fp(s)1607 2364 y Fn(gi)o(v)o(en)j(the)g(information) 987 2413 y(observ)o(ed)f(by)f(the)g(learning)g(algorithm)f(so)h(far)n (.)17 b(Speci\002cally)m(,)12 b(en-)987 2463 y(tries)e(in)g Fq(V)1136 2469 y Fp(s)1164 2463 y Fn(set)h(to)f(1)g(correspond)g(to)g (terms)h(kno)o(wn)f(to)g(be)g(present)987 2513 y(in)j(the)h(tar)o(get)f (function,)h(entries)g(set)g(to)f(0)h(correspond)f(to)g(terms)987 2563 y(kno)o(wn)7 b(to)g(be)i(absent)f(from)f(the)h(tar)o(get)g (function,)f(and)h(the)g(remain-)987 2613 y(ing)17 b(entries)h(are)g (each)h(in)e(the)h(tar)o(get)g(function)e(independently)987 2662 y(with)9 b(probability)f Fq(p)p Fn(.)p eop %%Page: 6 6 6 5 bop -91 42 a Fg(Claim)9 b(1)20 b Ft(After)12 b Fq(s)h Ft(queries,)g(at)f(most)f Fq(s)i Ft(of)f(the)f(entries)i(in)e Fq(V)809 48 y Fp(s)839 42 y Ft(ar)n(e)-91 91 y(set)f(to)g(1.)-91 180 y Fg(Pr)o(oof)o(.)76 b Fn(Immediate)32 b(by)e(de\002nition)g(of)g (the)h(augmented)-91 230 y Fj(MEMBER)13 b Fn(oracle.)p 874 225 19 19 v -91 343 a Fg(Claim)c(2)20 b Ft(After)12 b Fq(s)g Ft(queries,)h(with)d(pr)n(obability)f Fr(1)h Fs(\000)g Fq(e)709 328 y Fh(\000)p Fp(s=)p Fo(4)787 343 y Ft(,)i(ther)n(e)-91 393 y(ar)n(e)f(at)f(most)f Fr(2)p Fq(s=p)i Ft(zer)n(os)g(in)e Fq(V)359 399 y Fp(s)377 393 y Ft(.)14 b(\(Call)8 b(this)i(e)o(vent)h Fs(E)t Ft(.\))-91 482 y Fg(Pr)o(oof)o(.)i Fn(In)8 b(the)g(worst)f(case,)k(for)c(each)j (query)d(the)h(oracle)h(continues)-91 532 y(to)g(\003ip)g(coins)g (until)f(a)i(1)g(is)f(produced)g(\(in)g(other)g(words,)g(the)h(oracle) -91 581 y(is)g(not)f(prematurely)h(interrupted)e(by)i(a)g(pre)o (viously-seen)f(1,)i(or)f(by)-91 631 y(the)i(number)g(of)f(rele)o(v)o (ant)h(entries)g(being)g(e)o(xhausted\).)18 b(Thus,)13 b(the)-91 681 y(question)e(of)h(the)g(number)h(of)f(zeros)h(produced)f (is)g(equi)o(v)o(alent)f(to:)-91 731 y(Ho)o(w)f(man)o(y)i(times)f(will) e(we)i(\003ip)g(a)g(coin)f(of)h(bias)f Fq(p)h Fn(before)g(seeing)-91 781 y Fq(s)h Fn(heads?)19 b(In)12 b Fr(2)p Fq(s=p)g Fn(coin)g(\003ips)f (we)i(e)o(xpect)g(to)e(see)i Fr(2)p Fq(s)g Fn(heads.)19 b(By)-91 831 y(Chernof)o(f)9 b(bounds,)g(the)h(actual)g(number)g(of)g (heads)h(is)e(at)h(least)h(half)-91 880 y(this)e(quantity)g(with)g (probability)e(at)k(least)f Fr(1)f Fs(\000)h Fq(e)620 865 y Fh(\000)p Fo(2)p Fp(s=)p Fo(8)714 880 y Fn(.)p 874 875 V -41 954 a(F)o(or)i(a)i(gi)o(v)o(en)e(e)o(xample)i Fq(x)p Fn(,)f(and)g(v)o(ector)g Fq(V)576 960 y Fp(s)594 954 y Fn(,)g(let)g Fq(V)696 960 y Fp(s)714 954 y Fr(\()p Fq(x)p Fr(\))g Fn(denote)-91 1004 y(the)e(probability)e(that)h Fq(x)i Fn(is)f(positi)o(v)o(e)f(gi)o(v)o(en)h(the)h(distrib)o(utio)o(n) d(o)o(v)o(er)-91 1054 y(tar)o(get)15 b(functions)f(de\002ned)h(by)g Fq(V)406 1060 y Fp(s)424 1054 y Fn(.)28 b(Because)16 b Fq(V)639 1060 y Fp(s)673 1054 y Fn(describes)f(the)-91 1104 y(conditional)e(distrib)o(utio)o(n)f Fq(P)343 1110 y Fp(s)376 1104 y Fn(gi)o(v)o(en)i(the)h(queries)g(made)h(so)f(far)n(,) -91 1153 y(the)g(Bayes-optimal)g(prediction)e(for)i(an)h(e)o(xample)g Fq(x)f Fn(is)g(simply)m(,)-91 1203 y(\223If)9 b Fq(V)-12 1209 y Fp(s)6 1203 y Fr(\()p Fq(x)p Fr(\))j Fs(\025)g Fr(1)p Fq(=)p Fr(2)c Fn(predict)h(positi)o(v)o(e,)g(else)h(predict)e (ne)o(gati)o(v)o(e.)m(\224)14 b(W)m(e)-91 1253 y(bound)d(the)h(accurac) o(y)i(of)e(this)f(predictor)g(through)g(the)h(follo)o(wing)-91 1303 y(\002nal)e(claim.)-91 1392 y Fg(Claim)f(3)20 b Ft(F)l(or)8 b Fn(an)o(y)h Ft(vector)g Fq(V)339 1398 y Fp(s)366 1392 y Ft(of)f(size)477 1358 y Fi(\000)497 1373 y Fp(n)500 1406 y(t)517 1358 y Fi(\001)545 1392 y Ft(with)f(at)g(most)h Fq(s)h Ft(entries)-91 1442 y(set)15 b(to)e(1,)j(at)e(most)g Fr(2)p Fq(s=p)h Ft(entries)f(set)h(to)f(0,)i(and)e(the)g(r)n(emaining) -91 1491 y(entries)d(set)g(to)f Fq(p)p Ft(,)h(for)g(a)g(r)o(andom)f(e)o (xample)h Fq(x)p Ft(,)h(we)f(have)g(that)f(with)-91 1541 y(pr)n(obability)f(at)i(least)g Fr(1)f Fs(\000)g Fr(2)p Fq(=)352 1511 y Fs(p)p 386 1511 25 2 v 386 1541 a Fq(n)g Fs(\000)h Fr(2)p Fq(e)504 1526 y Fh(\000)p Fp(c)545 1514 y Ff(2)563 1541 y Ft(,)h(the)g(quantity)d Fq(V)819 1547 y Fp(s)837 1541 y Fr(\()p Fq(x)p Fr(\))-91 1591 y Ft(lies)h(within)e Fr(1)p Fq(=)p Fr(2)h Fs(\006)g Fr(\()p Fq(c)g Fr(+)h(1\))p Fq(t=)362 1561 y Fs(p)p 396 1561 V 396 1591 a Fq(n)p Ft(.)-91 1680 y Fg(Remark.)89 b Fn(Notice)21 b(that)f(by)h(plugging)d Fq(c)31 b Fr(=)711 1645 y Fi(p)p 753 1645 141 2 v 35 x Fr(\(ln)7 b Fq(n)p Fr(\))p Fq(=)p Fr(2)-91 1730 y Fn(into)22 b(Claim)h(3)g(\(and)g(using)g(the)g(de\002nition)f(of)h Fq(t)p Fn(\))g(we)h(ha)o(v)o(e)-91 1780 y(that)14 b(with)g(probability) e Fr(1)h Fs(\000)g Fr(4)p Fq(=)393 1750 y Fs(p)p 427 1750 25 2 v 427 1780 a Fq(n)p Fn(,)k Fq(V)503 1786 y Fp(s)521 1780 y Fr(\()p Fq(x)p Fr(\))e Fn(lies)g(within)e Fr(1)p Fq(=)p Fr(2)f Fs(\006)-91 1835 y Fq(O)q Fr(\(log)11 1816 y Fo(3)p Fp(=)p Fo(2)64 1835 y Fr(\()p Fq(sn)p Fr(\))p Fq(=)161 1805 y Fs(p)p 196 1805 V 30 x Fq(n)o Fr(\))p Fn(.)45 b(This)21 b(immediately)f(yields)g(a)i(weaker)-91 1884 y(v)o(ersion)14 b(Theorem)i(10)e(in)g(which)g Fr(log)o(\()p Fq(sn)p Fr(\))p Fq(=)579 1854 y Fs(p)p 614 1854 V 30 x Fq(n)h Fn(is)f(replaced)i(by)-91 1939 y Fr(log)-38 1921 y Fo(3)p Fp(=)p Fo(2)15 1939 y Fr(\()p Fq(sn)p Fr(\))p Fq(=)112 1909 y Fs(p)p 147 1909 V 30 x Fq(n)p Fn(.)f(After)c(pro)o (ving)f(Claim)g(3)h(we)h(gi)o(v)o(e)f(a)h(more)f(re-)-91 1989 y(\002ned)f(ar)o(gument)h(producing)d(the)i(stronger)g(bound.)-91 2063 y Fg(Pr)o(oof)e(of)g(Claim)f(3.)24 b Fn(Let)9 b(us)f(say)h(that)e (an)i(entry)e(of)h Fq(V)681 2069 y Fp(s)707 2063 y Fn(is)g(\223rele)o (v)o(ant)-91 2113 y(to\224)g(an)h(e)o(xample)h Fq(x)e Fn(if)g Fq(x)h Fn(satis\002es)g(the)f(conjunct)g(corresponding)f(to)-91 2162 y(that)j(entry;)f(that)h(is,)h(the)f(entry)g(is)g(rele)o(v)o(ant)g (to)g Fq(x)g Fn(if)g(the)h(conjunct')n(s)-91 2212 y(presence)g(in)f (the)g(tar)o(get)g(function)f(implies)h Fq(f)t Fr(\()p Fq(x)p Fr(\))i(=)g(1)p Fn(.)-41 2262 y(W)m(e)e(be)o(gin)g(by)g(sho)o (wing)f(that)h(for)g(a)g(random)h(e)o(xample)g Fq(x)p Fn(,)f(with)-91 2316 y(probability)e(at)j(least)g Fr(1)f Fs(\000)g Fr(2)p Fq(=)345 2286 y Fs(p)p 379 2286 V 379 2316 a Fq(n)g Fs(\000)g Fr(2)p Fq(e)496 2301 y Fh(\000)p Fp(c)537 2289 y Ff(2)555 2316 y Fn(,)i(the)f(follo)o(wing)d(three)-91 2366 y(e)o(v)o(ents)j(occur)n(.)-60 2447 y(1.)21 b(None)10 b(of)g(the)g(1-entries)g(in)f Fq(V)420 2453 y Fp(s)449 2447 y Fn(are)i(rele)o(v)o(ant)f(to)g Fq(x)p Fn(.)-8 2513 y(There)17 b(are)f(at)g(most)g Fq(s)g Fn(1-entries,)h(and)f(for)g (each)h(one,)g(the)-8 2563 y(probability)c(it)i(is)g(rele)o(v)o(ant)g (to)g Fq(x)h Fn(is)f Fr(2)571 2548 y Fh(\000)p Fp(t)611 2563 y Fn(.)30 b(Since)16 b Fq(s)p Fr(2)799 2548 y Fh(\000)p Fp(t)861 2563 y Fr(=)-8 2613 y(1)p Fq(=)p Fr(\(3)p Fq(n)p Fr(\))f Fn(by)g(the)g(de\002nition)e(of)i Fq(t)p Fn(,)i(this)e(e)o(v)o (ent)h(occurs)f(with)-8 2663 y(probability)7 b(at)k(least)f Fr(1)f Fs(\000)h Fr(1)p Fq(=)p Fr(\(3)p Fq(n)p Fr(\))p Fn(.)1018 42 y(2.)21 b(At)12 b(most)g Fr(\(2)p Fq(s)1273 12 y Fs(p)p 1308 12 V 30 x Fq(n=p)p Fr(\)2)1412 26 y Fh(\000)p Fp(t)1465 42 y Fn(of)g(the)g(0-entries)g(in)g Fq(V)1802 48 y Fp(s)1832 42 y Fn(are)h(rele-)1070 91 y(v)o(ant)d(to)f Fq(x)p Fn(.)1070 156 y(The)16 b(e)o(xpected)g(number)f (of)g(0-entries)g(rele)o(v)o(ant)g(to)f Fq(x)h Fn(is)g(at)1070 206 y(most)e Fr(\(2)p Fq(s=p)p Fr(\)2)1299 190 y Fh(\000)p Fp(t)1339 206 y Fn(.)22 b(By)13 b(Marko)o(v')n(s)f(inequality)m(,)h (the)g(chance)1070 255 y(that)d(it)f(is)h(more)h(than)1392 225 y Fs(p)p 1426 225 V 1426 255 a Fq(n)g Fn(times)f(this)f(is)h(at)h (most)f Fr(1)p Fq(=)1844 225 y Fs(p)p 1878 225 V 1878 255 a Fq(n)p Fn(.)1018 334 y(3.)21 b(The)d(test)g(e)o(xample)h Fq(x)f Fn(lies)f(in)h Fq(X)1588 340 y Fp(k)1626 334 y Fn(for)g Fq(k)h Fn(within)d Fq(n=)p Fr(2)e Fs(\006)1070 384 y Fq(c)1088 349 y Fi(p)p 1129 349 67 2 v 1129 384 a Fq(n=)p Fr(2)p Fn(.)1070 449 y(By)9 b(Hoef)o(fding)g(bounds,)h(this)f (e)o(v)o(ent)h(occurs)g(with)f(probabil-)1070 503 y(ity)g(at)i(least)f Fr(1)f Fs(\000)g Fr(2)p Fq(e)1362 488 y Fh(\000)p Fp(c)1403 475 y Ff(2)1422 503 y Fn(.)987 578 y(The)i(probability)c(that)j(all)g (three)g(e)o(v)o(ents)h(occur)g(is)f(at)g(least)1097 677 y Fr(1)f Fs(\000)1186 649 y Fr(1)p 1174 667 46 2 v 1174 705 a(3)p Fq(n)1233 677 y Fs(\000)1299 649 y Fr(1)p 1280 667 60 2 v 1280 676 a Fs(p)p 1314 676 25 2 v 1314 706 a Fq(n)1354 677 y Fs(\000)g Fr(2)p Fq(e)1435 660 y Fh(\000)p Fp(c)1476 647 y Ff(2)1506 677 y Fq(>)j Fr(1)d Fs(\000)1645 649 y Fr(2)p 1626 667 60 2 v 1626 676 a Fs(p)p 1661 676 25 2 v 30 x Fq(n)1700 677 y Fs(\000)g Fr(2)p Fq(e)1781 660 y Fh(\000)p Fp(c)1822 647 y Ff(2)1850 677 y Fq(:)1037 779 y Fn(Gi)o(v)o(en)14 b(that)g(the)g(abo)o(v)o(e)h (three)f(e)o(v)o(ents)h(occur)n(,)h(we)f(no)o(w)f(sho)o(w)987 829 y(that)f Fq(V)1087 835 y Fp(s)1105 829 y Fr(\()p Fq(x)p Fr(\))g Fn(lies)h(in)f(the)g(desired)h(range.)23 b(F)o(or)14 b(the)f(lo)o(wer)g(bound,)987 879 y Fq(V)1011 885 y Fp(s)1029 879 y Fr(\()p Fq(x)p Fr(\))f Fn(is)h(minimized)f(when)g Fq(x)g Fn(has)h(as)g(fe)o(w)g(1')n(s)f(as)h(possible)e(and)987 929 y(when)16 b(as)g(man)o(y)h(of)e(the)h(0-entries)f(in)g Fq(V)1601 935 y Fp(s)1635 929 y Fn(are)h(rele)o(v)o(ant)g(to)f Fq(x)h Fn(as)987 979 y(possible.)c(Thus)f Fq(V)1264 985 y Fp(s)1282 979 y Fr(\()p Fq(x)p Fr(\))f Fn(is)g(at)g(least)1055 1104 y Fq(V)1079 1110 y Fp(s)1097 1104 y Fr(\()p Fq(x)p Fr(\))42 b Fs(\025)f Fr(1)9 b Fs(\000)h Fr(\(1)f Fs(\000)h Fq(p)p Fr(\))1465 1026 y Fi(h)1484 1072 y Fr(\()1500 1055 y Fe(n=)p Ff(2)p Fd(\000)p Fe(c)1582 1035 y Fh(p)p 1611 1035 48 2 v 1611 1055 a Fe(n=)p Ff(2)1574 1080 y Fe(t)1659 1072 y Fr(\))1675 1069 y Fh(\000)1706 1055 y Ff(2)p Fe(s)1734 1040 y Fd(p)p 1757 1040 19 2 v 15 x Fe(n)p 1706 1063 70 2 v 1719 1083 a(p)p Ff(2)1748 1077 y Fe(t)1780 1026 y Fi(i)1195 1191 y Fs(\025)41 b Fr(1)9 b Fs(\000)1340 1133 y Fi(\024)1362 1191 y Fr(\(1)g Fs(\000)g Fq(p)p Fr(\))1486 1176 y(\()1503 1159 y Fe(n=)p Ff(2)p Fd(\000)p Fe(c)1585 1139 y Fh(p)p 1614 1139 48 2 v 1614 1159 a Fe(n=)p Ff(2)1576 1184 y Fe(t)1661 1176 y Fr(\))1679 1133 y Fi(\025)1708 1145 y(h)1728 1191 y Fq(e)1747 1174 y Fo(3)p Fp(s)1780 1153 y Fh(p)p 1807 1153 21 2 v 21 x Fp(n)o(=)p Fo(2)1861 1161 y Fe(t)1877 1145 y Fi(i)1195 1307 y Fr(=)41 b(1)9 b Fs(\000)1340 1249 y Fi(\024)1362 1307 y Fr(\(1)g Fs(\000)g Fq(p)p Fr(\))1486 1292 y(\()1503 1275 y Fe(n=)p Ff(2)p Fd(\000)p Fe(c)1585 1255 y Fh(p)p 1614 1255 48 2 v 1614 1275 a Fe(n=)p Ff(2)1576 1300 y Fe(t)1661 1292 y Fr(\))1679 1249 y Fi(\025)1708 1261 y(h)1728 1307 y Fq(e)1747 1290 y Fo(1)p Fp(=)1781 1269 y Fh(p)p 1808 1269 21 2 v 21 x Fp(n)1831 1261 y Fi(i)1310 1392 y Fn(\(de\002nition)f(of)i Fq(t)p Fn(\))1195 1476 y Fr(=)41 b(1)9 b Fs(\000)1340 1417 y Fi(\024)1362 1476 y Fr(2)1383 1458 y Fh(\000)1409 1461 y Fr(\()1425 1443 y Fe(n=)p Ff(2)p Fd(\000)p Fe(c)1507 1423 y Fh(p)p 1536 1423 48 2 v 1536 1443 a Fe(n=)p Ff(2)1498 1469 y Fe(t)1583 1461 y Fr(\))1599 1458 y Fp(=)1616 1461 y Fr(\()1633 1444 y Fe(n=)p Ff(2)1651 1468 y Fe(t)1680 1461 y Fr(\))1698 1417 y Fi(\025)1727 1430 y(h)1747 1476 y Fq(e)1766 1459 y Fo(1)p Fp(=)1800 1438 y Fh(p)p 1827 1438 21 2 v 21 x Fp(n)1850 1430 y Fi(i)1885 1476 y Fq(:)1310 1560 y Fn(\(de\002nition)f(of)i Fq(p)p Fn(\))987 1641 y(W)m(e)h(bound)e(the)h (e)o(xponent)g(for)g(suf)o(\002ciently)f(lar)o(ge)h Fq(n)p Fn(:)1089 1703 y Fi(\000)1108 1718 y Fp(n=)p Fo(2)p Fh(\000)p Fp(c)1204 1689 y Fs(p)p 1237 1689 55 2 v 1237 1718 a Fp(n=)p Fo(2)1193 1752 y Fp(t)1291 1703 y Fi(\001)p 1089 1759 222 2 v 1153 1770 a(\000)1172 1785 y Fp(n=)p Fo(2)1193 1818 y Fp(t)1226 1770 y Fi(\001)1357 1768 y Fs(\025)1431 1697 y Fi( )1468 1739 y Fq(n=)p Fr(2)f Fs(\000)h Fq(c)1604 1704 y Fi(p)p 1645 1704 67 2 v 1645 1739 a Fq(n=)p Fr(2)f Fs(\000)g Fq(t)p 1468 1759 309 2 v 1590 1797 a(n=)p Fr(2)1782 1697 y Fi(!)1815 1706 y Fp(t)1357 1917 y Fs(\025)1431 1846 y Fi( )1468 1888 y Fq(n=)p Fr(2)g Fs(\000)h Fr(\()p Fq(c)f Fr(+)g(1\))1707 1853 y Fi(p)p 1749 1853 67 2 v 35 x Fq(n=)p Fr(2)p 1468 1907 347 2 v 1609 1945 a Fq(n=)p Fr(2)1820 1846 y Fi(!)1853 1855 y Fp(t)1357 2066 y Fr(=)1431 1995 y Fi( )1463 2066 y Fr(1)g Fs(\000)1540 2003 y(p)p 1574 2003 21 2 v 1574 2038 a Fr(2\()p Fq(c)h Fr(+)f(1\))p 1540 2056 178 2 v 1599 2064 a Fs(p)p 1633 2064 25 2 v 1633 2094 a Fq(n)1722 1995 y Fi(!)1755 2003 y Fp(t)1357 2200 y Fs(\025)42 b Fr(1)8 b Fs(\000)1507 2137 y(p)p 1542 2137 21 2 v 35 x Fr(2)o(\()p Fq(c)i Fr(+)f(1\))p Fq(t)p 1507 2190 193 2 v 1573 2199 a Fs(p)p 1608 2199 25 2 v 30 x Fq(n)1713 2200 y(:)987 2305 y Fn(Thus)h(our)g(lo)o(wer)g (bound)f(on)h Fq(V)1440 2311 y Fp(s)1458 2305 y Fr(\()p Fq(x)p Fr(\))g Fn(is)1060 2399 y Fq(V)1084 2405 y Fp(s)1102 2399 y Fr(\()p Fq(x)p Fr(\))42 b Fs(\025)f Fr(1)9 b Fs(\000)1345 2353 y Fi(h)1364 2399 y Fr(2)1385 2382 y Fh(\000)p Fo(\(1)p Fh(\000)1467 2358 y(p)p 1494 2358 17 2 v 24 x Fo(2)o(\()p Fp(c)p Fo(+1\))p Fp(t=)1623 2361 y Fh(p)p 1650 2361 21 2 v 21 x Fp(n)p Fo(\))1686 2353 y Fi(i)d(h)1732 2399 y Fq(e)1751 2382 y Fo(1)p Fp(=)1785 2361 y Fh(p)p 1812 2361 V 21 x Fp(n)1834 2353 y Fi(i)1200 2503 y Fr(=)41 b(1)9 b Fs(\000)1350 2475 y Fr(1)p 1350 2493 V 1350 2531 a(2)1382 2444 y Fi(\024)1404 2503 y Fq(e)1428 2449 y Fd(p)p 1451 2449 15 2 v 17 x Ff(2)d(ln\(2\)\()p Fe(c)p Ff(+1\))h Fe(t)p Ff(+1)p 1429 2475 227 2 v 1521 2479 a Fd(p)p 1544 2479 19 2 v 15 x Fe(n)1662 2444 y Fi(\025)1200 2631 y Fs(\025)41 b Fr(1)9 b Fs(\000)1350 2603 y Fr(1)p 1350 2622 21 2 v 1350 2660 a(2)1382 2560 y Fi(")1407 2631 y Fr(1)g(+)1483 2603 y(2)1504 2569 y Fs(p)p 1539 2569 V 34 x Fr(2)d(ln\(2\)\()p Fq(c)j Fr(+)h(1\))p Fq(t)f Fr(+)g(1)p 1483 2622 379 2 v 1643 2630 a Fs(p)p 1677 2630 25 2 v 1677 2660 a Fq(n)1867 2560 y Fi(#)p eop %%Page: 7 7 7 6 bop 121 66 a Fr(=)200 38 y(1)p 200 56 21 2 v 200 94 a(2)235 66 y Fs(\000)282 3 y(p)p 316 3 V 316 38 a Fr(2)7 b(ln\(2\)\()p Fq(c)i Fr(+)g(1\))p Fq(t)h Fr(+)f(1)p Fq(=)p Fr(2)p 282 56 400 2 v 452 64 a Fs(p)p 486 64 25 2 v 486 94 a Fq(n)121 180 y Fs(\025)200 152 y Fr(1)p 200 171 21 2 v 200 209 a(2)235 180 y Fs(\000)282 152 y Fr(\()p Fq(c)g Fr(+)g(1\))p Fq(t)p 282 171 137 2 v 320 179 a Fs(p)p 355 179 25 2 v 30 x Fq(n)433 180 y(:)-41 290 y Fn(W)m(e)f(maximize)i Fq(V)218 296 y Fp(s)236 290 y Fr(\()p Fq(x)p Fr(\))e Fn(when)h Fq(x)f Fn(contains)g(as)h(man)o(y)g (1')n(s)g(as)g(pos-)-91 340 y(sible)f(and)i(as)f(fe)o(w)h(0-entries)e (as)i(possible.)i(Thus)d Fq(V)653 346 y Fp(s)671 340 y Fr(\()p Fq(x)p Fr(\))g Fn(is)g(at)g(most)80 446 y Fq(V)104 452 y Fp(s)122 446 y Fr(\()p Fq(x)p Fr(\))42 b Fs(\024)g Fr(1)9 b Fs(\000)g Fr(\(1)g Fs(\000)h Fq(p)p Fr(\))490 431 y(\()506 413 y Fe(n=)p Ff(2+)p Fe(c)587 393 y Fh(p)p 616 393 48 2 v 616 413 a Fe(n=)p Ff(2)579 439 y Fe(t)664 431 y Fr(\))220 528 y(=)42 b(1)9 b Fs(\000)g Fr(2)386 510 y Fh(\000)412 513 y Fr(\()428 496 y Fe(n=)p Ff(2+)p Fe(c)509 476 y Fh(p)p 538 476 V 538 496 a Fe(n=)p Ff(2)501 521 y Fe(t)586 513 y Fr(\))602 510 y Fp(=)619 513 y Fr(\()635 497 y Fe(n=)p Ff(2)653 520 y Fe(t)683 513 y Fr(\))710 528 y Fq(:)-91 614 y Fn(W)m(e)h(bound)g(the)g(e)o(xponent)g(for)f(suf)o (\002ciently)h(lar)o(ge)g Fq(n)p Fn(:)53 681 y Fi(\000)72 695 y Fp(n=)p Fo(2+)p Fp(c)167 667 y Fs(p)p 201 667 55 2 v 201 695 a Fp(n=)p Fo(2)157 729 y Fp(t)255 681 y Fi(\001)p 53 736 222 2 v 117 748 a(\000)136 763 y Fp(n=)p Fo(2)157 795 y Fp(t)190 748 y Fi(\001)320 746 y Fs(\024)394 675 y Fi( )432 717 y Fq(n=)p Fr(2)f(+)g Fq(c)567 681 y Fi(p)p 608 681 67 2 v 608 717 a Fq(n=)p Fr(2)p 432 736 244 2 v 487 774 a Fq(n=)p Fr(2)g Fs(\000)g Fq(t)680 675 y Fi(!)713 683 y Fp(t)320 894 y Fr(=)394 823 y Fi( )427 894 y Fr(1)g(+)503 865 y Fq(c)521 830 y Fi(p)p 563 830 67 2 v 35 x Fq(n=)p Fr(2)f(+)i Fq(t)p 503 885 192 2 v 533 923 a(n=)p Fr(2)f Fs(\000)g Fq(t)700 823 y Fi(!)733 832 y Fp(t)320 1043 y Fs(\024)394 972 y Fi( )427 1043 y Fr(1)g(+)503 981 y Fs(p)p 538 981 21 2 v 34 x Fr(2\()p Fq(c)g Fr(+)h(1\))p 503 1033 178 2 v 562 1042 a Fs(p)p 597 1042 25 2 v 30 x Fq(n)685 972 y Fi(!)718 981 y Fp(t)320 1177 y Fs(\024)42 b Fr(1)9 b(+)470 1149 y(2)491 1115 y Fs(p)p 526 1115 21 2 v 34 x Fr(2\()p Fq(c)g Fr(+)g(1\))p Fq(t)p 470 1168 213 2 v 547 1176 a Fs(p)p 582 1176 25 2 v 30 x Fq(n)698 1177 y(:)-91 1287 y Fn(Thus)h(our)g(upper)g(bound)f(on)h Fq(V)363 1293 y Fp(s)381 1287 y Fr(\()p Fq(x)p Fr(\))g Fn(is)18 1394 y Fq(V)42 1400 y Fp(s)60 1394 y Fr(\()p Fq(x)p Fr(\))41 b Fs(\024)h Fr(1)9 b Fs(\000)g Fr(2)323 1373 y Fh(\000)p Fo(\(1+)409 1358 y Ff(2)423 1340 y Fd(p)p 446 1340 15 2 v 18 x Ff(2\()p Fe(c)p Ff(+1\))p Fe(t)p 409 1366 135 2 v 456 1370 a Fd(p)p 478 1370 19 2 v 478 1385 a Fe(n)548 1373 y Fo(\))157 1478 y Fr(=)42 b(1)9 b Fs(\000)307 1450 y Fr(1)p 307 1468 21 2 v 307 1506 a(2)333 1478 y Fq(e)352 1456 y Fh(\000)383 1441 y Ff(2)397 1424 y Fd(p)p 420 1424 15 2 v 17 x Ff(2)d(ln)o(\(2\)\()p Fe(c)p Ff(+1\))p Fe(t)p 383 1450 200 2 v 463 1454 a Fd(p)p 486 1454 19 2 v 15 x Fe(n)157 1595 y Fs(\024)42 b Fr(1)9 b Fs(\000)307 1567 y Fr(1)p 307 1586 21 2 v 307 1624 a(2)340 1524 y Fi(")364 1595 y Fr(1)g Fs(\000)441 1567 y Fr(2)462 1533 y Fs(p)p 496 1533 V 496 1567 a Fr(2)e(ln)o(\(2\)\()p Fq(c)j Fr(+)f(1\))p Fq(t)p 441 1586 308 2 v 565 1594 a Fs(p)p 599 1594 25 2 v 599 1624 a Fq(n)753 1524 y Fi(#)157 1723 y Fs(\024)236 1695 y Fr(1)p 236 1713 21 2 v 236 1752 a(2)271 1723 y(+)317 1695 y(\()p Fq(c)h Fr(+)f(1\))p Fq(t)p 317 1713 137 2 v 356 1722 a Fs(p)p 391 1722 25 2 v 30 x Fq(n)468 1723 y(:)p 874 1820 19 19 v -41 1898 a Fn(Gi)o(v)o(en)e(the)h(abo)o(v)o(e)h(three)f(claims,)h(we)g(no)o(w)e (complete)i(the)e(proof)-91 1948 y(of)15 b(Theorem)i(10.)30 b(Claim)15 b(2')n(s)g(e)o(v)o(ent)i Fs(E)i Fn(fails)c(with)g (probability)-91 1997 y Fq(e)-72 1982 y Fh(\000)p Fp(s=)p Fo(4)5 1997 y Fn(.)f(Gi)o(v)o(en)d Fs(E)t Fn(,)f(we)i(would)d(like)g (to)h(kno)o(w)g(the)g(probability)e(that)-91 2047 y(the)j (Bayes-optimal)f(prediction)g(is)h(correct)g(on)g(a)h(random)f(e)o (xam-)-91 2097 y(ple.)26 b(De\002ne)16 b Fq(P)149 2103 y Fp(c)180 2097 y Fn(for)e Fr(1)20 b Fs(\024)g Fq(c)f Fs(\024)425 2067 y(p)p 460 2067 25 2 v 30 x Fq(n)c Fn(as)g(the)g (probability)d(for)i(a)-91 2147 y(random)d(e)o(xample)h Fq(x)f Fn(that)g Fs(j)p Fq(V)343 2153 y Fp(s)360 2147 y Fr(\()p Fq(x)p Fr(\))f Fs(\000)g Fr(1)p Fq(=)p Fr(2)p Fs(j)i(\024)i Fr(\()p Fq(c)c Fr(+)g(1\))p Fq(t=)760 2117 y Fs(p)p 794 2117 V 794 2147 a Fq(n)p Fn(.)16 b(By)-91 2202 y(Claim)10 b(3,)i(we)f(kno)o(w)f(that)h Fr(1)e Fs(\000)h Fr(2)p Fq(=)413 2172 y Fs(p)p 447 2172 V 447 2202 a Fq(n)g Fs(\000)g Fr(2)p Fq(e)564 2187 y Fh(\000)p Fp(c)605 2175 y Ff(2)636 2202 y Fs(\024)j Fq(P)708 2208 y Fp(c)737 2202 y Fs(\024)h Fr(1)p Fn(.)h(The)-91 2252 y(probability)9 b(that)j(the)g(Bayes-optimal)g(prediction)f(is)h(correct)h(for)-91 2302 y(a)e(random)f(e)o(xample,)i(then,)e(is)g(at)g(most)21 2411 y Fq(P)48 2417 y Fo(1)74 2353 y Fi(\022)109 2383 y Fr(1)p 109 2402 21 2 v 109 2440 a(2)144 2411 y(+)202 2383 y(2)p Fq(t)p 191 2402 60 2 v 191 2410 a Fs(p)p 225 2410 25 2 v 225 2440 a Fq(n)255 2353 y Fi(\023)63 2528 y Fr(+)42 b(\()p Fq(P)180 2534 y Fo(2)207 2528 y Fs(\000)10 b Fq(P)276 2534 y Fo(1)294 2528 y Fr(\))317 2469 y Fi(\022)353 2500 y Fr(1)p 353 2518 21 2 v 353 2556 a(2)388 2528 y(+)446 2500 y(3)p Fq(t)p 434 2518 60 2 v 434 2526 a Fs(p)p 469 2526 25 2 v 30 x Fq(n)499 2469 y Fi(\023)63 2644 y Fr(+)42 b(\()p Fq(P)180 2650 y Fo(3)207 2644 y Fs(\000)10 b Fq(P)276 2650 y Fo(2)294 2644 y Fr(\))317 2585 y Fi(\022)353 2616 y Fr(1)p 353 2634 21 2 v 353 2672 a(2)388 2644 y(+)446 2616 y(4)p Fq(t)p 434 2634 60 2 v 434 2643 a Fs(p)p 469 2643 25 2 v 29 x Fq(n)499 2585 y Fi(\023)1141 42 y Fr(+)42 b Fs(\001)7 b(\001)g(\001)1141 123 y Fr(+)42 b(\()p Fq(P)1258 111 y Fh(p)p 1285 111 21 2 v 22 x Fp(n)1317 123 y Fs(\000)9 b Fq(P)1385 111 y Fh(p)p 1412 111 V 22 x Fp(n)p Fh(\000)p Fo(1)1477 123 y Fr(\))1500 64 y Fi(\022)1536 95 y Fr(1)p 1536 113 V 1536 151 a(2)1571 123 y(+)1617 95 y(\()1633 65 y Fs(p)p 1668 65 25 2 v 30 x Fq(n)g Fr(+)h(1\))p Fq(t)p 1617 113 179 2 v 1677 122 a Fs(p)p 1711 122 25 2 v 1711 152 a Fq(n)1801 64 y Fi(\023)1847 123 y Fq(:)987 237 y Fn(By)g(telescoping)f(this)h(series,)h(we)g(get)f(a)h(bound)e(of)1133 375 y Fq(P)1160 363 y Fh(p)p 1187 363 21 2 v 21 x Fp(n)1216 316 y Fi(\022)1252 347 y Fr(1)p 1252 365 V 1252 403 a(2)1287 375 y(+)1333 347 y(\()1349 317 y Fs(p)p 1384 317 25 2 v 30 x Fq(n)g Fr(+)g(1\))p Fq(t)p 1333 365 179 2 v 1392 373 a Fs(p)p 1427 373 25 2 v 30 x Fq(n)1516 316 y Fi(\023)1556 375 y Fs(\000)1598 299 y Fh(p)p 1625 299 21 2 v 21 x Fp(n)o Fh(\000)p Fo(1)1613 335 y Fi(X)1614 423 y Fp(c)p Fo(=1)1695 375 y Fq(P)1722 381 y Fp(c)1766 347 y Fq(t)p 1743 365 60 2 v 1743 373 a Fs(p)p 1778 373 25 2 v 30 x Fq(n)1174 499 y Fs(\024)1253 471 y Fr(1)p 1253 489 21 2 v 1253 527 a(2)1288 499 y(+)1357 471 y Fq(t)p 1334 489 60 2 v 1334 497 a Fs(p)p 1369 497 25 2 v 30 x Fq(n)1406 465 y Fi(\000\000)1444 467 y Fs(p)p 1478 467 V 1478 499 a Fq(n)h Fr(+)f(1)1575 465 y Fi(\001)1283 639 y Fs(\000)1322 563 y Fh(p)p 1349 563 21 2 v 21 x Fp(n)p Fh(\000)p Fo(1)1337 600 y Fi(X)1339 687 y Fp(c)p Fo(=1)1419 580 y Fi(\022)1450 639 y Fr(1)g Fs(\000)1546 611 y Fr(2)p 1526 629 60 2 v 1526 638 a Fs(p)p 1561 638 25 2 v 30 x Fq(n)1600 639 y Fs(\000)h Fr(2)p Fq(e)1682 622 y Fh(\000)p Fp(c)1723 609 y Ff(2)1741 580 y Fi(\023)1771 556 y(1)1771 630 y(A)1174 775 y Fs(\024)1253 747 y Fr(1)p 1253 765 21 2 v 1253 803 a(2)1288 775 y(+)1357 747 y Fq(t)p 1334 765 60 2 v 1334 774 a Fs(p)p 1369 774 25 2 v 29 x Fq(n)1406 741 y Fi(\000\000)1444 743 y Fs(p)p 1478 743 V 1478 775 a Fq(n)g Fr(+)f(1)1575 741 y Fi(\001)1603 775 y Fs(\000)1645 741 y Fi(\000)1664 743 y Fs(p)p 1698 743 V 1698 775 a Fq(n)g Fs(\000)h Fr(1)1795 741 y Fi(\001)1283 903 y Fr(+)1320 875 y(2\()1357 845 y Fs(p)p 1392 845 V 30 x Fq(n)f Fs(\000)g Fr(1\))p 1320 893 185 2 v 1382 901 a Fs(p)p 1417 901 25 2 v 30 x Fq(n)1518 903 y Fr(+)h(2)1601 851 y Fh(1)1588 863 y Fi(X)1589 951 y Fp(c)p Fo(=1)1655 903 y Fq(e)1674 885 y Fh(\000)p Fo(2)p Fp(c)1733 832 y Fi(!)1174 1034 y Fr(=)1253 1006 y(1)p 1253 1024 21 2 v 1253 1062 a(2)1288 1034 y(+)1346 1006 y(4)p Fq(t)p 1334 1024 60 2 v 1334 1032 a Fs(p)p 1369 1032 25 2 v 30 x Fq(n)1408 1034 y Fs(\000)1455 1006 y Fr(2)p Fq(t)p 1455 1024 36 2 v 1460 1062 a(n)1505 1034 y Fr(+)1563 1006 y(2)p Fq(t)p 1551 1024 60 2 v 1551 1032 a Fs(p)p 1586 1032 25 2 v 30 x Fq(n)1625 1034 y Fs(\001)1686 1006 y Fq(e)1705 991 y Fh(\000)p Fo(2)p 1650 1024 136 2 v 1650 1062 a Fr(1)f Fs(\000)h Fq(e)1741 1050 y Fh(\000)p Fo(2)1174 1149 y Fr(=)1253 1121 y(1)p 1253 1140 21 2 v 1253 1178 a(2)1288 1149 y(+)f Fq(O)1369 1091 y Fi(\022)1427 1121 y Fq(t)p 1405 1140 60 2 v 1405 1148 a Fs(p)p 1439 1148 25 2 v 1439 1178 a Fq(n)1469 1091 y Fi(\023)1507 1149 y Fq(:)987 1266 y Fn(Thus)18 b(the)h(best)f(a)h(predictor)e(can)i(do)f(is)g(to)g (achie)o(v)o(e)i(a)f Fr(1)p Fq(=)p Fr(2)14 b(+)987 1316 y Fq(O)q Fr(\()p Fq(t=)1072 1286 y Fs(p)p 1106 1286 V 1106 1316 a Fq(n)p Fr(\))g Fn(probability)d(of)j(agreeing)g(with)e(the) i(tar)o(get)g(function,)987 1365 y(gi)o(v)o(en)9 b(that)f Fs(E)13 b Fn(occurs.)h(Since)9 b Fs(E)k Fn(fails)8 b(with)g Fq(o)p Fr(\()p Fq(t=)1696 1336 y Fs(p)p 1731 1336 V 29 x Fq(n)p Fr(\))h Fn(probability)m(,)987 1415 y(and)h Fq(t)i Fr(=)g Fq(O)q Fr(\(log)6 b Fq(sn)p Fr(\))p Fn(,)11 b(we)g(ha)o(v)o(e)g(the)g(theorem.)p 1953 1410 19 19 v 987 1557 a Fu(5.)i(Conclusions)1037 1666 y Fn(This)e(paper)g(closes)h (to)f(within)e(an)j Fq(O)q Fr(\(log)6 b Fq(n)p Fr(\))12 b Fn(factor)e(the)h(ques-)987 1716 y(tion)j(of)g(ho)o(w)h(well)f (algorithms)g(can)i(learn)f(the)f(class)i(of)f(mono-)987 1766 y(tone)f(Boolean)g(functions)f(on)h(the)g(uniform)f(distrib)o (ution,)g(gi)o(v)o(en)987 1815 y(a)19 b(polynomial)e(number)h(of)h (accesses)i(to)d(the)g(tar)o(get)h(function.)987 1865 y(It)14 b(is)h(natural)f(to)g(suppose)h(that)f(one)h(might)f(guarantee) h(an)h(error)987 1915 y Fr(1)p Fq(=)p Fr(2)5 b Fs(\000)g Fr(\012\(\(log)i Fq(n)p Fr(\))p Fq(=)1277 1885 y Fs(p)p 1312 1885 25 2 v 30 x Fq(n)o Fr(\))j Fn(using)e(a)i(more)g (sophisticated)e(algorithm)987 1965 y(than)16 b(that)g(of)h(Theorem)g (8.)33 b(In)16 b(particular)n(,)i(the)f(follo)o(wing)d(ap-)987 2015 y(proach)9 b(appears)g(promising:)h(First,)f(order)f(the)g(v)o (ariables)h(by)f(their)987 2065 y(observ)o(ed)19 b(indi)o(vidual)d (correlations)h(with)h(a)h(suf)o(\002ciently)e(lar)o(ge)987 2114 y(sample)12 b(of)g(data.)17 b(Then,)c(look)e(at)h(the)f Fq(n)h Fn(hypotheses)f Fq(h)1814 2120 y Fo(1)1833 2114 y Fq(;)c(:)g(:)g(:)t(;)g(h)1949 2120 y Fp(n)987 2164 y Fn(where)14 b Fq(h)1126 2170 y Fp(i)1153 2164 y Fn(is)f(the)g (majority)g(function)e(o)o(v)o(er)j(just)f(the)g(\002rst)g Fq(i)h Fn(v)o(ari-)987 2214 y(ables)j(in)g(this)f(ordering.)32 b(Finally)m(,)18 b(choose)g(the)f Fq(h)1769 2220 y Fp(i)1800 2214 y Fn(of)f(highest)987 2264 y(observ)o(ed)d(correlation)f(with)g (the)h(data)g(\(or)f(the)h(constant-zero)g(or)987 2314 y(constant-one)c(hypotheses)f(if)h(the)g(tar)o(get)h(function)d(is)j (suf)o(\002ciently)987 2363 y(non-fair\).)1037 2413 y(The)f(most)f (interesting)e(open)i(question)f(related)h(to)g(this)f(work)h(is)987 2463 y(that)i(of)f(the)i(learnability)d(of)i(monotone)f(DNF)i(formulas) f(o)o(v)o(er)h(the)987 2513 y(uniform)h(distrib)o(ution,)f(where)j(the) f(algorithm')n(s)e(time)i(and)h(sam-)987 2563 y(ples)d(used)g(may)h(be) f(polynomial)e(in)h(the)h(number)g(of)g(terms)g(in)g(the)987 2613 y(formula.)27 b(The)16 b(proof)e(of)h(Theorem)h(10)f(uses)h(a)f (tar)o(get)g(concept)987 2663 y(including)9 b Fr(\002\()p Fq(sn)p Fr(\))k Fn(terms,)f(and)g(so)f(it)g(does)g(not)g(apply)g (directly)f(to)p eop %%Page: 8 8 8 7 bop -91 42 a Fn(this)11 b(problem.)17 b(A)12 b(number)f(of)h (algorithms)e(ha)o(v)o(e)j(been)f(gi)o(v)o(en)g(for)-91 91 y(special)f(cases)i(of)e(this)f(problem)h(\(i.e.,)h(when)f(the)g (tar)o(get)g(function)-91 141 y(is)h(further)g(restricted)g(to)g(be)h (a)g(special)g(kind)e(of)h(monotone)g(DNF)-91 191 y(formula\))f(b)o(ut) g(we)h(kno)o(w)e(of)i(no)f(positi)o(v)o(e)f(results)h(better)g(than)g (the)-91 241 y(guarantee)g(of)e(Theorem)j(8)e(for)g(the)g(general)g (case.)-91 356 y Fu(Refer)o(ences)-86 459 y Fb([1])21 b(D.)c(Aldous.)38 b(On)17 b(the)g(Marko)o(v)f(chain)g(simulation)h (method)g(for)-22 505 y(uniform)10 b(combinatorial)f(distrib)o(utions)g (and)g(simulated)g(annealing.)-22 550 y(T)m(echnical)f(Report)h(60,)g (Uni)o(v)g(California)h(at)f(Berkele)o(y)n(,)g(1986.)-86 593 y([2])21 b(M.)15 b(Ben-Or)g(and)f(N.)h(Linial.)32 b(Collecti)o(v)o(e)15 b(coin)g(\003ipping,)h(rob)o(ust)-22 639 y(v)o(oting)11 b(schemes,)f(and)g(minima)h(of)h(Banzhaf)e(v)o (alues)f(\(preliminary)-22 685 y(report\).)14 b(In)c Fa(FOCS)p Fb(,)f(pages)e(408\226416,)h(1985.)-86 728 y([3])21 b(B.)10 b(Bollob)r(\264)-14 b(as.)12 b Fa(Combinatorics)p Fb(.)g(Cambridge)c(Uni)o(v)o(ersity)n(,)i(1986.)-86 771 y([4])21 b(N.)9 b(Bshouty)e(and)g(C.)i(T)m(amon.)i(On)d(the)g(F)o (ourier)h(spectrum)e(of)i(mono-)-22 817 y(tone)g(functions.)j Fa(J)o(A)o(CM)p Fb(,)d(43\(4\):747\226770,)f(Jul)h(1996.)-86 860 y([5])21 b(J.)11 b(Kahn,)h(G.)g(Kalai,)g(and)e(N.)i(Linial.)21 b(The)11 b(in\003uence)f(of)h(v)o(ariables)-22 906 y(on)i(Boolean)f (functions)h(\(e)o(xtended)g(abstract\).)28 b(In)14 b Fa(FOCS)p Fb(,)f(pages)-22 951 y(68\22680,)8 b(1988.)-86 994 y([6])21 b(M.)8 b(K)o(earns,)f(M.)h(Li,)h(and)d(L.)i(V)l(aliant.)i (Learning)c(Boolean)g(formulas.)-22 1040 y Fa(J)o(A)o(CM)p Fb(,)i(41\(6\):1298\2261328,)g(No)o(v)h(1994.)-86 1083 y([7])21 b(R.)12 b(Schapire.)21 b Fa(The)12 b(Design)e(and)i(Analysis)e (of)i(Ef)o(\002cient)g(Learning)-22 1129 y(Algorithms)p Fb(.)h(MIT)d(Press,)e(Cambridge)h(MA,)g(1992.)-91 1244 y Fu(A)o(ppendix)-91 1351 y Fg(Pr)o(oof)15 b(of)f(Lemma)g(9.)52 b Fn(F)o(or)14 b(each)i(v)o(ariable)f Fq(i)p Fn(,)h(our)e(ne)o(w)h (algo-)-91 1401 y(rithm)9 b Fq(A)40 1386 y Fh(0)62 1401 y Fn(computes)h(an)g(estimate)i Fr(~)-22 b Fq(r)448 1407 y Fp(i)471 1401 y Fn(of)10 b(the)g(rele)o(v)o(ance)h Fq(r)763 1407 y Fp(i)786 1401 y Fn(of)f(that)-91 1451 y(v)o(ariable)-84 1540 y Fq(r)-65 1546 y Fp(i)-10 1540 y Fr(=)42 b(Pr)7 b([)p Fq(f)t Fr(\()p Fq(x)p Fr(\))12 b(=)g(1)h Fs(j)7 b Fq(x)340 1546 y Fp(i)365 1540 y Fr(=)12 b(1)5 b(])j Fs(\000)i Fr(Pr)d([)p Fq(f)t Fr(\()p Fq(x)p Fr(\))12 b(=)g(1)i Fs(j)6 b Fq(x)773 1546 y Fp(i)798 1540 y Fr(=)12 b(0)5 b(])-10 1602 y(=)42 b(1)9 b Fs(\000)g Fr(2Pr)e([)p Fq(f)t Fr(\()p Fq(x)p Fr(\))12 b Fs(6)p Fr(=)g Fq(x)379 1608 y Fp(i)393 1602 y Fr(])j Fq(:)-91 1691 y Fn(F)o(or)8 b(each)h Fq(i)p Fn(,)h(after)e Fr(\(2)p Fq(=)p Fr(^)-21 b Fq(\017)251 1676 y Fo(2)269 1691 y Fr(\))7 b(ln\(8)p Fq(n=\016)r Fr(\))h Fn(e)o(xamples,)i(with)d (probability)-91 1741 y Fq(\016)r(=)p Fr(4)p Fq(n)h Fn(the)g(estimate)h (of)f Fr(Pr)f([)o Fq(f)t Fr(\()p Fq(x)p Fr(\))13 b Fs(6)p Fr(=)f Fq(x)476 1747 y Fp(i)489 1741 y Fr(])c Fn(is)g(within)f Fr(^)-21 b Fq(\017=)p Fr(2)8 b Fn(of)f(the)i(true)-91 1791 y(v)o(alue.)14 b(Thus)c(with)g(probability)e Fr(1)h Fs(\000)h Fq(\016)r(=)p Fr(4)g Fn(we)h(estimate)g(all)f(of)g(the)-89 1841 y Fr(~)-23 b Fq(r)-72 1847 y Fp(i)-48 1841 y Fn(within)8 b Fq(r)87 1847 y Fp(i)110 1841 y Fs(\006)i Fr(^)-22 b Fq(\017)p Fn(.)-41 1891 y(When)11 b Fq(f)k Fn(is)c(a)g(unate)g (function,)f(the)g Fq(i)p Fn(th)h(v)o(ariable)f(is)h(a)g(positi)o(v)o (e)-91 1940 y(indicator)h(e)o(xactly)j(when)e Fq(r)326 1946 y Fp(i)358 1940 y Fs(\025)18 b Fr(0)p Fn(.)24 b(W)m(e)14 b(de\002ne)h Fq(t)j Fr(:)f Fs(f)p Fr(0)p Fq(;)7 b Fr(1)p Fs(g)812 1925 y Fp(n)852 1940 y Fs(!)-91 1990 y(f)p Fr(0)p Fq(;)g Fr(1)p Fs(g)12 1975 y Fp(n)44 1990 y Fn(to)k(transform)f(bit)g (v)o(ectors)i(so)f(that)f Fq(f)15 b Fs(\016)9 b Fq(t)j Fn(is)f(a)g(monotone)-91 2040 y(function)e(if)g(we)i(ha)o(v)o(e)g(the)f (correct)h(v)o(alues)f(for)g(all)g(the)i Fr(~)-23 b Fq(r)732 2046 y Fp(i)746 2040 y Fn(:)122 2150 y Fq(t)p Fr(\()p Fq(x)p Fr(\))193 2156 y Fp(i)219 2150 y Fr(=)262 2091 y Fi(\032)314 2125 y Fq(x)338 2131 y Fp(i)465 2125 y Fn(if)11 b Fr(~)-22 b Fq(r)520 2131 y Fp(i)545 2125 y Fs(\025)12 b Fr(0)314 2174 y(1)d Fs(\000)h Fq(x)410 2180 y Fp(i)465 2174 y Fn(otherwise)668 2150 y Fq(:)-41 2264 y Fn(T)m(o)i(compute)g(its)g(return)f(v)o(alue,)j Fq(A)476 2249 y Fh(0)500 2264 y Fn(de\002nes)f(for)f Fq(A)g Fn(a)h(ne)o(w)g(or)o (-)-91 2314 y(acle)f Fj(SAMPLE)166 2296 y Fh(0)178 2314 y Fn(,)h(which)e(works)g(by)g(recei)o(ving)g Fr(\()p Fq(x;)c(f)t Fr(\()p Fq(x)p Fr(\)\))12 b Fn(from)-91 2364 y Fj(SAMPLE)i Fn(and)8 b(returning)f Fr(\()p Fq(t)p Fr(\()p Fq(x)p Fr(\))p Fq(;)g(f)t Fr(\()p Fq(x)p Fr(\)\))p Fn(.)13 b(Since)8 b Fr(\()p Fq(f)e Fs(\016)r Fq(t)p Fr(\)\()p Fq(t)p Fr(\()p Fq(x)p Fr(\)\))12 b(=)-91 2413 y Fq(f)t Fr(\()p Fq(x)p Fr(\))p Fn(,)h Fj(SAMPLE)191 2395 y Fh(0)215 2413 y Fn(is)f(an)g(oracle)g(to)g Fq(f)j Fs(\016)10 b Fq(t)p Fn(,)j(and)f(the)g(distrib)o(utio)o(n)-91 2463 y(of)h(its)g(returned)g(v)o(ectors)h(is)f(still)f(uniform.)22 b(So)13 b Fq(A)667 2448 y Fh(0)693 2463 y Fn(can)h(use)g(this)-91 2513 y(oracle)f(to)e(call)i Fq(A)p Fr(\()p Fj(SAMPLE)366 2495 y Fh(0)377 2513 y Fq(;)7 b(\016)r(=)p Fr(4\))p Fn(,)13 b(which)e(returns)h(some)h(hy-)-91 2563 y(pothesis)c(function)g Fq(h)p Fn(.)k(The)e(return)f(v)o(alue)g(of)g Fq(A)611 2548 y Fh(0)633 2563 y Fn(is)g Fq(h)f Fs(\016)g Fq(t)p Fn(.)-41 2613 y(Since)15 b Fq(t)g Fn(is)g(based)h(on)f(the)i Fr(~)-23 b Fq(r)391 2619 y Fp(i)405 2613 y Fn(,)17 b(ho)o(we)o(v)o(er)n (,)g Fq(f)h Fs(\016)13 b Fq(t)i Fn(may)h(not)e(be)-91 2663 y(monotone.)d(In)d(particular)n(,)h(the)f(transformation)f Fq(t)h Fn(may)h(transform)987 42 y(v)o(ariables)k(incorrectly)f(if)g Fq(r)1399 48 y Fp(i)1425 42 y Fn(is)h(within)e Fr(0)g Fs(\006)h Fr(^)-21 b Fq(\017)o Fn(.)22 b(But)12 b(in)g(this)g(case)987 91 y(we)h(can)g(relabel)f(a)h(small)g(fraction)e(of)h(the)g(points)f (to)h(make)h Fq(f)j Fs(\016)10 b Fq(t)987 141 y Fn(monotone.)20 b(Let)14 b Fq(x)d Fs(\010)g Fq(e)1350 147 y Fp(i)1377 141 y Fn(denote)i(the)g(bitwise)f(e)o(xclusi)o(v)o(e-OR)h(of)987 191 y Fq(x)e Fn(with)g Fq(e)1127 197 y Fp(i)1141 191 y Fn(,)i(the)e(bit)g(v)o(ector)h(that)f(is)g Fr(0)h Fn(e)o(xcept)g(in)f (the)h Fq(i)p Fn(th)f(position.)987 241 y(If)h Fq(t)h Fn(mistransforms)f(the)h Fq(i)p Fn(th)f(v)o(ariable,)h(we)h(relabel)e (the)h Fs(j)o Fq(r)1865 247 y Fp(i)1879 241 y Fs(j)i Fq(<)i Fr(^)-22 b Fq(\017)987 291 y Fn(fraction)15 b(of)g(points)f Fq(x)h Fn(where)h Fq(x)1479 297 y Fp(i)1513 291 y Fr(=)21 b(1)p Fn(,)c Fr(\()p Fq(f)h Fs(\016)13 b Fq(t)p Fr(\)\()p Fq(x)p Fr(\))21 b(=)g(0)p Fn(,)c(and)987 340 y Fr(\()p Fq(f)d Fs(\016)9 b Fq(t)p Fr(\)\()p Fq(x)g Fs(\010)h Fq(e)1208 346 y Fp(i)1222 340 y Fr(\))i(=)f(1)p Fn(.)1037 390 y(W)n(ith)19 b(probability)d Fr(1)g Fs(\000)g Fq(\016)r(=)p Fr(4)p Fn(,)22 b(the)d(number)h(of)f(v)o(ariables)g Fq(i)987 440 y Fn(for)f(which)g(we)h(must)f(do)g(this)g(relabeling)f(is)h(at)h (most)f Fq(n=)p Fr(2)d(+)987 454 y Fi(p)p 1028 454 235 2 v 1028 490 a Fr(\()p Fq(n=)p Fr(2\))7 b(ln\(4)p Fq(=\016)r Fr(\))o Fn(,)j(because)g(the)e(chance)i(that)f Fr(~)-23 b Fq(r)1694 496 y Fp(i)1716 490 y Fn(and)9 b Fq(r)1804 496 y Fp(i)1826 490 y Fn(ha)o(v)o(e)g(dif-)987 540 y(ferent)j(signs)f (is)g(at)h(most)g Fr(1)p Fq(=)p Fr(2)p Fn(.)17 b(Assuming)11 b(this)g(occurs,)i(we)f(may)987 589 y(need)k(to)f(relabel)h(as)g(much)g (as)h(an)e Fr(\()p Fq(n=)p Fr(2)e(+)1663 554 y Fi(p)p 1704 554 V 1704 589 a Fr(\()p Fq(n=)p Fr(2\))7 b(ln)o(\(4)p Fq(=\016)r Fr(\)\)^)-21 b Fq(\017)987 639 y Fn(fraction)10 b(of)g(the)g(points)f(to)h(make)i Fq(f)i Fs(\016)9 b Fq(t)i Fn(monotone.)i(But)c Fq(A)1870 624 y Fh(0)1893 639 y Fn(need)987 689 y(not)h(compute)h(these)h(to)e(generate)i Fj(SAMPLE)1676 671 y Fh(0)1687 689 y Fn(:)i(The)e(probability)987 739 y(that)c(none)h(of)g(the)g Fq(s)g Fn(e)o(xamples)i(seen)e(by)g Fq(A)g Fn(fall)f(in)h(these)g(relabeled)987 789 y(points)g(is)h(at)g (least)987 847 y Fi( )1020 918 y Fr(1)f Fs(\000)1091 847 y Fi( )1129 890 y Fq(n)p 1129 909 25 2 v 1131 947 a Fr(2)1168 918 y(+)1210 853 y Fi(r)p 1251 853 115 2 v 1256 890 a Fq(n)p 1256 909 25 2 v 1258 947 a Fr(2)1293 918 y(ln)1340 890 y(4)p 1340 909 21 2 v 1340 947 a Fq(\016)1365 847 y Fi(!)1405 918 y Fr(^)-21 b Fq(\017)1422 847 y Fi(!)1455 856 y Fp(s)1514 918 y Fs(\025)42 b Fr(1)9 b Fs(\000)1659 847 y Fi( )1697 890 y Fq(n)p 1697 909 25 2 v 1699 947 a Fr(2)1736 918 y(+)1778 853 y Fi(r)p 1819 853 115 2 v 1824 890 a Fq(n)p 1824 909 25 2 v 1826 947 a Fr(2)1861 918 y(ln)1908 890 y(4)p 1908 909 21 2 v 1908 947 a Fq(\016)1933 847 y Fi(!)1973 918 y Fr(^)-21 b Fq(\017s)1514 1018 y Fs(\025)42 b Fr(1)9 b Fs(\000)g Fq(\016)r(=)p Fr(4)g Fq(:)987 1109 y Fn(W)m(e)i(assume,)i(then,)f(that)e Fq(A)h Fn(sees)i(a)e(monotone)g(function)e(through)987 1159 y Fj(SAMPLE)1166 1141 y Fh(0)1177 1159 y Fn(.)1037 1209 y(If)j Fq(A)g Fn(succeeds,)j(its)d(hypothesis)f Fq(h)h Fn(has)h(error)f(at)h(most)f Fr(1)p Fq(=)p Fr(2)e Fs(\000)987 1259 y Fq(\017)p Fn(.)41 b(This)20 b(hypothesis)e(may)i(also)g(be)g (wrong)f(on)g(the)g Fr(\()p Fq(n=)p Fr(2)d(+)987 1273 y Fi(p)p 1028 1273 235 2 v 1028 1308 a Fr(\()p Fq(n=)p Fr(2\))7 b(ln\(4)p Fq(=\016)r Fr(\))o(\)^)-21 b Fq(\017)13 b Fn(relabeled)g(points,)g(so)f(its)g(error)h(on)f Fq(f)k Fs(\016)11 b Fq(t)i Fn(is)987 1364 y(at)d(most)g Fr(1)p Fq(=)p Fr(2)e Fs(\000)g Fq(\017)h Fr(+)f(\()p Fq(n=)p Fr(2)g(+)1427 1329 y Fi(p)p 1469 1329 V 35 x Fr(\()p Fq(n=)p Fr(2\))f(ln)o(\(4)p Fq(=\016)r Fr(\)\)^)-21 b Fq(\017)11 b Fs(\024)h Fr(1)p Fq(=)p Fr(2)c Fs(\000)h Fq(\017=)p Fr(2)p Fn(.)987 1414 y(This)h(is)h(the)f(error)h(of)f Fq(h)g Fs(\016)f Fq(t)i Fn(\(the)f(hypothesis)f(returned)h(by)g Fq(A)1893 1399 y Fh(0)1905 1414 y Fn(\))h(on)987 1464 y Fq(f)j Fs(\016)9 b Fq(t)g Fs(\016)g Fq(t)j Fr(=)f Fq(f)t Fn(.)1037 1514 y(F)o(our)d(e)o(v)o(ents)h(may)g(occur)f(to)g(pre)o(v)o (ent)g Fq(A)1619 1498 y Fh(0)1640 1514 y Fn(from)g(returning)e(a)j(hy-) 987 1563 y(pothesis)g(of)g(error)h(at)g(most)f Fr(1)p Fq(=)p Fr(2)e Fs(\000)g Fq(\017=)p Fr(2)p Fn(.)12 b(One)e(of)g(the)f (estimates)i(of)989 1613 y Fr(~)-23 b Fq(r)1006 1619 y Fp(i)1029 1613 y Fn(may)9 b(be)h(outside)e Fq(r)1306 1619 y Fp(i)1324 1613 y Fs(\006)d Fr(^)-21 b Fq(\017)p Fn(.)13 b(The)d(number)f(of)f(v)o(ariables)h(for)g(which)987 1663 y(we)h(must)g(do)g(relabeling)f(may)i(e)o(xceed)g Fq(n=)p Fr(2)d(+)1685 1627 y Fi(p)p 1727 1627 V 36 x Fr(\()p Fq(n=)p Fr(2\))f(ln)o(\(4)p Fq(=\016)r Fr(\))p Fn(.)987 1713 y(One)13 b(of)f(the)g(samples)h Fq(A)g Fn(sees)h(may)f(be)g(in)e(the)i(relabeled)f(points.)987 1763 y(Or)f(the)h Fq(h)f Fn(returned)g(by)g Fq(A)h Fn(may)g(ha)o(v)o(e) g(error)f(more)h(than)f Fr(1)p Fq(=)p Fr(2)f Fs(\000)g Fq(\017)p Fn(.)987 1812 y(Each)16 b(of)f(these)h(occurs)g(with)e (probability)e(at)k(most)f Fq(\016)r(=)p Fr(4)p Fn(,)h(so)g Fq(A)1960 1797 y Fh(0)987 1862 y Fn(succeeds)c(with)d(probability)f(at) i(least)g Fr(1)f Fs(\000)h Fq(\016)r Fn(.)p 1953 1857 19 19 v eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF