EspressoSystems/hyperplonk

potential optimization ideas

zhenfeizhang opened this issue · 2 comments

  • better parallelization for sum check
  • batch inversion in product check
  • batch open single polynomial
  • batch open multiple polynomial
  • parallelization of partial product computation
  • open with sqrt(2^mu) group operations with pre-compuation
  • sum-check multiplication with karatsuba/FFT
  • 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.