Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Extractors:Optimal Up to Constant Factors,Avi Wigderson,IAS,Princeton,Hebrew U.,Jerusalem,Joint work with,Chi-Jen Lu,Omer Reingold,Salil Vadhan.,To appear:STOC 03,Original Motivation,B84,SV84,V85,VV85,CG85,V87,CW89,Z90-91,Randomization is pervasive in CS,Algorithm design,cryptography,distributed computing,Typically assume perfect random source.,Unbiased,independent random bits,Can we use a“weak random source?,(Randomness)Extractors:convert weak random sources into almost perfect randomness.,Extractors,Nisan&Zuckerman 93,d,random bits,(short)“,seed,”,E,XT,k,-,source of length,n,m,almost-uniform bits,X has,min-entropy,k,(,is a,k,-,source)if,x PrX=x,2,-k,(i.e.no heavy elements).,Extractors,Nisan&Zuckerman 93,E,XT,k,-,source of length,n,m,bits,-close to uniform,X has,min-entropy,k,(,is a,k,-,source)if,x PrX=x,2,-k,(i.e.no heavy elements).,Measure of closeness:,statistical difference,(a.k.a.variation distance,a.k.a.half L,1,-norm).,d,random bits,(short)“,seed,”,Applications of Extractors,Derandomization of error reduction in BPP,Sip88,GZ97,MV99,STV99,Derandomization of space-bounded algorithms,NZ93,INW94,RR99,GW02,Distributed&Network Algorithms,WZ95,Zuc97,RZ98,Ind02,.,Hardness of Approximation,Zuc93,Uma99,MU01,Cryptography,CDHKS00,MW00,Lu02 Vad03,Data Structures,Ta02,Unifying Role of Extractors,Extractors are intimately related to:,Hash Functions,ILL89,SZ94,GW94,Expander Graphs,NZ93,WZ93,GW94,RVW00,TUZ01,CRVW02,Samplers,G97,Z97,Pseudorandom Generators,Trevisan 99,Error-Correcting Codes,T99,TZ01,TZS01,SU01,U02,Unify the theory of pseudorandomness.,Extractors as graphs,k,-source,X,|,X,|=2,k,(,k,)-extractor,Ext,:,0,1,n,0,1,d,0,1,m,0,1,n,0,1,m,x,Ext,(x,y),y,B,(,X,),Discrepancy,:For all but,2,k,of the x,0,1,n,|,(,X,),B,|/2,d,-,|,B,|/2,m,|t,.,0,Need,0,log 1/,0,log t.,Extractor seed length,t,.,log t,which may be as large as,log n,.,loglog n,(partially explains seed length of,RSW00,).,Solution idea:,start with,constant,0,.,Combine repeated condensing w/,error reduction,(la,RRV99,)to prevent error accumulation.,Error Reduction,Con,0,w/error,;condensation,;seed length,d,seed,0,k,-,source;length,n,(,k),-source;length,n,Con,0,Con,0,seed,1,(,k),-source;length,n,Con,has,condensation,2,;,seed length,2d,.,Hope:,error,2,.,Only if error comes from seeds!,Parallel composition,Con,0,:seed error,;condensation,;seed length,d,;,source error;entropy loss =k+d-k,seed,0,length,n,length,n,Con,0,Con,0,seed,1,length,n,Con,:s,eed error,O(,2,),;,condensation,2,;,seed,d+O(log 1/),;,source error;entropy loss+1,Serial composition,Con,0,:seed error,;condensation,;seed,d,;,source error;entropy loss =k+d-k,Con,0,Con:,s,eed error,O(),;,condensation,2,;,seed,2d,;,source error(1+1/);entropy loss 2,seed,0,seed,1,Con,0,Repeated condensing revisited,Start with,Con,0,w/,constant,seed error,1/18;,constant,condensation,;,constant,seed length,d,;,(source error,0,;entropy loss,0,).,Alternate parallel and serial composition,loglog n/k+O(1),times.,Con,w/seed error,;condenses to O(k)bits;,optimal,seed length,d=O(log n/k),;,(source error (polylog n/k),.,0,;,entropy loss O(log n/k),.,0,).,Home?Not so fast,2,nd,Challenge:No Such Explicit Lossless Condensers,Previous condensers,with constant seed length:,A,(k,),-condenser w/,n=n-O(1),C,RVW02,A,(k,(,k),),-condenser w/,n=n/100,Vad03,for,k=(,n),Here,:A,(k,(,k),),-condenser w/,n=n/100,for,any k,(see them later).,Still n,ot lossless!,Challenge persists,Win-Win Condensers,RSW00,Assume Con is a(k,(k),)-condenser then k-source X,we are in one of two good cases:,Con(X,Y)contains almost k bits of randomness Con is almost lossless.,X still has some randomness even conditioned on Con(X,Y).,(Con(X,Y),X)is a“block source CG85.Good extractors for block sources already known(based on NZ93,),Ext(Con(X,Y),X)is uniform on(k)bits,Win-Win under composition,More generally:,(Con,Som),is a win-win condenser if,k-source X,either:,Con(X,Y)is,lossless,.Or:,Som(X,Y)is,somewhere random,:a list of,b,sources one of which is uniform on,(,k),bits.,Parallel composition generalized:,Con(X,Y,1,Y,2,)=Con(X,Y,1,),Con(X,Y,2,),Som(X,Y,1,Y,2,)=Som(X,Y,1,),Som,(X,Y,2,),Serial composition generalized:,Con(X,Y,1,Y,2,)=Con(Con(X,Y,1,),Y,2,),Som(X,Y,1,Y,2,)=Som(X,Y,1,),Som,(Con(X,Y,1,),Y,2,),Partial Summary,We give a constant seed length,(k,(k),)-condenser w/n=n/100(still to be seen).,Implies a lossless win-win condenser with constant seed length.,Iterate repeated condensing and(seed-)error reduction loglog n/k+O(1)times.,Get a win-win condenser(Con,Som)where,Con condenses to O(k)bits and,Som produces a“short list of t sources where one of which is a block source(t can be made as small as log(c)n).,3,rd,Challenge:Mergers,TaShma96,Now we have a,somewhere random source,X,1,X,2,X,t,(one of the X,i,is random),t,can be made as small as log,(c),n,An extractor for such a source is called,merger,TaS96,.,Previous constructions:,mergers,w/seed length,d=O(