Module mle 

Helpful functions for manipulating MLEs (e.g. padding). Module for generating and manipulating mles.

Structs

GrayCodeIterator

A struct representing an iterator that iterates through the range (1..2^{num_bits}) but in the ordering of a Gray Code, which means that the Hamming distance between the bit representation of any consecutive indices is only 1.

LexicographicLE

A struct representing lexicographic bit-order in little-endian.

Functions

argsort

Returns the argsort (i.e. indices) of the given vector slice.

build_composite_mle

Construct a parent MLE for the given MLEs and prefix bits, where the prefix bits of each MLE specify how it should be inserted into the parent. Entries left unspecified are filled with F::ZERO.

compute_flipped_bit_idx_and_value_graycode

Compute the single flipped bit and its previous value for the gray codes iterator.

compute_flipped_bit_idx_and_values_lexicographic

Compute the flipped bits between a previous value and a current value, and return each of the flipped bits’ indices and previous value.

compute_inverses_vec_and_one_minus_inverted_vec

Compute the inverses and one minus the elem inverted for a vec of claim challenges.

compute_next_beta_value_from_current

Compute the next beta value from the previous by multiplying by appropriate inverses and challenge points given the flipped bits and their previous values. This is for when we have a single claim to compute the beta over.

compute_next_beta_values_vec_from_current

Compute the next beta values from the previous by multiplying by appropriate inverses and challenge points given the flipped bits and their previous values. This is for when we have multiple claims to compute the beta over.

evaluate_mle_at_a_point_gray_codes

This function non-destructively evaluates an MLE at a given point using the gray codes iterator. Optimized version that uses 2 multiplications instead of 1.

evaluate_mle_at_a_point_gray_codes_parallel

This function non-destructively evaluates an MLE at a given point using the gray codes iterator. Parallelized version that uses K threads.

evaluate_mle_at_a_point_lexicographic_order

This function non-destructively evaluates an MLE at a given point using the LexicographicLE iterator.

evaluate_mle_destructive

Destructively evaluate an MLE at a point by using the fix_variable algorithm iteratively until all of the variables have been bound.

get_dummy_random_mle_vec

Returns a vector of MLEs for dataparallel testing according to the number of variables and number of dataparallel bits.

get_mle_idx_decomp_for_idx

Returns the specific bit decomp for a given index, using num_bits bits. Note that this returns the decomposition in BIG ENDIAN!

get_random_mle

Helper function to create random MLE with specific number of vars

get_random_mle_from_capacity

Helper function to create random MLE with specific number of vars

get_total_mle_indices

Returns the total MLE indices given a Vec<bool>. for the prefix bits and then the number of free bits after.

pad_with

Return a vector containing a padded version of the input data, with the padding value at the end of the vector, such that the length is data.len().next_power_of_two(). This is a no-op if the length is already a power of two.

verify_claim

Verifies a claim by evaluating the MLE at the challenge point and checking that the result.