Let be a finite alphabet and be a finite set of distributions over . A Generalized Santha-Vazirani (GSV) source of type ( ) , introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence ( F 1 F n ) in n , where F i is a sample from some distribution d whose choice may depend on F 1 F i − 1 .

We show that all GSV source types ( ) fall into one of three categories: (1) non-extractable; (2) extractable with error n − (1) ; (3) extractable with error 2 − ( n ) . This rules out other error rates like 1 log n or 2 − n .

We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts with error from n = \poly (1 ) samples in time linear in n . Our algorithm for category (3) sources extracts m bits with error from n = O ( m + log 1 ) samples in time min O ( nm 2 m ) n O ( ) .

We also give algorithms for classifying a GSV source type ( ) : Membership in category (1) can be decided in NP , while membership in category (3) is polynomial-time decidable.