ࡱ> FM.Kb|JFIFddDucky!Adobed0M   #%'%#//33//@@@@@@@@@@@@@@@&&0##0+.'''.+550055@@?@@@@@@@@@@@@"!1" 2A0P@`Bp#!1AQaq "02@P`BRb ]<@ L L L L @ @ @@0C110C111101h)1 &4C4`X B P&mP5Djcd!a@&PH&*mP`P&`Li0L*V! Rm`@ R0#d)AՒ0@ eC(Ę&H!(&Į@`b*D b(kQ= @8hCa4Bv@d)l%04&1*BT)`*BJ@P$ 0 0C@m4($`0t֡7"$66M6L܉M΂]!*bW4KCB&m Ar%l̤!ЧD" &h&)Uȝ` \'rTԀW:v413UMԌMT L%h)rM&4CVhhM56Jj@C)$s)"DPB!bI5M%Ы;T 5'LJ!#BD , )dڵJ 3*Ն{gdM*cD[ t*P9lv(RCW7;D)Km\4!;B%N&SijQi Gu6-sIuPJѐKe"+455)qM\h7$Աԣl9lTERb)#L;Sj7\j@b^*d&H)sR"$4qBֳr+!M⦚t4b؆! i,őYɋ:NTCF2RK-ES&5Ahȶ!V!CWpk EA2YuKFEѝX)D<MSL0n*i)g"gCYZMUHf)5,WΤLVYUQ)H$ܦFѪLQ-t 2 IH ŠԄ!n:R̩X芫U()&i2hpCDZ!M9CHLcBZk*)8.H, CT;Lk-QkNtC"Dᗖ UJTR (*E@IE)T8n;D]2ɍr5͢"vRR:J(BШ:άj8)= t"I$&-F쑃N:{N$r*`K#MmidTy5-y [tT &^ L $hIHґr15rRPHLGSB D5cYBi (bmɝ͔ I+p!M(T H].I(cyҒԖ-R%jjR, R43f:TR ֔Lji̹Ji2t#+:bi:I/;h9rf:+sV$VtW;! j ℨbB*CYZ)LТ`ZI.t%g TU@LT8M^T8,ILE%W%EMAJySIh:$bo!zhpgA4rȡ*!ŚgHGM YY t*D h*RB\i*M!!%T(-<ǦTY()K$hJ!Mt)b!҂BY$RWU8)46p+TFD%X&ZB ZZMaQ(B(qIRr4!qPE6Efm4YTHZ$ڦuB03F`Ӆ*hڌ i RUC@FU&PEPjei KΒVfX4HDH$b*,&\cj"ª ""*P:F "QF1 HAjGQCΓR-E0mYN(s,kJUz,-HV ӚL\`E;j=3@, \ZrJnΔʧ Rh-Rgm IJ)(Ph!֒HES;@#d"(K\VZf`S0*5JjƯ;cj@A1jPA"ZH%TPMf-& R7H4gT(%-ҳpQK96#U t"4iٛmf)zeE^VLQ*mHyI[B42j%˜Wg>.\xsυ/2Ĺ~>g?sW?m~|*%isDRyy_sQ?GfyuG'^|TK_c?om~3'q#̦J'!:%N!rT \J*ua8,W(+L31YNN%qA>Z* Lsu"JOnd/Njl'2JTcp#*S\C )1'+l*\ RJ\9~)`$FWPH `ms?*V|*%FTuQT娟sSCTvbZK\LJ*אn|:SGu_=Zf7#fuz2St 4>3AeJJ^\RyԼzQgU`r]8(b<˱_}M Ϋ x\E`ΪXҷQB6@jZ@WS+2;Z@\_:aΫ2sͺ~,3P9~@%bKY\F*c-2RfRa'\93댧ZߗsF3p53#A'~0^ Ԣ<tY>%q3&8qST.V%f̙ͦƉՅF8nYJψ ֝M|\PK$KA̋A4 Wg/]8xtus®TLNVݼT:rVRμhƁBΦLS^SK ZWeKY|vtu9.gֺ u gý:sS9j%zG%2h:Os+:s̪;>+!h3ƙԈǯZ־q} 稢[-gfiYh9L eW|gj=N.ZW3|fgը|m$s54LeZYEX \{z.kh&u]L~ʣ\Lj+4&3g2phhih:c /^P{uXI8 sܷ.㾲Bkئys +ռN>spr0r Ij [i٪m. zĩH}면S48f1q^+=g]LB1?Fj&EWePďZ,xJ{К=f3η3,&r&lZӠ f!QygW]KC8rfi(Z3膝j?bkZ~ѓ+4)=s!ӧY3tc,Uֱֳ'f ޻KkkٜaeYgi sZI99ήvr:֜ۏV֬zs>EVU]3>PukZRS\^Gp tt[}Y2h3zդp̡3F yMTrN&CFIRR!fv\glE=k &Fu02J52g>C r #Lg ;^Ck0r3DW_9WNPT;0zG9dkݪQlbkZS׉*Ԇۭfjy\ǯK|䅩{K2ag/\KA)5si2+w ϯZY׻Y&l3u]f#2L3Z26GZӦL뙑dΖk-_۬c&}yusf:uc= Y`WJMoks4\..u[dkM @k[@/E{TӠZ[LʇRkNoA&7ˬuɕ9E!T}3:F :u~7٫\nz }73f&~!v&i5+C=o_XL4\8,Q;t=E2N-smҫy]iofܖ>p }ۂ&8p]/3J:׊+j}AQ˧3)ۼ`HLgZ+0ˤpjۂ\h"֗|| t3EIi=khVӟ̌vc>#ޥqtr|gZYs:6͹ Y]R/%:Rs;\nS} kڱLk&=iXsp%[Y3s_ 4崪qmQnWU0C'mS`%g GZd\ ѫu dz'gn]&4Oa3Td3bWD3zgejd<!?TuWKLZ;๜gJYx#6@Y'q7h͝}yˬƒi}?!ZUjYukgzLoZ@dkG\qY9Y֡zkt0&Bj~EM =L̜kjtz\g{>fd9fw; J&?LtdQm޸[gXL_jQ֋&NzMmRoE3zz.z#u,u 1NiMkc}rL=SLќ8Z8Yz^&Z&4taUtEsxijy jAL 82'X V{WPaPs5aheHz^X۝}=ymtiɽvqƺ&W[L:0¨ ɝ+32>i7sLk][U HR.bG-huYփGLjz[YiE]y=e'p?X,Wح$S6)w`\wXָ3kFsMk&~sbܜDUh2L]\榶ndXOY\OSg:IPLgmu{Y kZBYY7cז&f4[=z=ecttEΐOgM3 g($|UfhYD iLg&W5rkZרɐ57=z_^讳Q8ɜx[muvf[w32{3f:jvj^ W׎ hӲ*f >d5ՎΧ+*Zl pT70߱ ׳A7:Fpw NçHӭ:ukv ւvcJ2+zSH.DJ2t:20h1C]Mju\:z{k^ n PlPM}{K5Z\Q-[tGPwM\܋Hp~V}}OWK9 ` p:S1kZ3Ȼ -.oٝls?&yVg-ރLtAߵrU%C[ӤzΤbjcguLiEU^1nU ћV ?]S4*zItg}Wι\W9'5m0S@Jjh*h&yR'l.z{oO9oPRaP=Gc*ՙ,KE,-*S}5ut' ٸ"Egf;]b~jf9,2`!ɕ9 p]n bQ{tNՓY`֖tSZ3! 3t6tRbgV]$p2F_^lk3GaDN3fspͨVrCSԳ&X2ٜkMT׳]jdvNC^ͺskַI1r^ӌE֞]u%u.3;9̴2bm}]_c e֮dkӭ%?4<W 9 -ֵN4G49 EhT@!A9aUtr$҆yFj=`ZsTӘ23us82,CT\ ?Wn-r:=}M[mr1jV3M=ӧQthƙ ˒sz֬X%-]gU|odZ9˿c2-s5gfD\2kSy/KFRq[7öuvoפJ=~1Ss?Q7ˑPH )fɕEۧ9=sWfTifɱYɜQ9!o fg,άond~t̄!,Ĭ*FCy v|)ueIAm٧YxԳWĖt&!C&d@ofUϮ\\붷t}:cZzjSNRtI&WAհ9Lg0ݲNֵyװ,=giPu iΗ`Mf}uޝ`yp{]=(c7K%Z3`umJf193zkyxk|s91F; v9]1J&d]]ۨt+1׬4Fg7=}M_ѝӭQW)LQC [cgf Kk+3cY5ԃ{?5ۜ^Z3e8ζh'[/ ڂQ_RfulpXaR7Y>5~3Uu-bNˢtX煶hhgדZӦdY]6N;jg$:g?/56ڹ;';A+,zKg YZ24`&Fz9E.:ւkLtֻ8ˤPem1֟f9÷gWBR-^ڜ(ٜn̦f*N{@YYQ4n J4@3y0K:;\x3ev3]9|`퐷RYvO-&F;gkjv3/Zz(u3&G~VvkQOS&uPʺgla29ʱҹj gZgʠ F\f{d@Cvd&}zZeZ֟bޔE+ KI7vO#isl3H+35;֊jd=4{49LwåhS:Mp8*-AoSN*g<&>nA m^g3Qδ\d͙U9RM.5̔vtd 'S.6N@H te\vV3#fvjC-roq]Lu>~>sMN)ӓ$WZui1Lpμ-34k)Fknu֮uDX2^3g zW:ڦz2^ەnmhuRd d:nnp8q=σ9f@>ަyuYΪlL(-\.&_~us3}MCfuh-0g2+gx=9g!9=: oP3Pѓ׭1iZ18MN\l-e6sS󬼺7ty֪ Zjioј fwkJss8~֚sWY678}9Ү3zd4teSmƲ/Zæ7c|\g6fhX 3gétֵ j8>'ΉVo+֕1< .@Z2ёMYᅝ!I=hC_֑Uq[_Yzޓ}cKX]o&GJP S흐/SFQJEo9W띌 :GUε7ZB![55i)3v+P֕dє]mg]F:iMɌX0j13{{wnڿ_g ~׫ޔ+H붳IOg8Yg7ւ=m_:I'n7zw=@e+mOcdmsײgRe,4 *uSzN`ʍ̖zdM t&@ڀڳ\vQ4esΕ:[GP3_mVz##uikkFC+9oƴ˃ \vӯ^S.I%#3]reKW3Y׌5UP"AXGk[\d7uk(5{h*9Ajgmi]fhDk[PfB:QZS5iuf9sUh/AZbdq}/Յκ.sS) 0PuNdɭOYj|ƃNګ+3Wm=FiN@"ȩ.3%;d@M+3dəR v*g_ml5d /&]fz5dg[@&2vӕtk_>kzk kFQ\%芭Abz.E]/RgMN9)C:U3am2s[⺉,Wx.z:3z5gy 8&1Ψ5 tYwZtʏ&M!9Ӥ 粘5٥ Qu0ڌjuc9ˤ5پawf ^IdPJϪ2aDlk}ugBhV;It-P{fjM+ 2̔W*ՆJfsd4?̦ic] vjsu d}9Ur|%;/|z[ +Q֣˚OdOol&{ہKIˠ/ZwYE9 2UE_KYQg;G2ڳy>83 }WM!jLd@NibWEku?!.h7qLy}jJRȰSvX*C 9+Ygrj9Kc :ӧ[.ig%{=vW)bGtzM'Q|> `)sQSPY_fR3Pscۭ?&N{hȻј3P Ӑͯ V S{u uu]A;?6Nt0a`}g yY{-q:X4vm)u:XV&n.OBB:MwwΧ3u3χ>4GZt%S/KKs|̴W Ӡ?[Zt[w "b:VᴎOjEVH{.Py\jK b8sDF-M73WUHk9 4|`V|&AYDl.ߕZxekHx*ȷ3\8ounRƧ*\9vbs4itLD&P˖KOQV\x%Mme;{2sρ?gUy3;Em0Yrw?μ2~'i\[K.f7>`*Oy/*W x'5iep:Xp\, -JKeiqcaK.XBY/,-KX>gυ ϋU֝?GN =B:_ͱ]p<|Apj[.៝kWpj-˗ -Qbߋ ϛ|οo7[O_c?ޙrXoڤAr,˩dXrb_Fܹ|A,] ܾ{rf.eh-T *Q*T(J(~u+J /#ZX<~^VX/ })~}1}^JZƱ6/Q1}S^FY௢>'n " ~ִ/H%^Z 蝉xD/Q财/m%au^N(R,Y_(͞e*ǯ2 +l"$2B<'9֛H=Iz۶1 w.4 (󤔨y#Y[v1>Hf촲/lI1 HX,-<"YegYEU!6'b",Ouܲ[,b#(&%pR6z",̶@ƊIt( 7?*R<>Y"4Mg$x87vLi G''B,셄7#,z # ^FpGܻ!*<|U4Ydl>=W/mlD$Hu^M^œx+؄.HWr$?sXۤ]'81G y$|"OR[#Y"~G^Im.Gӧ?&l(^#28{U"헅Y)GUD< U{ݎ?RVY%r$Qt!.}vD%A#dm3OQy-/<b'%܍4܈Ȃ̞ p*'+ԽϔQ;rJn:q@^r4/ Djv|Uuݍ&u^rEOcFK'b'<7ek;w,r&hOɩd>%*%XK!C?/s.ǩ䗤uT1z.R!Po뫇dR> a TY de^k _rs$y=>]} ^i3/ m K)d^cܓ>7Y2F0ps w>*xX$Z%-F|Z ^IL?r-% -i,eID~B!<'O$`]R1,FB fbEScKG-^M-r?o='粖G W$uSu\lKV^엃0>3i}oZUU2z A1 Tߦ)&2F^zc&YHj)i$d|DK'`!T^G̓2yYUeuC>}U4ݶ?, f F L}(ne +KaW+!}Dnɑ$MdɊ!)DĒJV)8^ 1֓"^ p5 زVv"::^Ic܏>='Otz"Ϗ_r.ߑ!Agl=OG/YJc+{ pF`Dg9!T)݋b1b1l͍% ampz[ N4%lKT^gGe Qx~‡5OKW'|S,>p<<[dNt='',m-%^I$=Kg>=p"XđKj/_"Gė WW2Q/G4|zgI^ļ uge#?r/ݐ@I#@Ң&OGv8^zp|J1u%`5nW>K"X>8FEz-o[%DrK<kKVؘ^v= T=4mPr~N=kK(q/Vyx%]pO <ɛ Ƹ+rbH ~;ݐقVH{\K-bIc!`RBPK,)Y/,HDlnB? ?")~o2>%ɉkCK/F~ڸɚ/',|BSLoE剡)Z%'Bx)$=_:Dr%=7&kOb1,ull@B#KE zL6F{24Y=-$py&,ɛ9") b%d2J )^p&g>;#/-lD% D<]q6ϊB\  %9>S|GS3$DuvCgw9JK11DdU)G]d䅒ƕ!{K,|'=pR>H5/cI߱[mDvB"`A%m&4Hn/Qd ,]QBs|b,n^Ii-%H|V7eř|mTV/,Ci$4l] U/$K<4sI+'ɼ0%q"%KDU]/HHވƊ9L UM񶞂HuN+rJ\ !ܡ1:ppLKj[?!uرq+#u|3ؘ0DR[dnG0K%f)99&) 2z-pHp!-/,7%M>+ܡ9eFKtX-VɊ'n,F[%BX'%%A$Lz cyvOgleIHV^KbV ~Dc^4$xG!:&e('^9{8I I}nm[nN[""u:R"F$Kؽ*+,#mS.3m Ƶ^>)%g0Xt]UKeBҥ~670(1GirrK?:.X )!a7%id!*X8Dr# Qc O'XJVBPUlN|؄_bt!{Hd,E[ݑd|)pxe[!+/) $22nF!\KfD_Y(L$ X)DbIcs.2~Tgq)'d ƖNǁ=82':{2Q϶:>J%.7)ANz^ Kvxܯv"VĞXK>}<.Zxbo?bd=zX[igNK$u%ĐdutCt~Jȧ#HD!-du=DQKLݒǨ#_BK!HP[܅YPBx<OjE[$ 얆߰TğQ-=! 0su*D4EI JD|Xۢ6-A =Q=)x䥍ė)$!"u:rd_Tʢ[hIzHH\\rd+|Bnbl)nV CnngQ,e=^⶗-wnFUB'}" {"2VD`Ky>=.ܐJع& ҒJ>)D T u@#d'/HYnζGU%K#cX)y.>]{׹Diz6Og1 #FɃ2V x'aP (^g/bom[-0f{1dnpILOkdrJ'ɒdnN`L8=-K,GZ>*KoO-u>+ܕD䬓="p[!/ $H$}uE G&i:!8!)6KKqZP;VGd#t"4yGSO'>]+C?q%@o}t?g9!nI IgstZ$l``F?|>O'ѷɋ9zB]3BtIz#t9# %$߁,$َu'_y:rx.1[[BҶ'Β/B":u//؅ȥ4)r_n$AC{! ،dq=6{a'ۅ*.ZrBҶK<#<*qMu\iVF#q>n?#Jz^7#m% C>tKΒelY(n(d!aoLQ*,s 6Uΐ41N%!|V!c{L!g}>]^䯹nX4ް^ &䄨%J-؞E^HP䎾Yw,/$ox<I$x2^4pz <DF|z{9 ,//JP~GȏېrmAI7S-%)?' ,N,)$\Kܼ"{Vy'7>[IjY/ܡ<^OQB i .9܅x$"/|-lN BDrU-yjO$NF$b Me< [ik؎9"HE{g Q`>ļQ%))Ye[zL(d"<*-ؖGT>ݯU,Wө e~4luoqN^9.׭u4%s /bȖUٞ Vy/%i.x!nI' ,m۷]" z[^'$".o'& (Q}<:Fd6Y/; r?(ΰFM$9%pY.7*ˡ.KrlbXJϗlLFcs&Y Oٵ bHTOpB-EđY)zɒbtVγ2ynJhY-/Ư=(d%//bYCycOb!K)/-Eg,bY RzK$} n3SQ cmcbLd-+$,/Y(xҰf bXoIu%x%VBy'd4%;'8H1&J#a;Ę"`BJ,^^璈TK%kk^#G)pY &OmH$*2%躱xc\P9rz]Bd'\唰>ݷ'>NbuR7N|bK& RDI"{R Y"~p>k}{9gb^ \;~J#/:K#9XM𱤒1oqU2Y%Гs sGK6~%2Iv1//rd/("hXųԷIX-ޓ;QB!;O{!u蟗ૂ۳6ȋ3 b^u[w*cmHYgedVmqY?'C< iFli\*9b[&rP^߱J]DFD>K~!amO:yx,ܷdp9r.O{֘_'PlϏU<YjķODh3d =#s0+92{ ,g5'Ǫydƒܻ̕lL^C% /}rVH_qy,[,^,m,]zlm,v)rBB,dux(D/=Ks#J pLI.ddǡ,vEh=M#m<ˡs#_џbй&HW$!Y'/ Ix!k%R "OK!-!{K|^N|fX3$bEi ܫD$%c$$6%/Q!Ξ~ڷf4dZI>KYkB]A?KoRx(n/^^I&~ >CԂ +=~ޱ} ~Tk o/^OV_G/QsdU'J[*k~?_ Hkk*,WԗWgE?ӯ;je<ܩ77777777777777777777777777777777Ŝ( F/ 0|DArialgs }0z[ 0DTahomags }0z[ 0" DWingdings }0z[ 00Dcmsy10gs }0z[ 0"@DSymbolgs }0z[ 0 A .  @n?" dd@  @@`` ( x4N%HH ,,   !" $ % &D()5*+ .0 3 457: :; <GE> ? @ A BCDDG H LL,R$.Kb|M 0AAP]Qf@83[E1 ʚ;G 8ʚ;g4DdDd z[ 0ppp@ <4ddddL 0| 80___PPT10 ?  %}2Extracting Randomness From Few Independent Sources<Boaz Barak, IAS Russell Impagliazzo, UCSD Avi Wigderson, IAS>  1-Plan: Randomness Extraction Randomness Extractors Randomness Extractors Solution 1: Seeded Extractors  Solution 1: Seeded Extractors  Seedless Extractors       $ Plan: %!        &"  2.Plan:  Distributional Version of [BKT] 51  !Plan: ($Detailed Plan: Collision Probability   +'Detailed Plan: )%Nave Approach *&Nave Approach ,(Detailed Plan: Proof of Main Lemma Tools: A First Distributional Analog: -)    .*    Another Result:A disperser for the case that all samples come from same distribution, which only requires W(log n) entropy (using [EH]). J{[ff  Open ProblemsExtractors/Dispersers with lower entropy requirement (k=nW(1) or even k=W(log n) ) Improvement for the case of two samples (related to constructing Ramsey graphs). More applications of results/techniques.6fff fff ',  ` fy`ff3` Mj*333FV*` ffNNt^X` ffNL|>rL` +T3f3f` MMMff3f` Lx[he2` {$$>?" dd@,?nAd@    @ `  n?" dd@   @@``PR    @ ` ` p>> `$(  ` ` 6 " `P  T Click to edit Master title style! !$ ` 0l " `  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S ` 6 #" `^ `  Z* ` 6 #" `^   \* ` 6 #" `^ `  \*z ` NA޽h ?texture_mid#" @@ +T3f3f80___PPT10. ` Textured  d(  d d <dQ #" `   T Click to edit Master title style! ! d 0T " `    W#Click to edit Master subtitle style$ $ d 6X #" `^ `  Z* d 6\ #" `^   \* d 6a #" `^ `  \*z d NA޽h ?texture_mid#" @@ +T3f3f80___PPT10. `  *(  x  c $kd   r  S lld `    H  0޽h ? 33___PPT10i.@NH+D=' = @B +   "p (    B& `0    2  0 "` N3. Introduce main tool  Thm by [BKT,K]8( $     0 "`p  q4.* Prove our main theorem.:     0 "` p1. Discuss problem and model8      0M "`@P g2. State our result8   H  0޽h ? +T3f3f___PPT10i.s+D=' = @B +*  tll(  lr l S 8`0   N l 6 ,$ 0 fRandomness is central to CS (c.f., randomized algorithms, cryptography, distributed computing)2g  J  l 6x  ,$ 0 m7How do you execute randomized algorithms and protocols?88 f l 6 P  ,$ 0 Solution: sample some  random physical data (coin tossing, thermal noise, hard disk movement,& )(a  W G l 6  @,$ 0 KProblem: data from physical sources is not a sequence of ideal coin tosses.FL    " H l 0޽h ? +T3f3f^ V ___PPT106 .PG+D* ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(++0+l ++0+l ++0+l ++0+l +/  ( p(  p p B\r `p  r  p 6 r p L Definition : E:{0,1}n{0,1}0.1k is an extractor if 8 r.v. X with entropy k , E(X) is close to U0.1kff  f f f f      f  f  f f  f   f f f p 6`r 0 ,$ 0 IIdea:(   p 0!r4P :   p <d1" Pp ,$@ 0  p 6G"`@ ,$@ 0  p 0 P ,$D  0  p 0 P ,$D   0  p s *1" `0@ ,$D  0 p 0 P ,$D   0 p s *"`p ,$D 0 p 6'r P@ ,$ 0 7X f p 6*r  ,$ 0 7E f p 6$.r  0,$ 0 Ghigh entropy data p 61r   ,$  0 ? extractor   p 65r  ,$  0 Duniform output p 69r ` ,$ 0 Urandomized algorithm / protocol  H p 0޽h ? +T3f3f~ v ___PPT10V .s+~D' = @B D]' = @BA?%,( < +O%,( < +D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* p%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DU' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* p%(D' =-s6Bwipe(left)*<3<* pDu' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* p%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* p%(D' =-s6Bwipe(left)*<3<* pD' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* p%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-s6Bwipe(left)*<3<*pD' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(++0+pr ++0+pr ++0+pr ++0+pr ++0+pr ++0+pr ++0+pr +    tu (  t t B~r `p  r  t 6Pr p L Definition : E:{0,1}n{0,1}0.1k is an extractor if 8 r.v. X with entropy k , E(X) is close to U0.1kff  f f f f      f  f  f f  f   f f f  t 6r 0`,$ 0 oProblem: No extractor exists.6    t 6r  ,$ 0 Thm: 8 E:{0,1}n{0,1}0.1k there s a r.v. X w/ entropy n-1 s.t. first bit of E(X) is constant.b G f  f f f f f  f   G f f  f $:" t 6\r  ,$ 0 z\Proof Sketch: Assume wlog |{ x | E1(x)=0 }| 2n/2 let X be the uniform dist over this set.] ff ffffff#DH t 0޽h ? +T3f3f___PPT10.s++D' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(++0+tr ++0+tr ++0+tr +[6   x(  x x BLr `p  r  x 6r p`,$ 0 Def: E:{0,1}n{0,1}d{0,1}0.1k is a (seeded) extractor if 8 r.v. X w/ min-entropy k | E(X,Ud)  U0.1k |1 < 1/100 . yffGfffffff ffffff ff ff x 6r `0 ,$ 0 Many exciting results, applications and connections [Z,NZ,Ta,Tr,RSW,STV,TSZ,SU,& ]. *TS]Q]Q5 x 6r  `  ,$ 0 jThm [LRVW]: For every n,k there s a seeded extractor with d=O(log n)E  ff! ff6#R x 6r  ` ,$ 0 dCorollary: Any probabilistic algorithm can be simulated w/ weak random source + polynomial overhead.8e Yf2l 0   x0 ,$D 0 x BGH 0  <   x 6   vX has min-entropy k (denoted H(X)k) if 8x Pr[ X=x ] 2-k. Every such dist is convex comb of  flat dist  uniform dist on set of size 2k. In this talk: entropy = min-entropyf ffffff ffffPfff(f  x 6 p L Definition : E:{0,1}n{0,1}0.1k is an extractor if 8 r.v. X with entropy k , E(X) is close to U0.1kff  f f f f      f  f  f f  f   f f fH x 0޽h ?x +T3f3f##___PPT10#.s+`ިD!' = @B Dj!' = @BA?%,( < +O%,( < +DD' =%(D' =%(D' =A@BBBB0B%(D' =+4 8?`CB ppt_xBCB1+ppt_w/2B*Y3>B ppt_x<* xD ' =+4 8?XCB ppt_yBCB ppt_yB*Y3>B ppt_y<* xD' =1:Bhidden*o3>+B#style.visibility<* x%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*xD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*xD' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<* x%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* xD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* xD' =-g6B fade*<3<* xD' =%(D' =%(D)' =4@BB BB%(D' =-g6B fade*<3<* xD' =1:Bhidden*o3>+B#style.visibility<* x%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x%(Dz ' =%(D" ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*xD' =1:Bhidden*o3>+B#style.visibility<*x%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*xD' =1:Bhidden*o3>+B#style.visibility<*x%(D$' =A@BB@BB0B%()?)?Dk' =.37 BBBBBEM 0.0 -2.89017E-6 L 0.0 -0.37734 *3>*B ppt_xB ppt_y=@0BBAApBBB2A<*xD"' =A@BB@BB0B%()?)?Di' =.17 BBBBBCM 0.0 1.38728E-6 L 0.0 -0.37734 *3>*B ppt_xB ppt_y=@0BBAApBBB2A<*x++0+x ++0+x ++0+x ++0+x ++0+x ++0+x ++0+x ++0+x ++0+ x +   |&(  | | BX `p    | 6HY p` p jThm [LRVW]: For every n,k there s a seeded extractor with d=O(log n)E  ff! ff6# | 6c `  dCorollary: Any probabilistic algorithm can be simulated w/ weak random source + polynomial overhead.8e YfL  | 6(i `  ,$ 0 ^Question: What about other uses of randomness? For example, can we use this for cryptography?8_ T  | 6n  ` ,$ 0 :Answer: No! For example, if we concatenate encryptions according to all possible seeds this won t be secure! Dnbf"  | 6u  `P,$ 0  Need to use seedless extractors!L! ]Q ]Q]QH | 0޽h ? +T3f3f  ___PPT10 .s+_S1D ' = @B D ' = @BA?%,( < +O%,( < +D$' =%(D' =%(Dt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* |%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* |D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* |D' =-g6B fade*<3<* |DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* |%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* |%(++0+ | ++0+ | ++0+ | +.  B :   (    B `p     6 `  \Idea: Bypass impossibility result by making additional assumption on the high entropy input.8]VfU  0 "``` ,$ 0 SIn this work: We assume that input comes from few independent distributions ([CG]).DT>8  64 `,$ 0 6Long history and many results [vN,P,B,SV,CW,TV,KZ,..] *76]Q]Q(  6Ĭ  ` ,$ 0 Def: E:{0,1}nc{0,1}0.1k is a c-sample extractor if 8 ind. r.v. X1,& ,Xc w/ min-entropy k | E(X1,& ,Xc)  U0.1k |1 < 1/1002~ffff f ffffff ffffffff ffff>7 l     p  ,$D 0  <h     | 2-W(k)Tffff`B  B 0D| )  0L "`@`P,$ 0 5Motivation: mathematically clean and plausible model.66 *H  0޽h ? +T3f3f"!___PPT10!.s+NeD' = @B D=' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D1' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D$' =A@BB@BB0B%()?)?Dk' =.37 BBBBBEM 0.0 -4.21965E-6 L 0.0 -0.52161 *3>*B ppt_xB ppt_y=@0BBAApBBBʈ<* D' =4@BB@BB%()?)?Ds' =.;7 BBBBBMM 0.0 -3.81503E-6 L 0.00417 -0.52161 *3>*B ppt_xB ppt_y=@0BBAApBB;Bʈ<* +0+0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+  ++0+  ++0+  ++0+  +    ! (    0 "`PP`,$ 0 >zOptimal (non-explicit) construction: c=2 , every kW(log n)>'ffGffff3  6l  0  Def: E:{0,1}nc{0,1}0.1k is a c-sample extractor if 8 ind. r.v. X1,& ,Xc w/ min-entropy k | E(X1,& ,Xc)  U0.1k |1 < 2-W(k)Zffff f ffffff ffffffff ffffff>7   0H) "`0 ,$ 0 XPrevious best explicit construction [SV,V,CG,ER,DEOR]: c=2 , every k(1+e)n/2N7ffGffffff  04 "` ` ,$ 0 IObtained by variants of following 1-bit output extractor: E(x,y) = FJ:ff,;P  0; "`` ,$ 0 LProblematic, since natural entropy sources often have entropy less than n/2.FMHfH  0޽h ? +T3f3f___PPT10.s+DV' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D$' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(+P+0+ ++0+  ++0+  ++0+  ++0+ ++0+ +M&  80  (    6b 0  Def: E:{0,1}nc{0,1}0.1k is a c-sample extractor if 8 ind. r.v. X1,& ,Xc w/ min-entropy k | E(X1,& ,Xc)  U0.1k |1 < 2-W(k)Zffff f ffffff ffffffff ffffff>7   0~ "`  ,$ 0 bZOur Result: For every d>0 c=poly(1/d) , k=dn.  ff fffffffl 0 p  0 p,$D 0n"   0o"`0   0 "`0 p tMain Thm: 8 d>0 9 c=poly(1/d) and poly-time E:{0,1}nc{0,1}n s.t. if 8 ind. r.v. X1,& ,Xc w/ min-entropy dn | E(X1,& ,Xc)  Un |1 < 2-W(n) GffG fffffff f fffffff ffffffff ffffffb6    0 "`PP` >zOptimal (non-explicit) construction: c=2 , every kW(log n)>'ffGffff3  0 "`0  XPrevious best explicit construction [SV,V,CG,ER,DEOR]: c=2 , every k(1+e)n/2N7ffGffffffH  0޽h ? +T3f3f___PPT10.s+WޞDQ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* D ' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D3' =4@BB@BB%()?)?D' =.O7 BBBBBaM 3.33333E-6 -3.00578E-6 L 3.33333E-6 -0.67699 *3>*B ppt_xB ppt_y=@0BBAApBBB~O<* ++0+ ++0+ ++0+ ++0+  ++0+  +      (  f"  0o"``   0 "``  tMain Thm: 8 d>0 9 c=poly(1/d) and poly-time E:{0,1}nc{0,1}n s.t. if 8 ind. r.v. X1,& ,Xc w/ min-entropy dn | E(X1,& ,Xc)  Un |1 < 2-W(n) GffG fffffff f fffffff ffffffff ffffffb6    B  ``   2  0@ "`   N3. Introduce main tool  Thm by [BKT,K]8( $     0 "` 0 p4. Prove our main theorem.:     0 "` 0  b1. Discuss problem and model*    0 "`p  Y2. State our result*    0| "`p   1Show BKT (almost) immediately implies dispersers.H2&   0% "`  B H  0޽h ? +T3f3fnf___PPT10F.s+D' = @B DM' = @BA?%,( < +O%,( < +D' =%(D,' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D`' =K@BB BBPB0B%(/%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(++0+  ++0+  ++0+ ++0+ ++0+ ++0+ ++0+ +0  E= (  f"  0o"``   0X^ "``  tMain Thm: 8 d>0 9 c=poly(1/d) and poly-time E:{0,1}nc{0,1}n s.t. if 8 ind. r.v. X1,& ,Xc w/ min-entropy dn | E(X1,& ,Xc)  Un |1 < 2-W(n) GffG fffffff f fffffff ffffffff ffffffb6    0D "`P,$ 0 n&Our main tool is the following result:,'&Z  0 "`0 ,$ 0 Thm 1 [BKT,K]: 9 absolute constant e>0 s.t. for prime field F, and set AF, max{ |A+A| , |A A| } min{ |A|1+e , |F| } x}Gffff fGfffGffGf fffff$%R  0 "` P,$ 0 1. Finite field analog of a theorem by [ES]. 2. Note Thm 1 would be false if F had non-trivial subfields. 3. Note if A is arithmetic (resp. geometric) sequence, then |A+A| (resp. |A A|) is small.Nf(f5ffGff >6O(  0 "`@ ,$ 0 V4A+A = { a+b | a,b 2 A } A A = { ab | a,b 2 A }5fGffGffGf fGfffP 8l       ,$D  0ZB   s *Do 0 ZB   s *Do  H  0޽h ? +T3f3f3 + ___PPT10 .s+`D' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(left)*<3<* D' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D"' =A@BB@BB0B%()?)?Di' =.17 BBBBBCM 0.0 2.36994E-6 L 0.0 -0.38289 *3>*B ppt_xB ppt_y=@0BBAApBBB. D<*D' =4@BB@BB%()?)?Dg' =./7 BBBBBAM 0.0 1.7341E-7 L 0.0 -0.38844 *3>*B ppt_xB ppt_y=@0BBAApBBBF<* ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ +7    @l (     0l "` ,$ 0 j"How is this related to extractors?,#"  0 "``P rThm 1 [BKT,K]: 9 absolute constant e>0 s.t. for prime field F, and set AF, max{ |A+A| , |A A| } |A|1+eNoGffff fGfffGffGffff$%D  0 "`,$ 0 &0Disperser Lemma [BKT]: Let d>0 and F a prime field, then 9c=poly(1/d) and poly-time E:FcF s.t. if X1,& ,XcF satisfy |Xi| |F|d, then E(X1,& ,Xc) = FffffGf ffffff ffffff ffffffffffffPV "h  0 "` P,$ 0 hCorollary: Identify {0,1}n w/ prime field F of size 2n. Then, we get poly-time E s.t. if r.v. s X1,& ,Xc have entropy dn, then Supp{E(X1,& ,Xc)}={0,1}n This is called a disperser.  fff fffffffGffffffffff PQ%&H  0޽h ? +T3f3f  ___PPT10 .s+ܙED ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(++0+ ++0+ ++0+ ++0+ +:  P (    0J "`  j"How is this related to extractors?,#"  0Q "``P rThm 1 [BKT,K]: 9 absolute constant e>0 s.t. for prime field F, and set AF, max{ |A+A| , |A A| } |A|1+eNoGffff fGfffGffGffff$%D  0g "` 0Disperser Lemma [BKT]: Let d>0 and F a prime field, then 9c=poly(1/d) and poly-time E:FcF s.t. if X1,& ,XcF satisfy |Xi| |F|d, then E(X1,& ,Xc) = FrffffGf ffffff ffffff ffffffffffffPV "  0 "` @ ,$ 0 ~Proof: Use lemma of Rusza to get  asymmetric version of Thm 1.:@8,   0 "`@ P ,$ 0 8Lemma [R,N]: If A,B G w/ |A|=|B|=M, and |AB| M1+e, then |AA| M1+O(e)M fGff ffGffGfffffGffGfffffD  0  "``P,$ 0 Thm 1 [BKT,K]: 9 absolute constant e>0 s.t. for prime field F, and sets A,B,CF, (with |A|=|B|=|C|) |AB+C| |A|1+ejyGffff fGff ffGffGffff$%NN  0T "`P P,$ 0 We let E be recursive application of a,b,cab+c with depth O(log(1/d)). Jfffff  ffff%   0t "` ,$ 0 +W|A A| large ) |A B| large ) |AB+C| large |A+A| large ) |A+C| large ) |AB+C| largeXfGffGfGfffGfGfffGfGfGffH  0޽h ? +T3f3f$$___PPT10v$.s+?l[6D!' = @B De!' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(DL' =%(D' =A@BBBB0B%()))D' =+4 8?`CB ppt_xBCB1+ppt_w/2B*Y3>B ppt_x<*D ' =+4 8?XCB ppt_yBCB ppt_yB*Y3>B ppt_y<*D' =1:Bhidden*o3>+B#style.visibility<*%(D' =A@BBBB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*D' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+  ++0+  +ta   //CF.(  B  0D| ,$@ 0B  0D| ,$@ 0B  0D|P ,$@ 0|z p    0 p ,$D  0`B  0D|p p `B  0D|p  `B  0D|p     0D "`   b DEfG   0< "`` P  d+ FFfG|z 0 p `   0 0p ,$D  0`B  0D|0 p  `B  0D|0p 0 `B  0D|p `   0t "`   b DEfG  0l  "`` P  d+ FFfG|z P   p P ,$D 0`B  0D|P `B  0D| `B  0D|   0& "`  b DEfG  0+ "`@` d+ FFfG|z    p   ,$D 0`B  0D| `B  0D| `B  0D|0   01 "`  b DEfG  06 "`@` d+ FFfG|z       ,$D 0`B ! 0D| `B " 0D| `B # 0D|0  $ 0= "`.N b DEfG % 0A "`p  d+ FFfG|z   &  P ,$D 0`B ' 0D| 0 `B ( 0D|` ` `B ) 0D|  * 04H "`@ .0 N b DEfG + 0,M "`0 p  d+ FFfG|z   ,   ,$D 0`B - 0D| ``B . 0D| `B / 0D|  0 0dS "`p.`N b DEfG 1 0\X "``pP d+ FFfG|z   2   ,$D  0`B 3 0D| ``B 4 0D| `B 5 0D|  6 0^ "`p.`N b DEfG 7 0Hc "``pP d+ FFfG> 8 0(h "` ,$ 0 a1 , a2, & j ffffff 9 0o "`  ,$ 0 fapoly(1/delta)<f ff : 08u "`p` ,$  0 O.2   ; 0ty "`0 ,$  0 O.2   < 0} "` ,$ 0 O.2   = 04 "`p`` ,$ 0 O.2   > 0 "`P ,$ 0 O.2   ? 0 "` ,$ 0 O.2  B @ 0D|  ,$@ 0 A 0 "` ,$ 0 O.2   B 0$ "` @ ,$ 0 O.2   C 0 "` P ,$ 0 O.2   D 0 "`` P ,$ 0 ?" f E 0 "`  ,$ 0 ;+f F 0L "``P Thm 1 [BKT,K]: 9 absolute constant e>0 s.t. for prime field F, and sets A,B,CF, (with |A|=|B|=|C|) |AB+C| |A|1+ejyGffff fGff ffGffGffff$%NH  0޽h ? +T3f3f22___PPT101.s+CD.' = @B D.' = @BA?%,( < +O%,( < +D2' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*&%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*2%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D> ' =%(D ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*:%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*;%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*?%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*>%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*=%(D' =%(D}' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*A%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*B%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*C%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*E%(++0+8 ++0+9 ++0+: ++0+; ++0+< ++0+= ++0+> ++0+? ++0+A ++0+B ++0+C ++0+D ++0+E +   (      B\) `@`   $   0* "` N3. Introduce main tool  Thm by [BKT,K]*('      0/ "`P `  p4. Prove our main theorem.:      04 "` b1. Discuss problem and model*     09 "` Y2. State our result*     0> "`p   1Show BKT (almost) immediately implies dispersers.H2& H   0޽h ? +T3f3f___PPT10i.s+D=' = @B +8#    `  (    BZ `p   j  0L` "` @ ,$ 0 vOur Main Lemma: 9 absolute constant e>0 s.t. for prime field F, and distributions A,B,CF, (with H(A)=H(B)=H(C)), the distribution AB+C is 2-eH(A) close to having entropy (1+e)H(A)GfffffGfff fGffffffffGfffff)'  0z "`,$ 0 Main Lemma ) Main Theorem. N G  0 "` Thm 1 [BKT,K]: 9 absolute constant e>0 s.t. for prime field F, and sets A,B,CF, (with |A|=|B|=|C|) |AB+C| |A|1+ejyGffff fGff ffGffGffff$%N  0P "` ,$ 0 RV( The distribution AB+C assigns to x the prob that ab+c=x with a2RA , b2RB , c2RC )WfGff ffGfffGfNfffGfNfffGfNff,*H  0޽h ? +T3f3f___PPT10.s+s #D' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D ' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D@' =A@BB@BB0B%()?)?D' =.O7 BBBBBaM 3.33333E-6 -1.56069E-6 L 3.33333E-6 -0.41063 *3>*B ppt_xB ppt_y=@0BBAApBBB>R<* D>' =A@BB@BB0B%()?)?D' =.M7 BBBBB_M -1.11022E-16 4.79769E-6 L -0.00417 -0.57157 *3>*B ppt_xB ppt_y=@0BBAApBBBQ<* ++0+  ++0+  ++0+  ++0+  ++0+  ++0+  ++0+  ++0+  +6  ^-V-EK0,(  06 0 04 "``@@ vOur Main Lemma: 9 absolute constant e>0 s.t. for prime field F, and distributions A,B,CF, (with H(A)=H(B)=H(C)), the distribution AB+C is 2-eH(A) close to having entropy (1+e)H(A)GfffffGfff fGffffffffGfffff) 0 0 "`@ Main Lemma ) Main Theorem. N G}'l 0  H00 ,$D 0`B 0 0D|  `B 0 0D| ` `B  0 0D| PN p    0 p @P `B  0 0D|p p `B  0 0D|p  `B  0 0D|p   0 0 "`   b DEfG 0 0 "`` P  d+ FFfGPN 0 p `  0 p P `B 0 0D|0 p  `B 0 0D|0p 0 `B 0 0D|p `  0 0  "`   b DEfG 0 0  "`` P  d+ FFfGPN P  0 P ```B 0 0D|P `B 0 0D| `B 0 0D|  0 08 "`  b DEfG 0 0t "`@` d+ FFfGPN   0 P ``B 0 0D| `B 0 0D| `B 0 0D|0   0 0 "`  b DEfG !0 0l "`@` d+ FFfGPN   "0  `B #0 0D| `B $0 0D| `B %0 0D|0  &0 0d$ "`.N b DEfG '0 0d) "`p  d+ FFfGPN   (0  `B )0 0D| 0 `B *0 0D|` ` `B +0 0D|  ,0 0/ "`@ .0 N b DEfG -0 04 "`0 p  d+ FFfGPN   .0 P `B /0 0D| ``B 00 0D| `B 10 0D|  20 0: "`p.`N b DEfG 30 0? "``pP d+ FFfGPN   40 P `B 50 0D| ``B 60 0D| `B 70 0D|  80 0E "`p.`N b DEfG 90 0J "``pP d+ FFfG :0 0O "`0`0 a1 , a2, & j ffffff ;0 0 W "` p  O.2   <0 0D[ "`p` `  O.2   =0 0_ "`   O.2   >0 0c "` @  O.2   ?0 0h "` 0   O.2   @0 0$l "`` P  O.2  `B A0 0D|   B0 0p "`  p  O.2   C0 0t "`P p @  O.2   D0 0(y "`  0  O.2   E0 0L} "`  ?" f F0 0 "`P @  ;+f G0 0 "` `  fapoly(1/delta)<f ffH 0 0޽h ? +T3f3f___PPT10.s+#,Da' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*H0%(D' =%(D' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*H0D' =1:Bhidden*o3>+B#style.visibility<*H0%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*0D' =1:Bhidden*o3>+B#style.visibility<*0%(+8+0+0 +  .&p9(  6 6 0  "``@@ vOur Main Lemma: 9 absolute constant e>0 s.t. for prime field F, and distributions A,B,CF, (with H(A)=H(B)=H(C)), the distribution AB+C is 2-eH(A) close to having entropy (1+e)H(A)GfffffGfff fGffffffffGfffff) 7 B `p    8 0 "`P  <Prove Main Lemma by reducing to [BKT]. We use  magic lemmas of Gowers & Rusza in the reduction.*ba  ,AH  0޽h ? +T3f3f___PPT10i.s+D=' = @B +  e ]  (  6  0 "``@@ vOur Main Lemma: 9 absolute constant e>0 s.t. for prime field F, and distributions A,B,CF, (with H(A)=H(B)=H(C)), the distribution AB+C is 2-eH(A) close to having entropy (1+e)H(A)GfffffGfff fGffffffffGfffff)  BH `p     0 "` ,$ 0 1. Introduce collision probability  a different entropy measure. dD    0 "`  ,$ 0 {'2. Rephrase Main Lemma in terms of C.P.8($0  0< "`  ,$ 0 :3. Show nave approach to proving, and show counterexample8;7  0 "`p,$ 0 24. Use Gowers & Rusza s lemmas to show counterexample essentially captures all cases8VR,>H  0޽h ? +T3f3f^ V ___PPT106 .s+D* ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+ ++0+ ++0+ ++0+ +     (    0L% "`@,$ 0 RDcp(X) = Prx,x X[ x= x ] = x px2# ffff fffffff$  B0 `p     04 "` ,$ 0 &Fact 3: If X is convex combination of X1,& ,Xm then cp(X) max { cp(X1), & , cp(Xm) }X fffffffGf ff ffff>,  0DD "`pp,$ 0 !Fact 1: If H(X)k then cp(X)2-k" fGfffGfff   0Q "`p@,$ 0 Fact 2: If cp(X)2-k(1+e) then is 2-ek/2 close to having min-entropy at least k(1+e/2). F[ fGffffffffff'ffff  0a "`@ ,$ 0 OINotation: If D is r.v., then the 2-entropy of D is H2(D) = log(1/cp(D))J f fffff4|  0n "`@  ,$ 0 Fact 1 + Fact 2 ) H2(D) ~ H(D)Gff ffH  0޽h ? +T3f3f`X___PPT108.s+*D' = @B Dw' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(+P+0+ ++0+ ++0+ ++0+ ++0+  ++0+ +/    4E (    0 "`` (Main Lemma: 9 e>0 s.t. for prime field F, dists A,B,CF, (with H(A)=H(B)=H(C), the distribution AB+C is 2-eH(A) close to entropy (1+e)H(A) Gffff fGfff fGffffffffGfffff,c2 2 6@ ,$D  0L 3 0 "` ` ,$ 0 ZMain Lemma (CP version): 9 e>0 s.t. for prime field F, and sets A,B,CF (with |A|=|B|=|C| ), the distribution AB+C is |A|-e close to having 2-entropy (1+e)log |A|Gffff fGff f fGffffff Gffff! 4 0l "``0,$ 0 u+Thus, it is sufficient to prove CP version..,+H  0޽h ? +T3f3f"___PPT10.s+)D' = @B Dq' = @BA?%,( < +O%,( < +D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*3%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*2%(D' =-s6Bwipe(down)*<3<*2DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D ' =%(D' ' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*2D' =1:Bhidden*o3>+B#style.visibility<*2%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*4D' =1:Bhidden*o3>+B#style.visibility<*4%(D"' =A@BB@BB0B%()?)?Di' =.17 BBBBBCM 0.0 4.91329E-6 L 0.0 -0.54937 *3>*B ppt_xB ppt_y=@0BBAApBBB!<*3++0+ ++0+3 ++0+3 ++0+4 ++0+4 +   + #   (    B `p   X  0 "`  1. Introduce collision probability  a different entropy measure. HD !  0 "`   m'2. Rephrase Main Lemma in terms of C.P.*('  0D "`   :3. Show nave approach to proving, and show counterexample8;7  0 "`p $4. Use Gower s and Rusza s lemmas to show counterexample essentially captures all cases8XT>   0 "``` ZMain Lemma (CP version): 9 e>0 s.t. for prime field F, and sets A,B,CF (with |A|=|B|=|C| ), the distribution AB+C is |A|-e close to having 2-entropy (1+e)log |A|Gffff fGff f fGffffff Gff f!H  0޽h ? +T3f3f___PPT10i.s+D=' = @B +V&  d \   (    BA `p     00C "`p P,$D 0 dProve direct analog to BKT.    0I "`  P,$ 0 x Conjecture : 9 e>0 s.t. for prime F, and set AF max { H2(A+A) , H2(A A) } (1+e)log|A|~_Gffff fGffff fffGffGfffffG  0_ "`  ,$ 0 |RCounter Example: A=AG [AA AG - geometric seq. AA - (disjoint) arithmetic seq. SfNffGff N ffNffNf  f    f  0l "` ,$ 0 4^However, in this case H2(A A+A) (1+e)log |A|0fffGffGfffff  0w "` P ,$ 0 H:cp(A+A),cp(AA)1/10|A| hence H2(A+A), H2(AA)log|A|+O(1); fGffGfffffffGffGf fH  0޽h ? +T3f3f___PPT10r.s+PDN' = @B D ' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D ' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D8' =A@BB@BB0B%()?)?D' =.G7 BBBBBYM 3.33333E-6 1.7341E-7 L -0.00348 -0.37734 *3>*B ppt_xB ppt_y=@0BBAApBB9㺐B2A<* ++0+ ++0+  ++0+  ++0+  ++0+  ++0+  ++0+  ++0+  ++0+  +  . &   (    B@ `p     0\ "`p0 xRCounter Example: A=AG [ AA AG - geometric seq. AA - (disjoint) arithmetic seq.  SffGfffffffNffff  0  "` ,$ 0 (DClaim: H2(AA + A) (1+e)log |A|#fffGffGfffff  0 "`  ,$ 0 s3Sketch: AA+A is convex comb of AA A+A and AGA+A.$4fGfffNffGfff N fGff]   0 "`  ,$ 0 A cp(AA A+A) cp(AAA) which is low since A is an arithmetic seqBfNfOfGffGff N fGfffOf>)   0 "`,$ 0 T AGA+A is convex comb of AGa+A but cp(AGa+A) is low since AGa is a geometric seq<UfNfGfff N fffNff fNf  f  PH  0޽h ? +T3f3f^ V ___PPT106 .s+cD* ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(++0+ ++0+ ++0+  ++0+  +7  %   (    B `p   X  00 "`  1. Introduce collision probability  a different entropy measure. HD !  0% "`   m'2. Rephrase Main Lemma in terms of C.P.*('  0) "`   :3. Show nave approach to proving, and show counterexample*;:  0p. "`p 64. Use Gowers and Rusza s lemmas to show counterexample essentially captures all cases8XT,>  08 "``p JMain Lemma: 9 absolute constant e>0 s.t. for prime field F, and sets A,B,CF (with |A|=|B|=|C| ), the distribution AB+C is |A|-e close to having c.p. |A|-(1+e) Gffff fGff f fGfffffffGffff,%n H  0޽h ? +T3f3f___PPT10.s+D' = @B D' = @BA?%,( < +O%,( < +D' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D"' =A@BB*BB0B%()?)?Di' =.17 BBBBBCM 0.0 -1.38728E-6 L 0.0 0.18312 *3>*B ppt_xB ppt_y=@0BBAApBBB,=<*+P+0+ ++0+ ++0+ ++0+ ++0+ ++0+ +  |(    Bw `p     s *y "` ,$ 0 Z(Loose) Notations:,  0D "`@  ,$ 0 BA number M1+e is called  large A number M1-W(e) is called  not-too-small A distribution D has  high 2-entropy if H2(D) (1+e)log M   Gffff  Gfffffff ffffGffffff$  0D "`` zMain Lemma (CP version): 9 absolute constant e>0 s.t. for prime field F, and sets A,B,CF (with |A|=|B|=|C| ), the distribution AB+C is |A|-e close to having 2-entropy (1+e)log |A|Gffff fGff f fGffffff Gff f3  0 "`@,$ 0 Our Goal: Prove that AB+C is close to having high 2-entropy. (i.e., it is close to having c.p. 1/M1+e)j  fGffFGffff[   s *l "` p ,$ 0 dLet M=|A|=|B|=|C| and fix some e>0 (e.g., BKT s e divided by 100)B fff f*H  0޽h ? +T3f3f^ V ___PPT106 .s+fD* ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+  ++0+  ++0+ ++0+ +s  (    B `p     0\ "` VNThm 1 [BKT,K]: If AF is not too small then either |AA| or |A+A| is large. OfGfffGfff fLp  0 "`( 4Lemma [R,N]: If |AA| is large then |AB| is large.5 fGfffGff   0  "`P  Magic Lemma [G,BS]: Either H2(AB) is large or 9 not-too-small subsets A A, B B s.t. |A B | is not large.vp fffGffGfGfffGfffGff ffTH  0޽h ? +T3f3f___PPT10i.s+D=' = @B +0   (  X  04 "`p0,$ 0 `Cor [BKT+R]: If 9 not-too-small B s.t. |AB| is not large then |A+C| is large 8 not-too-small C.a GfffGfff Gfff$<  B C `p     0F "`@0,$ 0 `Proof: |AB| is not large ) |AA| is not large [R] ) |A+A| is large [BKT] ) |A+C| is large [R].nafGffGfGffGf Gff  0,[ "`0P ,$ 0 gNatural Analog: If 9 not-too-small B s.t. H2(AB) is not large then H2(A+C) is large 8 not-too-small C.JhGfffffGfffff Gfff%@  0l "` 0 ,$ 0 !This is false: e.g., A=B=C=AG [AA"ffNffGff N f-  0w "`0 ,$ 0 However, the following is true:P  k  0 "`0P,$ 0 _PF Lemma: If 9 not-too-small B s.t. |AB| is not large then H2(A+C) is large 8 not-too-small C.,` GfffGfffff Gfff>H  0޽h ? +T3f3f6"."___PPT10".s+zuD ' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DF' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D"' =A@BB@BB0B%()?)?Di' =.17 BBBBBCM 0.0 4.62428E-7 L 0.0 -0.82127 *3>*B ppt_xB ppt_y=@0BBAApBBB>Ҿ<*++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ +#  0 (      0 "` ` ,$ 0 Def: A not-too-small set AF is  plus friendly if H2(A+C) is large 8 not-too-small set C. >^fGfffffGf Gfff:   0 "` ,$ 0 Proof: If H2(A+C) is not large then by Gowers s Lemma 9 not-too-small A A, C C s.t. |A +C | is not large. hqfffGGfGfffGfff,)#7   00 "``` _PF Lemma: If 9 not-too-small B s.t. |AB| is not large then H2(A+C) is large 8 not-too-small C.,` GfffGfffff Gfff>L   0D "`` ,$ 0 By Rusza s lemma |A +A | is not large ) by BKT |A A | is large. C fGfGff 9   0 "` `` ,$ 0 Since A A , |AA| is also large ) by Rusza s lemma |AB| is large  contradiction! VfGfffGffG fGff('   00 p0 ,$D 0    0 "` `,$ 0 h1. A plus-friendly, b2F ) Ab plus-friendly. 2. A , A  plus-friendly, disjoint ) A [A  plus-friendly. Xj]Qf]QfGff]QG]Qf]Qf]Qf]QG]QfGff]Q]QNB   c $D  ,$D 0H   0޽h ? +T3f3f___PPT10.s+pD;' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* q%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D ' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(++0+  ++0+  ++0+  ++0+  ++0+  +)  y (    0Y "`p $bOur Goal: Prove AB+C close to having  low c.p. .2 fGff+  0(e "` ,$ 0 T1+2 ) contradiction since AB+C is M-e close to convex comb of A+B+C and AB+C, butWGfGfffffffGfffO fGffV  0z "`  ,$ 0 La) H2(A+B+C) is large since convex comb of A+b+C and A+b is plus-friendly.MffffGff ffffff,-I  0 "`P ,$ 0 Qb) H2(AB+C) is large since convex comb of AB+c which are permutations of AB.RfffO fGff fO fffO ff-   08 "`@,$D 0 Assume H2(AB+C) not large. We ll show A=A+[A s.t. A+,Aare disjoint and 4KfffGffffGffO ffffO f,/  0, "`Pp,$ 0 T1) A+ is  plus friendly (or A+ is empty) +ffff 6  0 "`ppP,$ 0 L2) H2(A B) is large (or |A| M1-e) ,'fffO ffGff fOffGffffH  0޽h ? +T3f3f-%___PPT10.nK+DD' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* K%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(Db' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(++0+ ++0+ ++0+ ++0+ ++0+  ++0+  ++0+  ++0+  +-#  @ J(    00 "`p $bOur Goal: Prove AB+C close to having  low c.p. .2 fGff+p  0 "`@ Assume H2(AB+C) not large. We ll show A=A+[A s.t. A+,A disjoint and 4IfffGffffGffO ffffO f0^  0 "`Pp T1) A+ is  plus friendly (or A+ is empty) +ffff   0 "`ppP L2) H2(A B) is large (or |A| M1-e) ,'fffO ffGff fOffGffff   0 "`` ,$ 0 6We build partition iteratively. Initially A+=; , A=A.7*fffGffO ff   0T  "``  ,$ 0 ZAssume A is not-too-small (o/w we re done). L.fO f%   0 "`  ,$ 0 "By Gowers lemma, 9 not-too-small subsets A A, B B s.t. |A B | not large. 2Q GffGffO ffGfffGff ,.   0$ "` ,$ 0 rBy PF Lemma A is plus-friendly, remove A from A and add it to A+.FfffO fff   B@1  ,$ 0 6^Assume H2(AB) is not large (o/w we re done).0fffO fGff!  s *"``P,$D 0H  0޽h ? +T3f3f___PPT10.nK+'D' = @B Dj' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+  ++0+  ++0+  ++0+  ++0+  +  N F 0  (  f"  0o"``0 f"  0o"`   0  "` P tMain Thm: 8 d>0 9 c=poly(1/d) and poly-time E:{0,1}nc{0,1}n s.t. if 8 ind. r.v. X1,& ,Xc w/ min-entropy dn | E(X1,& ,Xc)  Un |1 < 2-W(n) GffG fffffff f fffffff ffffffff ffffffb6    0, "`0 EThis finishes the proof of the Main Lemma and hence the Main Theorem..FEB  0l5 "`@`  Main Lemma: 9 absolute constant e>0 s.t. for prime field F, and distributions A,B,CF, (with H(A)=H(B)=H(C)<0.8log|F|), the distribution AB+C is 2-eH(A) close to having entropy (1+e)H(A) GfffffGfff fGffffffffGfffff%B  s *Dop@,$D  0  0O "`R(h,$ 0 a2-10n@fffH  0޽h ? +T3f3frj___PPT10J.s+$D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(left)*<3<* D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(+8+0+  +}  @$(  r  S xk` `0   r  S Ll```   H  0޽h ? +T3f3f___PPT10i.!8]+D=' = @B +  P0(  x  c ${` `P   x  c $x|`  `  H  0޽h ? +T3f3f___PPT10i.!8]+D=' = @B +r"(1CsH0_R@>m?ć041TEG!J$0Cc(pi9uQ 1 x+lK5u? jJ6 Oh+'0T hp    $083Extracting Randomness From Few Independent SourcesiBoazcti Texturedg RBoazred286Microsoft PowerPoint Fr@6Dx@N@л*PGSg  )'    """)))UUUMMMBBB999|PP3f333f3333f3ffffff3f̙3ff333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffff3ffff̙fff3fffff3fff333f3f3ff3ff33f̙̙3̙ff̙̙̙3f̙3f333f3333f3ffffff3f̙3f3f3f333f3333f3ffffff3f̙3f3ffffffffff!___www4'A x(xKʦ """)))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___wwwmmlmrllllmmllmmlmrllllrmqlmmlllllrmlmmmlllmmmmqmmmllmmmmqmmmlmmrmlmmmmllmmmmlmlmmmmlmmmlmrmlrmlmmmrmlmrmlmrmmmmmmrmmmmlmmmmlmrmlmmmmlmmmmmmlmmmmmmmmlmmmmqmrrrrmmqmrrmmmmmrmmmlmmrrlmllmmrrlmmmmlmmmrmmrmmmmrmmrrrmmrmmqrmmmmmϮϑϋϐϮmϋϑϑϑϑϑϑϐϋϮϐϑϑϮϮϮϑϮϮϮϮϮϮϐϮϑϑϑϑϑϑϑϮϑϑϑϮϑϮϑϑϑϋϮϑϑϮϋϮϑϐϑϑϋϮϋϐϑϮϮϑϑϑϑϮϑϑϮϑϑϮϐϑϐϮϋϑϋϮϐϑϑϋϋϑϑϐϑϑϋϑϑϑϑϋϑϑϮϑϋϐϋϑϮϑϑϮϑϮϑϮϮϑϋϮϮϑϋϑϑϑϑϑϑϐϑϮϮϑϐϮϑϑϐϮϮϮϮϑϮϑϋϑϑϐϮϮϑϑϐϑϐϑϮϮϮϑϮϮϑϮϑϴϮϑϮϋϮϑϑϮϑϑϮϑϑϮϮϮϑϑϐϮϑϐϮϑϑϮϋϑϮϑϑϑϮϮϑϑϮϑϑϑϑϑϮϐϮϑϑϮϑϮϐϴϑϮϑϑϮϑϑϑϑϮϋϮϑϑϑϮϋϮϑϮϑϐϑϮϮϑϑϐϑϑϮϑϑϮϐϑϮϑϑϑϐϮϑϑϑϐϑϑϑϑϑϑϒϑϐϑϮϑϑϑϑϑϮϮϑϮϐϑϑϑϋϑϮϋϐϐϋϑϮϑϮϋϮϑϋϋϐϑϮϐϮϐϑϮϮϐϮϮϑϮϐϮϮϑϐϮϑϑϑϑϑϮϑϮϑϑϑϑϮϋϮϮϮϮϑϮϮϑϑϑϑϮϮϮϮϮϋϑϑϋϑϑϑϑϑϐϑϑϐϮϑϑϑϑϑϑϮϑϑϑϑϑϮϑϐϐϑϮϮϐϮϑϮϑϐϮϮϑϮϑϑϑϑϮϮϑϋϑϐϑϮϑϑϑϑϮϑϑϑϑϋϑϑϑϮϑϑϮϑϑϑϑϑϐϑϐϮϐϑϮϑϑϐϐϑϐϮϐϑϑϑϳϑϑϑϑϑϮϑϑϮϑϮϑϮϮϑϑϑϮϑϑϑϮϑϑϮϑϑϑϐϮϑϑϑϐϑϑϑϮϮϮϐϑϐϑϮϑϮϐϮϑϑϐϐϑϑϑϐϑϮϑϮϐϮϐϑϑϑϐϑϐϐϑϑϑϮϑϑϐϐϮϑϑϐϑϮϑϑϮϑϑϑϑϮϑϑϑϑϑϑϑϑϮϑϮϑϮϮϑϮϑϑϑϑϮϮϑϮϑϑϑϑϮϮϑϑϮϑϮϮϑϑϑϮϮϑϑϋϑϐϑϑϮϐϐϑϴϮϑϑϮϐϑϑϴϑϑϮϑϑϑϑϑϮϐϑϑϑϮϑϮϑϑϮϑϑϑϋϑϑϑϮϮϐϐϐϑϑϮϑϑϑϮϮϐϑϑϑϮϮϑϮϋϮϮϑϑϮmϑϮϋϑmϮϐlrmrrmmmmmrmmmrrmmmmmmlmrrqlmrqrmmmllmqrmmmllmmmrmmmlmmmmmrmmmlmmmmmlmmmmmmqmmmlrmmmqmmlmrmmmlqrlmmlqmmlmlqmmmrlmqmllmmlmmmrlmllmmlmllmmlmmmrlmrmlmmmmrlmrmmlllmllmmlllmmlrmlmlmllmmlmlmmlmlmlllmmmlmlmmlmmllmllmmmlmmmmmmllmllmmmlmllmlmrllmlmmmmmllmlmrllmlmm՜.+,0l    On-screen ShowBarakee<#A )ArialTahoma Wingdingscmsy10Symbol Textured3Extracting Randomness From Few Independent SourcesPlan:Randomness ExtractionRandomness ExtractorsRandomness ExtractorsSolution 1: Seeded ExtractorsSolution 1: Seeded ExtractorsSeedless ExtractorsSlide 9 Slide 10Plan: Slide 12 Slide 13 Slide 14 Slide 15Plan: Distributional Version of [BKT] Slide 18Plan:Detailed Plan:Collision Probability Slide 22Detailed Plan:Nave ApproachNave ApproachDetailed Plan:Proof of Main LemmaTools:A First Distributional Analog: Slide 30 Slide 31 Slide 32 Slide 33Another Result:Open Problems  Fonts UsedDesign Template Slide Titles#_6K BoazBoaz  !"#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwyz{|}~Root EntrydO)PicturesMCurrent UserSummaryInformation(MUPowerPoint Document('ZKDocumentSummaryInformation8x