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?



Your Answer

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