Struct MultilinearExtension 

pub struct MultilinearExtension<F: Field> {
    pub f: Evaluations<F>,
}

Stores a function \tilde{f}: F^n -> F, the unique Multilinear Extension (MLE) of a given function f: {0, 1}^n -> F:

    \tilde{f}(x_0, ..., x_{n-1})
        = \sum_{b_0, ..., b_{n-1} \in {0, 1}^n}
            \tilde{beta}(x_0, ..., x_{n-1}, b_0, ..., b_{n-1})
            * f(b_0, ..., b_{n-1}).

where \tilde{beta} is the MLE of the equality function:

    \tilde{beta}(x_0, ..., x_{n-1}, b_0, ..., b_{n-1})
        = \prod_{i  = 0}^{n-1} ( x_i * b_i + (1 - x_i) * (1 - b_i) )

Internally, f is represented as a list of evaluations of f on the boolean hypercube. The n variables are indexed from 0 to n-1 throughout the lifetime of the object even if n is modified by fixing a variable to a constant value.

Fields

f: Evaluations<F>

The bookkeeping table with the evaluations of f on the hypercube.

Implementations

impl<F: Field> MultilinearExtension<F>

pub fn new(evals_vec: Vec<F>) -> Self

Create a new MultilinearExtension from a Vec<F> of evaluations.

pub fn new_from_evals(evals: Evaluations<F>) -> Self

Generate a new MultilinearExtension from a representation evals of a function f.

pub fn new_sized_zero(num_vars: usize) -> Self

Creates a new mle which is all zeroes of a specific num_vars. In this case the size of the evals and the num_vars will not match up

pub fn iter(&self) -> EvaluationsIterator<'_, F>

Returns an iterator accessing the evaluations defining this MLE in “big-endian” order.

pub fn to_vec(&self) -> Vec<F>

Generate a Vector of the evaluations of f over the hypercube.

pub fn is_fully_bound(&self) -> bool

Returns true if the MLE has not free variables. Equivalent to checking whether that Self::num_vars is equal to zero.

pub fn first(&self) -> F

Returns the first element of the bookkeeping table of this MLE, corresponding to the value of the MLE when all varables are set to zero. This operation never fails (see Evaluations::first).

pub fn value(&self) -> F

If self represents a fully-bound MLE (i.e. on zero variables), it returns its value. Otherwise panics.

pub fn new_zero() -> Self

Generates a representation for the MLE of the zero function on zero variables.

pub fn num_vars(&self) -> usize

Returns n, the number of arguments \tilde{f} takes.

pub fn get(&self, idx: usize) -> Option<F>

Returns the idx-th element, if idx is in the range [0, 2^self.num_vars).

pub fn evaluate_at_point(&self, point: &[F]) -> F

Evaluate \tilde{f} at point \in F^n.

Panics

If point does not contain exactly self.num_vars() elements.

pub fn len(&self) -> usize

Returns the length of the evaluations vector.

pub fn fix_variable_at_index(&mut self, var_index: usize, point: F)

Fix the 0-based var_index-th bit of \tilde{f} to an arbitrary field element point \in F by destructively modifying self.

Params

• var_index: A 0-based index of the input variable to be fixed.
• point: The field element to set x_{var_index} equal to.

Example

If self represents a function \tilde{f}: F^3 -> F, self.fix_variable_at_index(1, r) fixes the middle variable to r \in F. After the invocation, self represents a function \tilde{g}: F^2 -> F defined as the multilinear extension of the following function: g(b_0, b_1) = \tilde{f}(b_0, r, b_1).

Panics

if var_index is outside the interval [0, self.num_vars()).

pub fn fix_variable(&mut self, point: F)

Optimized version of fix_variable_at_index for var_index == 0.

Panics

If self.num_vars() == 0.

pub fn stack_mles(mles: Vec<MultilinearExtension<F>>) -> MultilinearExtension<F>

Stacks the MLEs into a single MLE, assuming they are stored in a “big endian” fashion.

pub fn convert_into_u8_vec(&self) -> Vec<u8>

Convert a MultilinearExtension into a vector of u8s. Every element is padded to contain 8 bits.

pub fn convert_into_u16_vec(&self) -> Vec<u16>

Convert a MultilinearExtension into a vector of u16s. Every element is padded to contain 16 bits.

pub fn convert_into_u32_vec(&self) -> Vec<u32>

Convert a MultilinearExtension into a vector of u32s. Every element is padded to contain 32 bits.

pub fn convert_into_u64_vec(&self) -> Vec<u64>

Convert a MultilinearExtension into a vector of u64s. Every element is padded to contain 64 bits.

pub fn convert_into_u128_vec(&self) -> Vec<u128>

Convert a MultilinearExtension into a vector of u128s. Every element is padded to contain 128 bits.

Trait Implementations

impl<F: Clone + Field> Clone for MultilinearExtension<F>

fn clone(&self) -> MultilinearExtension<F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for MultilinearExtension<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, F> Deserialize<'de> for MultilinearExtension<F>

where F: Field,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F: Field> From<Vec<bool>> for MultilinearExtension<F>

fn from(bools: Vec<bool>) -> Self

Converts to this type from the input type.

impl<F: Field> From<Vec<i32>> for MultilinearExtension<F>

fn from(ints: Vec<i32>) -> Self

Converts to this type from the input type.

impl<F: Field> From<Vec<i64>> for MultilinearExtension<F>

fn from(ints: Vec<i64>) -> Self

Converts to this type from the input type.

impl<F: Field> From<Vec<u32>> for MultilinearExtension<F>

fn from(uints: Vec<u32>) -> Self

Converts to this type from the input type.

impl<F: Field> From<Vec<u64>> for MultilinearExtension<F>

fn from(uints: Vec<u64>) -> Self

Converts to this type from the input type.

impl<F: PartialEq + Field> PartialEq for MultilinearExtension<F>

fn eq(&self, other: &MultilinearExtension<F>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F> Serialize for MultilinearExtension<F>

where F: Field,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<F: Field> Zeroize for MultilinearExtension<F>

fn zeroize(&mut self)

Zero out this object from memory using Rust intrinsics which ensure the zeroization operation is not “optimized away” by the compiler.

impl<F: Field> StructuralPartialEq for MultilinearExtension<F>