---
# System prepended metadata

title: composed-poly-design

---

- the goal is to create a general structure that allows for polynomial composition that is correct, efficient and easy to use
- the immediate use is to represent the f(b, c) polynomial in the [[gkr]] protocol, so I'd start my analysis from there and see if I can generalize later. 
- $f(b, c) = add(b, c)(w(b) + w(c)) + mul(b, c)(w(b) \cdot w(c))$ 
- we can further simplify to 
- $f(b, c) = add(b, c)w_1(b, c) + mul(b, c)w_2(b, c)$ 
- where $w_1(b, c) = w(b) + w(c)$ and $w_2(b, c) = w(b) \cdot w(c)$ 

- in the very specific case we have three types of polynomials
	- unit polynomials - represents a single [[multilinear-extension|mle]].
	- sum polynomials - holds a collection of [[multilinear-extension|mle]]s that are assumed to be added to one another.
	- product polynomials - holds a collection of [[multilinear-extension|mle]]s that are assumed to be multiplied with one another.

- we are making a tradeoff between full representation (add and multiply everything out) vs [[decomposition]]
	- #todo explore the cost model for decomposition vs multiplying out (there is a tradeoff space here). 

- rust enums could be used to achieve infinite composition
	- see very rough experiment: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=19dcde23b698067275a1ea78f51ba53a

- more importantly, I need to define the constraints when composing 

- [[polynomial-composition-constraints]]
	- the only identifiable feature of the [[multilinear-extension|mle]]s right now is the number of variables that they have. 
	- we don't know if two [[multilinear-extension|mle]]s share the same variables (no variable labelling), hence we have to assume. 

	- [[uniform-variable-constraint]]
		- one constraint that could be had is that all [[multilinear-extension|mle]] in the composed polynomial have the same variables
			- the following equation fits that:
			- $f(b, c) = add(b, c)w_1(b, c) + mul(b, c)w_2(b, c)$ 
			- how do we enforce such a constraint?
				- when constructing product, sum or unit, they ensure all the composed polynomials have the same number of variables and they themselves inherit that number.

	- NOTE: it is possible to combine polynomials with different variables will just need an extra labelling step to make everything work. 
		- might also require some kind of compile time formula parsing to make the UX better. 
		- but for the first version will stick to the [[uniform-variable-constraint]]

- max variable degree calculation (assuming [[uniform-variable-constraint]])
	- for unit polynomials the degree is basically 1
	- for sum polynomials the degree is the highest degree of the component polynomials
	- for product polynomials, the degree is the sum of the degrees of the component polynomials


- methods to implement
	- evaluate
	- partial_evaluate
	- n_vars
	- deg
	- reduce
		- fully evaluates the polynomial (multiply and sum everything out in the [[2HC]]) and returns the final vector
		- the [[hypercube|HC]] can be generalized later. 