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

Conventional lookups based on log-derivative #959

Open
ledwards2225 opened this issue Apr 22, 2024 · 0 comments
Open

Conventional lookups based on log-derivative #959

ledwards2225 opened this issue Apr 22, 2024 · 0 comments

Comments

@ledwards2225
Copy link
Collaborator

Tldr: Without structured trace? optional. With structured trace? Necessary

Committing to the lookup grand product is one of our highest commitment costs (equivalent to permutation grand product) so converting to log-deriv would be beneficial even without the structured trace optimization. With a structured trace, however, it becomes an unacceptably large cost because it is not constant over "dead" ranges, i.e. it is dense and nontrivial across the full size of the trace. This is in contrast to the permutation grand product which takes constant values in the dead regions and can thus be committed to relatively cheaply via the sorted MSM optimization.

@ledwards2225 ledwards2225 added this to the Structured Trace milestone Apr 22, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant