Struct MultilinearPoly

Source

pub struct MultilinearPoly<F: Field> { /* private fields */ }

Expand description

A multilinear polynomial represented by its evaluation table.

The table has 2^num_vars entries in big-endian bit order: the first variable is the most significant bit. For a 2-variable polynomial f(x0, x1):

Index	x0	x1	Value
0	0	0	`evals[0]`
1	0	1	`evals[1]`
2	1	0	`evals[2]`
3	1	1	`evals[3]`

§Examples

use field_cat::F101;
use proof_cat::MultilinearPoly;

// f(x0, x1): f(0,0)=1, f(0,1)=2, f(1,0)=3, f(1,1)=4
let poly = MultilinearPoly::from_evals(vec![
    F101::new(1), F101::new(2), F101::new(3), F101::new(4),
])?;

assert_eq!(poly.num_vars().count(), 2);

// Sum over the Boolean hypercube: 1 + 2 + 3 + 4 = 10
assert_eq!(poly.sum_over_boolean_hypercube(), F101::new(10));

// Evaluate at a Boolean point: f(1, 0) = 3
let val = poly.evaluate(&[F101::new(1), F101::new(0)])?;
assert_eq!(val, F101::new(3));

Implementations§

Source §

impl<F: Field> MultilinearPoly<F>

Source

pub fn from_evals(evals: Vec<F>) -> Result<Self, Error>

Construct from an evaluation table.

The table length must be a power of two (including 1).

§Errors

Returns Error::NotPowerOfTwo if evals.len() is not a power of two or is zero.

§Examples

use field_cat::F101;
use proof_cat::MultilinearPoly;

// A 1-variable polynomial: f(0) = 3, f(1) = 7.
let poly = MultilinearPoly::from_evals(vec![
    F101::new(3), F101::new(7),
])?;
assert_eq!(poly.num_vars().count(), 1);

// Non-power-of-two lengths are rejected.
let err = MultilinearPoly::<F101>::from_evals(vec![
    F101::new(1), F101::new(2), F101::new(3),
]);
assert!(err.is_err());

Source

pub fn num_vars(&self) -> NumVars

The number of variables.

Source

pub fn evals(&self) -> &[F]

The evaluation table.

Source

pub fn sum_over_boolean_hypercube(&self) -> F

Sum of all evaluations on the Boolean hypercube.

This equals sum_{x in {0,1}^n} f(x).

Source

pub fn evaluate(&self, point: &[F]) -> Result<F, Error>

Evaluate the multilinear extension at an arbitrary point.

Uses iterated partial evaluation: for each variable i, the table is split in half and each pair (lo, hi) is interpolated as lo * (1 - r_i) + hi * r_i. After n rounds a single value remains.

§Errors

Returns Error::DimensionMismatch if point.len() != num_vars.

§Examples

use field_cat::F101;
use proof_cat::MultilinearPoly;

// f(x) = 3*(1-x) + 7*x = 3 + 4x
let poly = MultilinearPoly::from_evals(vec![
    F101::new(3), F101::new(7),
])?;

// f(0) = 3, f(1) = 7, f(2) = 11
assert_eq!(poly.evaluate(&[F101::new(0)])?, F101::new(3));
assert_eq!(poly.evaluate(&[F101::new(1)])?, F101::new(7));
assert_eq!(poly.evaluate(&[F101::new(2)])?, F101::new(11));