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?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
