Statistical tests are used to check whether a source of randomness is "good". Blum and Goldreich (1992) mentioned two types of statistical tests : (1) deterministic polynomial time statistical tests and (2) logspace statistical tests. They also state that "all the statistical tests used in practice can be implemented by logspace machines". To give some examples, Sivakumar showed that the statistical tests corresponding to set discrepancy problem, lattice approximation problem and Johnson-Lindenstrauss Lemma can be implemented by a logspace machine with an index tape and an advice tape.

I am looking for statistical tests that are in $LogCFL$ but not known to be in logspace. Are there any such tests ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.