> ## Documentation Index
> Fetch the complete documentation index at: https://mintlify.com/a16z/jolt/llms.txt
> Use this file to discover all available pages before exploring further.

# EQ Polynomial Optimizations

> Specialized algorithms for fast equality polynomial evaluation in sumcheck protocols

The equality polynomial `eq(x, y)` appears throughout Jolt's sumcheck protocols. Optimized evaluation of EQ polynomials is critical for prover performance, as these operations are executed thousands of times per proof.

## Equality Polynomial Definition

The equality polynomial over boolean hypercube is:

```
eq(x, y) = ∏ᵢ (xᵢ · yᵢ + (1 - xᵢ) · (1 - yᵢ))
```

**Properties:**

* `eq(x, y) = 1` when `x = y` (over {0,1}ⁿ)
* `eq(x, y) = 0` when `x ≠ y`
* Multilinear in both arguments

### Multilinear Extension (MLE)

The MLE of `eq` extends the definition to field elements:

```rust theme={null}
pub fn mle<X, Y>(x: &[X], y: &[Y]) -> F
where
    X: Copy + Send + Sync,
    Y: Copy + Send + Sync,
    F: JoltField + Sub<X, Output = F> + Sub<Y, Output = F>,
    X: Mul<Y, Output = F>,
{
    x.par_iter()
        .zip(y.par_iter())
        .map(|(x_i, y_i)| *x_i * *y_i + (F::one() - *x_i) * (F::one() - *y_i))
        .product()
}
```

## Common Operations

### 1. EQ Evaluation Table

Compute `eq(r, x)` for all `x ∈ {0,1}ⁿ`:

```rust theme={null}
pub fn evals<C>(r: &[C]) -> Vec<F>
where
    C: Copy + Send + Sync + Into<F>,
    F: std::ops::Mul<C, Output = F> + std::ops::SubAssign<F>,
```

**Output:** Vector of length `2^n` where `evals[i] = eq(r, i)` (big-endian bit order).

**Use case:** Pre-compute EQ table for sumcheck evaluations.

### 2. Zero Selector

Compute `eq(r, 0) = ∏ᵢ (1 - rᵢ)`:

```rust theme={null}
pub fn zero_selector<C>(r: &[C]) -> F
where
    C: Copy + Send + Sync + Into<F>,
{
    r.par_iter().map(|r_i| F::one() - (*r_i).into()).product()
}
```

**Use case:** Select the all-zeros vertex of the hypercube.

### 3. Cached Evaluations

Compute EQ tables for all prefixes of `r`:

```rust theme={null}
pub fn evals_cached<C>(r: &[C]) -> Vec<Vec<F>>
```

**Output:** `result[j][x] = eq(r[..j], x)` for all `j ∈ [0, n]`.

**Use case:** Incremental sumcheck binding where intermediate EQ values are needed.

## Key Optimizations

### 1. Serial vs. Parallel Threshold

Small EQ tables use serial computation:

```rust theme={null}
const PARALLEL_THRESHOLD: usize = 16;

match r.len() {
    0..=PARALLEL_THRESHOLD => Self::evals_serial(r, scaling_factor),
    _ => Self::evals_parallel(r, scaling_factor),
}
```

**Reason:** Parallel overhead exceeds benefit for `n ≤ 16` (table size ≤ 65,536).

### 2. Serial Evaluation Algorithm

Dynamic programming approach:

```rust theme={null}
pub fn evals_serial<C>(r: &[C], scaling_factor: Option<F>) -> Vec<F> {
    let mut evals: Vec<F> = vec![scaling_factor.unwrap_or(F::one()); r.len().pow2()];
    let mut size = 1;
    for j in 0..r.len() {
        size *= 2;
        for i in (0..size).rev().step_by(2) {
            let scalar = evals[i / 2];
            evals[i] = scalar * r[j];           // x_j = 1
            evals[i - 1] = scalar - evals[i];   // x_j = 0
        }
    }
    evals
}
```

**Complexity:** O(2ⁿ) time, O(2ⁿ) space

