ࡱ> 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+ +