Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Native bounded MLE #8651

Open
Tracked by #7817
jeanmon opened this issue Sep 19, 2024 · 0 comments · May be fixed by #8668
Open
Tracked by #7817

Native bounded MLE #8651

jeanmon opened this issue Sep 19, 2024 · 0 comments · May be fixed by #8668
Assignees
Labels
avm AVM related tickets (aka public VM)

Comments

@jeanmon
Copy link
Contributor

jeanmon commented Sep 19, 2024

Implement a variant of Polynomial::evaluate_mle() for "long zero tail" polynomials, i.e., polynomials with all zero coefficients from a given index (bound). This method is meant for polynomials where at least half of the last coefficients are zero. Assuming that bound <= 2^k and size of polynomial is 2^n, then we can fold over k dimensions and finally multiply the result with (1 - challenge) for all the challenges at higher dimensions.
Namely, all monomials containing terms X_{k+1}, ....X_n have zero coefficients and all the monomials with non-zero coefficients contain the term (1-X_{k+1}) * (1-X_{k+2}) * ..... * (1-X_n).
Therefore, we perform a standard mle in dimension k and the result is multiplied by (1-u_{k+1}) * (1-u{k+2}) * ...(1-u_n) where u_i's denote the challenges.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
avm AVM related tickets (aka public VM)
Projects
Status: In Progress
Development

Successfully merging a pull request may close this issue.

1 participant