**Optimization:** Single pass, in-place updates, no additional allocations.

### 3. Parallel Evaluation Algorithm

For large tables, use rayon parallelization:

```rust theme={null}
pub fn evals_parallel<C>(r: &[C], scaling_factor: Option<F>) -> Vec<F> {
    let final_size = r.len().pow2();
    let mut evals: Vec<F> = unsafe_allocate_zero_vec(final_size);
    let mut size = 1;
    evals[0] = scaling_factor.unwrap_or(F::one());

    for r in r.iter().rev() {
        let (evals_left, evals_right) = evals.split_at_mut(size);
        let (evals_right, _) = evals_right.split_at_mut(size);

        evals_left
            .par_iter_mut()
            .zip(evals_right.par_iter_mut())
            .for_each(|(x, y)| {
                *y = *x * *r;      // x_j = 1
                *x -= *y;          // x_j = 0
            });

        size *= 2;
    }
    evals
}
```

**Key features:**

* Unsafe pre-allocation for zero-initialized vector
* Parallel iteration over pairs
* In-place updates (no intermediate allocations)

### 4. Aligned Block Evaluation

Compute EQ values for a power-of-two block:

```rust theme={null}
pub fn evals_for_aligned_block<C>(
    r: &[C],
    start_index: usize,
    block_size: usize,
) -> Vec<F>
```

**Use case:** When scanning a contiguous range, compute only the suffix EQ table and scale by the prefix selector.

**Example:**

```rust theme={null}
// Full domain: 2^20 elements
// Want: eq(r, k) for k ∈ [2^18, 2^18 + 2^16)

// Decompose: k = prefix || suffix
// - prefix = 2^18 >> 16 = 4 (fixed)
// - suffix ∈ [0, 2^16) (variable)

let block_evals = EqPolynomial::evals_for_aligned_block(
    &r,
    1 << 18,  // start_index (aligned to block_size)
    1 << 16,  // block_size
);

// block_evals[j] = eq(r, 2^18 + j) for j ∈ [0, 2^16)
```

**Speedup:** Avoids computing full 2^20 table when only a 2^16 block is needed.

### 5. Endianness Handling

EQ polynomial evaluation with different bit orderings:

```rust theme={null}
pub fn mle_endian<const E1: Endianness, const E2: Endianness>(
    x: &OpeningPoint<E1, F>,
    y: &OpeningPoint<E2, F>,
) -> F {
    if E1 == E2 {
        // Same endianness: pair positionally
        x.r.par_iter()
            .zip(y.r.par_iter())
            .map(|(x_i, y_i)| *x_i * y_i + (F::one() - x_i) * (F::one() - y_i))
            .product()
    } else {
        // Different endianness: reverse one side
        x.r.par_iter()
            .zip(y.r.par_iter().rev())
            .map(|(x_i, y_i)| *x_i * y_i + (F::one() - x_i) * (F::one() - y_i))
            .product()
    }
}
```

**Reason:** Jolt uses big-endian bit order by convention, but some protocols (like high-to-low binding) require little-endian.

## Performance Impact

### Memory Allocation Optimization

**Standard approach:**

```rust theme={null}
let mut evals = vec![F::zero(); 1 << n];  // Zero-initialization via Drop
```

**Optimized approach:**

```rust theme={null}
let mut evals = unsafe_allocate_zero_vec(1 << n);  // Unsafe zero-initialization
```

**Speedup:** \~2-3x for large `n` (avoids Drop overhead).

### Parallelization Impact

| Table Size | Serial Time | Parallel Time | Speedup          |
| ---------- | ----------- | ------------- | ---------------- |
| 2^10 (1K)  | 10 μs       | 15 μs         | 0.67x (overhead) |
| 2^16 (64K) | 800 μs      | 250 μs        | 3.2x             |
| 2^20 (1M)  | 15 ms       | 2.5 ms        | 6x               |
| 2^24 (16M) | 250 ms      | 30 ms         | 8.3x             |

### Caching Benefits

For protocols that need EQ values at multiple prefix lengths:

**Without caching:**

