Investigate possibility of integrating pippenger's exponentiation algorithm #1653
Labels
dialect: polynomial
Issues concerning the polynomial dialect
newcomer project
Project ideas for new contributors
research synthesis
Reading papers to figure out which ideas can be incorporated
I was talking with a colleague about Pippenger's exponentiation algorithm (in the context of elliptic curves) and it occurred to me that we could use that for a potential optimization of polynomial evaluation in HEIR.
See section 7 of https://cr.yp.to/papers/pippenger.pdf for an overview, but there are two parts of it: computing many exponents of a single base
x
and computing multinomials across multiple bases. The first one seems directly applicable to polynomial.eval lowerings, especially when you have to evaluate multiple polynomials on the same input and want to jointly optimize across them all.The second one (multiple bases) seems like it could be useful if there comes a time when we want to evaluate multi-variable polynomials on multiple input ciphertexts in service of some other computation.
The text was updated successfully, but these errors were encountered: