1
$\begingroup$

Goldreich Levin algorithm is an algorithm that based on some assumption (boundness on Fourier coefficients) outputs the indices for most significant Fourier coefficients of a boolean function, however a strong assumption for this algorithm to work is the uniform distribution over the input domain. Is there a distribution free generalization for the PAC agnostic setting when the distribution is unknown? Is it efficient in terms of sample and time complexity?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.