Struct ShiftIndPartialEval

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

Represents MLE of shift indicator $f_{b, o}(X, Y)$ on $2*b$ variables partially evaluated at $Y = r$

Formal Definition

Let $x, y \in {0, 1}^b$ If ShiftVariant is CircularLeft: * $f(x, y) = 1$ if ${y} - {o} \equiv {x} (\text{mod } 2^b)$ * $f(x, y) = 0$ otw

Else if ShiftVariant is LogicalLeft:

• $f(x, y) = 1$ if ${y} - {o} \equiv {x}$
• $f(x, y) = 0$ otw

Else, ShiftVariant is LogicalRight:

• $f(x, y) = 1$ if ${y} + {o} \equiv {x}$
• $f(x, y) = 0$ otw

where:

• ${x}$ is the integer representation of the hypercube point $x \in {0, 1}^b$,
• $b$ is the block size parameter’
• $o$ is the shift offset parameter.

Observe $\forall x \in {0, 1}^b$, there is at most one $y \in {0, 1}^b$ s.t. $f(x, y) = 1$

Intuition

Consider the lexicographic ordering of each point on the $b$-variate hypercube into a $2^b$ length array. Thus, we can give each element on the hypercube a unique index $\in {0, \ldots, 2^b - 1}$ Let $x, y \in {0, 1}^{b}$ be s.t. ${x} = i$ and ${y} = j$ $f(x, y) = 1$ iff: * taking $o$ steps from $j$ gets you to $i$ (wrap around if ShiftVariant is Circular + direction of steps depending on ShiftVariant’s direction)

Note

CircularLeft corresponds to the shift indicator in Section 4.3. LogicalLeft corresponds to the shift prime indicator in Section 4.3. LogicalRight corresponds to the shift double prime indicator in Section 4.3.

Example

Let $b$ = 2, $o$ = 1, variant = CircularLeft. The hypercube points (0, 0), (1, 0), (0, 1), (1, 1) can be lexicographically ordered into an array [(0, 0), (1, 0), (0, 1), (1, 1)] Then, by considering the index of each hypercube point in the above array, we observe: * $f((0, 0), (1, 0)) = 1$ because $1 - 1 = 0$ mod $4$ * $f((1, 0), (0, 1)) = 1$ because $2 - 1 = 1$ mod $4$ * $f((0, 1), (1, 1)) = 1$ because $3 - 1 = 2$ mod $4$ * $f((1, 1), (0, 0)) = 1$ because $0 - 1 = 3$ mod $4$ and every other pair of $b$-variate hypercube points $x, y \in {0, 1}^{b}$ is s.t. f(x, y) = 0. Using these shift params, if f = [[a_i, b_i, c_i, d_i]_i], then shifted_f = [[b_i, c_i, d_i, a_i]_i]

Example

Let $b$ = 2, $o$ = 1, variant = LogicalLeft. The hypercube points (0, 0), (1, 0), (0, 1), (1, 1) can be lexicographically ordered into an array [(0, 0), (1, 0), (0, 1), (1, 1)] Then, by considering the index of each hypercube point in the above array, we observe: * $f((0, 0), (1, 0)) = 1$ because $1 - 1 = 0$ * $f((1, 0), (0, 1)) = 1$ because $2 - 1 = 1$ * $f((0, 1), (1, 1)) = 1$ because $3 - 1 = 2$ and every other pair of $b$-variate hypercube points $x, y \in {0, 1}^{b}$ is s.t. f(x, y) = 0. Using these shift params, if f = [[a_i, b_i, c_i, d_i]_i], then shifted_f = [[b_i, c_i, d_i, 0]_i]

Example

Let $b$ = 2, $o$ = 1, variant = LogicalRight. The hypercube points (0, 0), (1, 0), (0, 1), (1, 1) can be lexicographically ordered into an array [(0, 0), (1, 0), (0, 1), (1, 1)] Then, by considering the index of each hypercube point in the above array, we observe: * $f((1, 0), (0, 0)) = 1$ because $0 + 1 = 1$ * $f((0, 1), (1, 0)) = 1$ because $1 + 1 = 2$ * $f((1, 1), (0, 1)) = 1$ because $2 + 1 = 3$ and every other pair of $b$-variate hypercube points $x, y \in {0, 1}^{b}$ is s.t. f(x, y) = 0. Using these shift params, if f = [[a_i, b_i, c_i, d_i]_i], then shifted_f = [[0, a_i, b_i, c_i]_i]

Implementations

impl<F: Field> ShiftIndPartialEval<F>

pub fn new( block_size: usize, shift_offset: usize, shift_variant: ShiftVariant, r: Vec<F>, ) -> Result<Self, Error>

pub fn multilinear_extension<P>(&self) -> Result<MultilinearExtension<P>, Error>

where P: PackedFieldIndexable<Scalar = F>,

Evaluates this partially evaluated circular shift indicator MLE $f(X, r)$ over the entire $b$-variate hypercube

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<F: TowerField> MultivariatePoly<F> for ShiftIndPartialEval<F>

fn n_vars(&self) -> usize

The number of variables.

fn degree(&self) -> usize

Total degree of the polynomial.

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

Evaluate the polynomial at a point in the extension field.

fn binary_tower_level(&self) -> usize

Returns the maximum binary tower level of all constants in the arithmetic expression.