potential optimization ideas

[zhenfeizhang]

• better parallelization for sum check
• batch inversion in product check
• batch open single polynomial
• batch open multiple polynomial

[bbuenz]

• parallelization of partial product computation
• open with sqrt(2^mu) group operations with pre-compuation
• sum-check multiplication with karatsuba/FFT

[chancharles92]

• Reduce the number of rounds to \mu in the batching sumcheck .
• Reduce the number of PCS openings to 1, make the batching as efficient as possible.
• Split the merged witness commitment, reduce the number of variables to \mu + 1 in the product polynomial.
• Parallelize the computation of witness commitments.
• (Optional) Exploit the fact that many evaluation points share a common suffix.
• Optimize high-degree poly sumcheck using dynamic programming (#89 (comment))
• Check why PCS opening is more expensive than PCS committing.