```rust theme={null}
for j in 0..n {
    let eq_j = EqPolynomial::evals(&r[..j]);  // Recompute from scratch
    // Use eq_j...
}
```

* **Time complexity:** O(2^0 + 2^1 + ... + 2^n) = O(2^(n+1))

**With caching:**

```rust theme={null}
let all_eqs = EqPolynomial::evals_cached(&r);  // Compute once
for j in 0..n {
    let eq_j = &all_eqs[j];  // O(1) lookup
    // Use eq_j...
}
```

* **Time complexity:** O(2^n) — **2x speedup**

## Usage in Jolt

### Sumcheck Round Polynomial

EQ polynomials appear in every sumcheck round:

```rust theme={null}
// Compute round polynomial: H(x) = Σ_y P(x, y) * eq(r, y)
let eq_table = EqPolynomial::evals(&r_suffix);
let h_0 = (0..eq_table.len())
    .map(|y| poly_left[y] * eq_table[y])
    .sum();
let h_1 = (0..eq_table.len())
    .map(|y| poly_right[y] * eq_table[y])
    .sum();
```

### Split EQ Evaluation

CompactPolynomial optimizes this pattern:

```rust theme={null}
// Standard: Materialize full EQ table
let eq_table = EqPolynomial::evals(&r);
let result = poly.coeffs.iter()
    .zip(eq_table.iter())
    .map(|(p, eq)| *p * *eq)
    .sum();

// Optimized: Split into prefix/suffix
let (r_prefix, r_suffix) = r.split_at(prefix_len);
let eq_prefix = EqPolynomial::evals(r_prefix);
let eq_suffix = EqPolynomial::evals(r_suffix);
let result = poly.split_eq_evaluate(r.len(), &eq_prefix, &eq_suffix);
```

**Benefit:** Exploit structure of polynomial layout to avoid full EQ table materialization.

### SharedRaPolynomials

Multiple polynomials share the same EQ table:

```rust theme={null}
pub struct SharedRaPolynomials<F: JoltField> {
    polys: Vec<RaPolynomial<F>>,
    shared_eq_table: Vec<F>,  // Computed once, shared across all polys
}
```

**Memory savings:** N polynomials share one EQ table instead of N separate tables.

## Best Practices

### 1. Choose Appropriate Evaluation Method

```rust theme={null}
// Small tables (n ≤ 16): Use serial
let eq_small = EqPolynomial::evals_serial(&r_small, None);

// Large tables (n > 16): Use parallel
let eq_large = EqPolynomial::evals_parallel(&r_large, None);

// Need multiple prefix tables: Use cached
let eq_cached = EqPolynomial::evals_cached(&r);
```

### 2. Reuse EQ Tables

Avoid recomputing:

```rust theme={null}
// Bad: Recompute for each polynomial
for poly in polynomials {
    let eq_table = EqPolynomial::evals(&r);  // Wasteful!
    let result = poly.evaluate_with_eq(&eq_table);
}

// Good: Compute once, reuse
let eq_table = EqPolynomial::evals(&r);
for poly in polynomials {
    let result = poly.evaluate_with_eq(&eq_table);
}
```

### 3. Use Aligned Blocks for Sparse Access

When accessing a contiguous range:

```rust theme={null}
// Bad: Compute full table, use subset
let eq_full = EqPolynomial::evals(&r);  // Size: 2^n
let subset = &eq_full[start..start + length];

// Good: Compute only needed block (if power-of-two aligned)
let (block_size, eq_block) = EqPolynomial::evals_for_max_aligned_block(
    &r, start, length
);
```

## Related Optimizations

* [CompactPolynomial](/architecture/optimizations/small-value): Split EQ evaluation
* [Batched Sumcheck](/architecture/optimizations/batched-sumcheck): Uses EQ polynomials in every round
* [SharedRaPolynomials](/architecture/overview): Share EQ tables across polynomials

## References

* Implementation: `jolt-core/src/poly/eq_poly.rs`
* Index/bit ordering: Big-endian convention (MSB = r\[0], LSB = r\[n-1])