ࡱ> mjkl( / 0DArialNew  C (0(z[ 0 DWingdings C (0(z[ 0  Dcmsy10gs C (0(z[ 0 "0DSymbolgs C (0(z[ 0 @DBrush Script C (0(z[ 0 BPDArial Narrow C (0(z[ 0 "`DTimes New Roman(0(z[ 0  A .  @n?" dd@  @@`` pht9HG H G  '   ( 0AA@3]3@83ʚ;ʚ;g4KdKd@z[ 0ppp@ <4ddddl 0C  80___PPT10 ?  %x"Computational Analogues of Entropy'Boaz Barak Ronen Shaltiel Avi Wigdersonb Statistical Min-Entropy  Our ContributionsStudy 3 variants (1 new) of pseudoentropy. Equivalence & separation results for several computational model. Study analogues of IT results. cReview - Pseudorandomness  Defining Pseudoentropy  Defining Pseudoentropy    HILL & Metric Def are Equivalent!!(  Unpredictability & Entropy  Unpredictability & Entropy      Construct P from D2 ]]      Open ProblemsAnalog of Thm 2 (unpredictabilityentropy)? Meaningful concatenation property? Separate Yao & Metric pseudoentropy. Dv MP 1 [ ` %J++f` Fh;K]mSq|` h` ffiff3` ffΟ` }` RP@hk]Ҧ]phk]b` ff` ѹWfff3>?" dd@,?Pd@ l2 " d@l2`" d n?" dd@   @@``PR    @ ` `6p>> VVGG(rV(  (n (  2BCDE4F>d @  MlwN0 *eN5l @`#" `OVOT   ( " > (  BlCDEF"d@ llll@`#" ` P \   ( " 2 ( # l?d @? #" `fz)2 (  f? @? #" `R2 ( T?d @? #" ` 2  ( N? @? #" `82  ( T?d @? #" `R  (  bB~CDELFV @ x 6eM;ekAS$ xx~~ x x x (,@`#" ` v$  (  JBCBDE@FJ @ 6a0$a<B<x0<$ 6x$066"$@`#" `oJ+  (  JBYCDE@FJd @  Bl$<YH*lB  B B"$@`#" ` B  (  BCDEFyd @ 88~7S[57 5SkM/7~ 2)2$2~1)qAAe=Agq1~agI%=[y\~~rt@`#" ` nV (  B`CDE$F.d @  0```0 @`#" `%2 ( N? @? #" `Fl \ /J  ( "/J 2 ( T?y @? #" `^Z 2 ( Z?yd @? #" ` v) 2 ( T?y @? #" `%  2 ( N? @? #" `@  2 ( N? @? #" `Q  2 ( N? @? #" `  z2 ( Z?yd @? #" `  _2 ( Z?d @? #" ` H = (  BCDE\Ff @ N $<ITyr~s`CB 0 N04@`#" `   (  jBzCDEFyd @ 44;_`<$la$<`?]cWJ?z3WztJztW-xT0mf0TMx# J#zG}k;z#Jjl@`#" `^   (  BCDEpFzd @ ,0SlH*IC $BwfH,\BkS0b,,:<@`#" `"  (  JBkCDE@FJd @ YTSA$5SekTe*YAS*YTYT"$@`#" `  N ( BCCDEPFZ U*<<C* [t $nNz`6z*,@`#" `eW N ( BCDEPFZ +CtHV<+x =m1VzV7m%=*,@`#" `K   (  BhC3DEpFzd @ hma1O1lB\ C*Nr+=7Cm=+3 37Oahmhm:<@`#" `   !(  B6CDElFvd @ 6*yP*xH0  $  **T,V8<@`#" ` /D ~ "(  :BbCDE8FBd @ 7P\Zb$bJJ$CZ7 @`#" ` J  #( JBCDEpFz s71[$T0 g$N~I%1s!+QIaCQ+!:<@`#" `Y\   gU $( "  gUf %(  "BCDE(F4 @ JJ\r<le0 &Jn 0e9or\EoL9nJ&Ll<E\\\~c-S0*$n*J0,S~T~6\96T~.d,nd.-c9\\@`@`#" `hJ %. &(  B CDEF @ $$$JBlfO<  I0ZZ* J*!NQr{C{lQH'0JL@`#" ` & @ '(  BaCDE`Fj @  q$0xNr7aa1~Zl<$k   24@`#" ` V ((  BHC6DE$F.d @  H$6$66*HHHH@`#" `~ )(  ZBClDEHFRd @ +ZZN0B`l+lfTg<g*BT+Z+Z&(@`#" `ZU *(  JBCUDE@FJd @ wrqY/%UUMqr<wYq<wrwr"$@`#" `FgV +(  BSCZDE$F.d @  ;ZSTG<5*#0;Z;Z@`#" `( ,( bBCDEF ??%yIVg g%wgTI0%0TfwH0%g 0DBJ0 g$kB<`+<Oksg2bsO+@`#" `] * -(  BCDEF @ ::hh<T'rE]ioi7Kg'nsfBg$7$0BZ~Br$ 7$mNm z ?im7u]9fB*hhvx@`#" `  .(  BBmCBDE<FF @ +gm 1r *B60r $@`#" ` A N /(  BBC0DE F* @ B0  0*BB@`#" `o 2 0( T? @? #" `W2 1( N? @? #" `.=2 2( T?d @? #" `B+2 3( N? @? #" `.^X2 4( T?d @? #" `Rr02 5( N? @? #" `\  I  6( " I  7(  jB~C`DEPFZd@ `ZSB#$*MHZ`Z7T`B~*x*ZB1NZ``*,@`#" `r   8(  JBC6DE@FJd@  xN $06$$Nx"$@`#" `   9(  JB<CDE@FJd@ 6Z0~6~<Z6B0***0B6Z6Z"$@`#" `  I n :(  *BCDE0F:d@  r H6 r r r @`#" `   ;(  rBCDETF^@  r`N5*e_ /$ HZr )A) r r,0@`#" ` Y  <(  BCDE`Fj@ B w$HZrwZ`rZB0H24@`#" `q + v =(  2B+CDEFd@ ,,Z* 6HZl ~*Z~+l+Z+H6`0~ lZ H60`  6%H%Z%l~[\@`@`#" `  b    >(# "  2 ?( H?? #" `  2 @( N?d? #" `  2 A( H?? #" `7% w 2 B( N?d? #" `R5 d  C( <K  " `} K  T Click to edit Master title style! !$ D( 0K  " ` K  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S E( 6d$K  #" `^ ` K  Z* F( 6)K  #" `^  K  \* G( 6 .K  #" `^ ` K  \*B ( s *޽h ? h___PPT10i. +D=' = @B +  RippleV  UUFF,T(  ,OT   , " > ,  BlCDEF"d@ llll@`#" ` P \   , " 2 , # l?d @? #" `fz)2 ,  f? @? #" `R2 , T?d @? #" ` 2 , N? @? #" `82  , T?d @? #" `R  ,  bB~CDELFV @ x 6eM;ekAS$ xx~~ x x x (,@`#" ` v$  ,  JBCBDE@FJ @ 6a0$a<B<x0<$ 6x$066"$@`#" `oJ+  ,  JBYCDE@FJd @  Bl$<YH*lB  B B"$@`#" ` B   ,  BCDEFyd @ 88~7S[57 5SkM/7~ 2)2$2~1)qAAe=Agq1~agI%=[y\~~rt@`#" ` nV ,  B`CDE$F.d @  0```0 @`#" `%2 , N? @? #" `Fl \ /J  , "/J 2 , T?y @? #" `^Z 2 , Z?yd @? #" ` v) 2 , T?y @? #" `%  2 , N? @? #" `@  2 , N? @? #" `Q  2 , N? @? #" `  z2 , Z?yd @? #" `  _2 , Z?d @? #" ` H = ,  BCDE\Ff @ N $<ITyr~s`CB 0 N04@`#" `   ,  jBzCDEFyd @ 44;_`<$la$<`?]cWJ?z3WztJztW-xT0mf0TMx# J#zG}k;z#Jjl@`#" `^   ,  BCDEpFzd @ ,0SlH*IC $BwfH,\BkS0b,,:<@`#" `"  ,  JBkCDE@FJd @ YTSA$5SekTe*YAS*YTYT"$@`#" `  N , BCCDEPFZ U*<<C* [t $nNz`6z*,@`#" `eW N , BCDEPFZ +CtHV<+x =m1VzV7m%=*,@`#" `K  ,  BhC3DEpFzd @ hma1O1lB\ C*Nr+=7Cm=+3 37Oahmhm:<@`#" `    ,  B6CDElFvd @ 6*yP*xH0  $  **T,V8<@`#" ` /D ~ !,  :BbCDE8FBd @ 7P\Zb$bJJ$CZ7 @`#" ` J  ", JBCDEpFz s71[$T0 g$N~I%1s!+QIaCQ+!:<@`#" `Y\   gU #, "  gUf $,  "BCDE(F4 @ JJ\r<le0 &Jn 0e9or\EoL9nJ&Ll<E\\\~c-S0*$n*J0,S~T~6\96T~.d,nd.-c9\\@`@`#" `hJ %. %,  B CDEF @ $$$JBlfO<  I0ZZ* J*!NQr{C{lQH'0JL@`#" ` & @ &,  BaCDE`Fj @  q$0xNr7aa1~Zl<$k   24@`#" ` V ',  BHC6DE$F.d @  H$6$66*HHHH@`#" `~ (,  ZBClDEHFRd @ +ZZN0B`l+lfTg<g*BT+Z+Z&(@`#" `ZU ),  JBCUDE@FJd @ wrqY/%UUMqr<wYq<wrwr"$@`#" `FgV *,  BSCZDE$F.d @  ;ZSTG<5*#0;Z;Z@`#" `( +, bBCDEF ??%yIVg g%wgTI0%0TfwH0%g 0DBJ0 g$kB<`+<Oksg2bsO+@`#" `] * ,,  BCDEF @ ::hh<T'rE]ioi7Kg'nsfBg$7$0BZ~Br$ 7$mNm z ?im7u]9fB*hhvx@`#" `  -,  BBmCBDE<FF @ +gm 1r *B60r $@`#" ` A N .,  BBC0DE F* @ B0  0*BB@`#" `o 2 /, T? @? #" `W2 0, N? @? #" `.=2 1, T?d @? #" `B+2 2, N? @? #" `.^X2 3, T?d @? #" `Rr02 4, N? @? #" `\  I  5, " I  6,  jB~C`DEPFZd@ `ZSB#$*MHZ`Z7T`B~*x*ZB1NZ``*,@`#" `r   7,  JBC6DE@FJd@  xN $06$$Nx"$@`#" `   8,  JB<CDE@FJd@ 6Z0~6~<Z6B0***0B6Z6Z"$@`#" `  I n 9,  *BCDE0F:d@  r H6 r r r @`#" `   :,  rBCDETF^@  r`N5*e_ /$ HZr )A) r r,0@`#" ` Y  ;,  BCDE`Fj@ B w$HZrwZ`rZB0H24@`#" `q + v <,  2B+CDEFd@ ,,Z* 6HZl ~*Z~+l+Z+H6`0~ lZ H60`  6%H%Z%l~[\@`@`#" `  b    =,# "  2 >, H?? #" `  2 ?, N?d? #" `  2 @, H?? #" `7% w 2 A, N?d? #" `R5 d  B, <D "*p  T Click to edit Master title style! ! C, 0u " `    W#Click to edit Master subtitle style$ $ D, 6̲K  #" `` `  Z* E, 6K  #" ``  K  \* F, 6K  #" `` ` K  \*B , s *޽h ? h___PPT10i. +D=' = @B +  *(  x  c $K B,*p K  r  S K C,p `  K  H  0޽h ? 33___PPT10i.Jg @J+D=' = @B +  # 4 (  4 4 0   H(X) Shannon-Ent(X)d 2  ]G ] ] ]r 4 S  C( `n    4 0   <*Definition: H(X)k iff maxx Pr[ X=x ]<2-k+ 2    ]G ] ]  ] ]  ] ]> 4 4 0  g ( X r.v. over {0,1}n ) 2] ]] 4 0, U Properties:. 2 $$ 4 0$C    H(X)=n iff X~Un@ 2  ] ],  4 0*    H(X,Y) H(X) (concatenation) r  2  ]G ] ] ]  4 05#v * If H(X)k then 9 (efficient) f s.t. f(X)~eUk/2 (extraction)TD 2   ]G ] ] G ]G    ]    ] ] ]  ] ,!l P  4PPP,$D 0n"  4 0Ԕ"`P   4 0E@@  YOur Objectives:. 2$$  4 0J  r1. Investigate possible defs for computational Min-Entropy. 2. Check whether computational defs satisfy analogs of statistical properties. 2!        N   ,@,8XH 4 0޽h ? hyq___PPT10Q.Jg\ؽ+UD%' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*4D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*4D' =-g6B fade*<3<*4+   \Tl(  lr l S bC( `}   r l S gD(     l 0 i ` ,$ 0 E In this talk: 2$ l 0m  `,$ 0 K7Present the 3 variants. Show 2 results + proof sketchesH l 0޽h ? h___PPT10.h`"+~eED@' = @B D' = @BA?%,( < +O%,( < +D2' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(+p+0+lK  ++0+lK  +     8v (  8r 8 S XvC( `}    8 0y` Def: X is pseudorandom if r 2   ]      8 0 M ,,maxD2C biasD(X,Un) < e 2 ] ]O ]O ] ] ] ] ] ] ]  8 0(`  ,$ 0 rC  class of efficient algorithms (e.g. s-sized circuits)t: 2G ] ]  ] 8 0 @  ,$ 0 <$biasD(X,Y) = | EX[D(X)] - EY[D(Y)] |% 2 ] ] ]  ](] ] ]  ] ] ](](] T 8 04,$ 0 ` e  parameter (in this talk: some constant > 0)D1 2  ]  "N  8 0ԩ@],$ 0 4i.e., X is computationally indistinguishable from Unj5 2 ]+]]]H 8 0޽h ? h  ___PPT10 ._gA@+qqD ' = @B De ' = @BA?%,( < +O%,( < +D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* 8%(D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*8%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(++0+8 ++0+8 ++0+8 ++0+ 8 + F  <<(  <x < c $C( `    < 0   *X is pseudorandom if b 2  ]      < 0x Pm ,,maxD2C biasD(X,Un) < e 2 ] ]O ]O ] ] ] ] ] ] ] RB < s *DԔ  < 0Hp ,$ 0 Def 1 [HILL]: HHILL(X)k if 2   ] ] ]G ] ]    F  < 0@@,$ 0 R9Y s.t. H(Y) k and maxD2C biasD(X,Y) < e* 2G ] ]  ]G ] ]  ] ]O ]O ] ] ] ] ],   < 0@`,$ 0 t@minH(Y) K maxD2C biasD(X,Y) < e! 2 ] ]O ]N ] ] ]O ]O ] ] ] ] ]$ B  < s *DԔ,$D  0e  < 0  ,$  0 Def 2: HMet(X)k if 2  ] ] ]G ] ]   < 0@` ,$  0 |@maxD2C minH(Y) K biasD(X,Y) < e! 2 ] ]O ]O ] ] ]O ]N ] ] ] ] ],  < 0 @  ,$ 0 mIDef 3 [Yao]: HYao(X)k if X cannot be efficiently compressed to k-1 bits.J 2   ] ] ]G ] ]  ]$  ] , 4B < s *DԔ,$D  0B < s *DԔ  ,$D 0l   < ,$D 0 < BX  G&H| "`  <  < 0`"    ;Oi.e., X is computationally indist. from some Y with k statistical min-entropy.P 2BF ]!BFBF ]BG ]F ]B/rl   < ,$D 0 < H/ G)H| "`  < $ < 64 @   hi.e., 8 efficient D, X is computationally indist. by D from some Y=Y(D) with k statistical min-entropy.i 2BG ] BF ]BF ]BF ]BFBF ]BG ]F ]B*9H < 0޽h ?/ << h--___PPT10-._gA@+jD+' = @B D+' = @BA?%,( < +O%,( < +D2' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* <%(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' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*<D' =1:Bhidden*o3>+B#style.visibility<*<%(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<* <%(D' =%(D' =%(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<* <%(D' =%(DB' =A@BB@BB0B%()?)?D' =.Q7 BBBBBcM -3.33333E-6 4.16185E-6 L -3.33333E-6 -0.07538 *3>*B ppt_xB ppt_y=@0BBAApBBB^<* <D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* <%(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' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*<D' =1:Bhidden*o3>+B#style.visibility<*<%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(++0+ <  ++0+ <  ++0+ <  ++0+ <  ++0+ <  ++0+ <  ++0+<  ++0+<  +   @(  @x @ c $P[ C( `     @ 00]  p,$ 0 AClaim 2: For k=n all 3 defs equivalent to pseudorandomness.bB 2     ]1   ,RB @ s *DԔz @ 0|i   bHHILL(X)k if minH(Y) K maxD2C biasD(X,Y) < e^2 2 ] ] ]G ] ]  ] ]O ]N ] ] ]O ]O ] ] ] ] ]  6  v  @ 0@{  `HMet(X)k if maxD2C minH(Y) K biasD(X,Y) < e\1 2 ] ] ]G ] ]  ] ]O ]O ] ] ]O ]N ] ] ] ] ] 6    @ 0(  lvHYao(X)k if X can t be efficiently compressed to k-1 bits.< 2 ] ] ]G ] ]  ]"  ]  3RB  @ s *DԔRB @ s *DԔ``RB @ s *DԔRR @ 0   ,$ 0 ,Claim 1: H(X) HHILL(X) HMet(X) HYao(X)- 2   ]G ] ] ] ]G ] ] ] ]G ] ] ] ], @ 0< p=,$ 0 5Claim 3: All 3 defs satisfy extraction property.[Tre]f6 2     ]], H @ 0޽h ? h  ___PPT10 ._gA@+a3 lD ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =-g6B fade*<3<*@D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =-g6B fade*<3<*@D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =-g6B fade*<3<*@++0+@  ++0+@  ++0+@  +X  &D ((  Dr D S  C( `    v D 0ľ P  ^HHILL(X)k if minH(Y)K maxD2C biasD(X,Y) < e^0 2 ] ] ]G ] ]  ] ]O ]N ] ] ]O ]O ] ] ] ] ]  6   r D 0 C \HMet(X)k if maxD2C minH(Y)K biasD(X,Y) < e\/ 2 ] ] ]G ] ]  ] ]O ]O ] ] ]O ]N ] ] ] ] ] 6   RB D s *DԔ00RB D s *DԔ  u  D 0 0 ,$ 0 Thm 1: HHILL(X) = HMet(X) 2  ] ] ] ] ]$\  D 0 p` ,$ 0 J(For C = poly-sized circuits, any e)b& 2]]F  D 0 c0,$ 0 Proof: Suppose HHILL(X)+B#style.visibility<* D%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* D%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* D%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* D%(D ' =%(DH ' =%(Dt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*DD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*DD' =-g6B fade*<3<*DDt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*DD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*DD' =-g6B fade*<3<*DD2 ' =%(D' =%(Dt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*DD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*DD' =-g6B fade*<3<*DD' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-s6Bwipe(left)*<3<*DD' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-o6Bwipe(up)*<3<*DD' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D ' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-o6Bwipe(up)*<3<*DD' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*DD' =1:Bhidden*o3>+B#style.visibility<*D%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*DD' =1:Bhidden*o3>+B#style.visibility<*D%(D' =%( D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*DD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*DD' =-g6B fade*<3<*DD' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*"D%(D' =-s6Bwipe(left)*<3<*"DD' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*DD' =1:Bhidden*o3>+B#style.visibility<*D%(D)' =4@BB BB%(D' =-g6B fade*<3<*"DD' =1:Bhidden*o3>+B#style.visibility<*"D%(D' =%( D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =%( D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* D%(D' =-s6Bwipe(left)*<3<* DD' =%( D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*&D%(D' =-g6B fade*<3<*&D+0+0+ D  ++0+ D  ++0+ D  ++0+D  ++0+D  ++0+D  ++0+D  ++0+D  ++0+D  ++0+D  +    HJ(  Hr H S LO C( `     H 0,P `,$ 0 Thm [Yao]: If X is unpredicatble with adv. e then X is pseudorandom w/ param e =neT 2    ]  ]  ]  ] ]G ] ]H ' H 0_ ` ,$ 0 $Loss of factor of n due to hybrid argument  useless for constant advantage enN 2  ]     H 04h  Pj ,$ 0 aThis loss can be crucial for some applications (e.g., extractors, derandomizing small-space algs):b 2/ 2],B  l P 0  H `,$D 0n" H 0Ԕ"`P 0 H 0n   _Can we do better?2 2  H H 0޽h ? h___PPT10.Zh`Q+*D' = @B D ' = @BA?%,( < +O%,( < +D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*H%(D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*H%(D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*H%(DW' =%(D' =%(D' =4@BB7BB%())))?D' =1:Bvisible*o3>+B#style.visibility<* H%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* HD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* HD' =-g6B fade*<3<* H++0+H  ++0+H  ++0+H  +  ` X(  Xx X c $oK C( `  K   X 0qK ` p,$ 0 TIT Fact [TZS]: If X is IT-unpredictable with const. adv. then H(X)=W(n) J 2    ],  ] ] ]  X 00}K ``,$ 0 w)We obtain the following imperfect analog:2* 2)  J  X 0dK p`@ ,$ 0 Thm 2: If X is unpredictable by SAT-gate circuits with const. adv. then HMet(X)=W(n) V 2   ]    ] ] ] ] ]$E  X 0K  ,$ 0 LIn paper: A variant of Thm 2 for nonuniform online logspace.ZM 2  (    ]> H X 0޽h ? h^ V ___PPT106 .Zh`Q+f(ZoD* ' = @B D ' = @BA?%,( < +O%,( < +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%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* X%(++0+XK  ++0+XK  ++0+ XK  ++0+ XK  +(  p\(  \ \ 0Ԁ ``@ Thm 2: If X is unpredictable by SAT-gate circuits with const. adv. then HMet(X)=W(n) V 2   ]    ] ] ] ] ]$EJ \ 04 `@P,$ 0 Proof: Suppose that HMet(X)<dn We ll construct a SAT-gate predictor P s.t.R 2   ] ] ] ]  ]%] ],3 \ 0 P`p ,$ 0 n@Pri,X[ P(X1,& ,Xi-1)=Xi ] = 1  d! 2 ] ](] ] ] ] ] ] ] ](] ] ] ]V \ 0   ,$ 0 TWe have that maxD2CminH(Y)dn biasD(X,Y)e0+ 2  ] ]O ]O ] ] ]O ] ]N ] ] ] ]G ] ]  B \ s *DԔ p ,$D 0  \ 0  m ,$ 0 \i.e., 9D s.t. 8Y If H(Y)dn then biasD(X,Y) eV/ 2G ] ]  ]G ] ]  ]G ] ] ]  ] ] ]G ] ] ] >     \ 0  ,$ 0 vnAssume: 1) |D-1(1)| < 2dn *2) PrX[ D(X)=1 ] = 18 2  ] ] ] ] ] ]  ] ] ]%4l    \p P ,$D 0  \ B GH*y    < N Pp   \  ` n  \ 0|"`Pp n2 \ 0|"`  n2 \ 0|"`  \ 0 c T{0,1}n2 2F ]N ] \ 0p   OD2 2F ]N ] \ 0 P M  OX2 2F ]N ]H \ 0޽h ? \ h2*___PPT10 .`hP+ND' = @B D' = @BA?%,( < +O%,( < +D2' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* \%(DA' =%(