The optimization problem in that PR just minimizes the total number of relin ops (with a hard-bound on the maximum key basis size allowed in the program). We could relax this by having a cost per (operation, degree) tuple, and charging the solver for doing ops with a larger key basis. It's not clear how much this could improve efficiency/noise growth, but some papers (like Blatt-Gusev-Polyakov-Rohloff-Vaikuntanathan 2019 https://eprint.iacr.org/2019/223) mention that they might NEVER do relinearization.
It's also not clear to what extent various libraries we export to would support high-basis-degree ops.
But to implement this feature, we would mainly need a way to estimate costs of the ops, and the changes to the ILP would be relatively small.
Pre-filing issue for https://github.com/google/heir/pull/1016
The optimization problem in that PR just minimizes the total number of relin ops (with a hard-bound on the maximum key basis size allowed in the program). We could relax this by having a cost per (operation, degree) tuple, and charging the solver for doing ops with a larger key basis. It's not clear how much this could improve efficiency/noise growth, but some papers (like Blatt-Gusev-Polyakov-Rohloff-Vaikuntanathan 2019 https://eprint.iacr.org/2019/223) mention that they might NEVER do relinearization.
It's also not clear to what extent various libraries we export to would support high-basis-degree ops.
But to implement this feature, we would mainly need a way to estimate costs of the ops, and the changes to the ILP would be relatively small.