Transcript Encodings

1
Introduction
In this lecture we’ll cover:






Definition of strings as functions and vice
versa
Error correcting codes
Low degree polynomials
Low degree extension
Consistent readers
Consistency tests
2
Strings & Functions

Let  = 1 2 . . . 3, where i.
We can describe the string  as a function
 : [1…n]  , such that i (i) = i.

Let f be a function f : D  R. Then f can
be described as a string over the alphabet
 = R|D|, spelling f’s value on each point of
D.
3
Strings & Functions - Example
For example, let f be a function f : Z5  Z5,
and let  = Z5.
f(x) = x2

 = 0, 1, 4, 4, 1
4
Error Correcting Codes
Definition (encoding): An encoding E is a
function E : n  m, where m >> n.
Definition (-code): An encoding E is an
-code if n (E(),E())  1 - ,
where (x,y), denotes the fraction of
entries on which x and y differ.
5
A Generic -code
Set F to be the finite field Zp for some
prime p, and assume for simplicity that
 = F and m = p.
Given n, let E() be the string of the
function f : F  F that satisfies:
f is the unique n – 1 degree polynomial
such that f(i - 1) = i for all 1  i  n.
6
A Generic -code (2)

E() can be interpolated from any n points.

Hence, for any , E() and E() may agree
on at most n – 1 points.

Therefore, E is an (n – 1) / m - code.
7
A Generic -code - Example
p = m = 5, n = 2
 = 1, 2
 = 3, 1
f(x) = x + 1
f(x) = 3x + 3
E() = 1, 2, 3, 4, 0
E() = 3, 1, 4, 2, 0
8
Polynomials Over Finite Fields

Let V = Fd be a geometric space of
dimension d.

Let p be a polynomial p : V  F of degree h
in each variable.

The total degree of p is hd.
9
Properties of Low Degree Polynomials

The value of p on any point of V can be
interpolated from many (almost all) sets of
(h+1)d points of V.
(This is true when the points are linearly
independent).

If p is of a degree greater than hd, then
interpolation of a single point xV from
different sets of (h+1)d points may give
different values (be inconsistent).
10
Properties of Low Degree Polynomials (2)

Two distinct polynomials, p1 and p2, can
agree on at most a very small () fraction
of V, i.e. (p1,p2)  1 - .
11
Properties of Low Degree Polynomials (3)

The restriction of a polynomial of degree h
in each variable to an affine sub-space of
dimension d’ is a polynomial of dimension d’
and degree h in each variable.

The restriction of a polynomial p of degree
h in each variable to a curve  : F  V of
degree k, p((t)) is a univariate polynomial
of degree hk.
12
Low Degree Extension (LDE)
Definition (low degree extension): Assume
H  F, such that |H| << |F|, and let
d = log|H|n.
A string n is describable as a function
 : Hd  .
LDE() is a function LDE() : Fd  F such
that:
 LDE() agrees with  on Hd (extension).
 LDE() is of degree |H| - 1 in each
variable (low degree).
13
Consistent Reading
We need to be able to read a value of an
LDE in a globally consistent manner.
 That is, have a representation scheme (a
set of variables) for LDE(), and a reading
procedure, that for any xV accesses a
very small number of representation
variables and:
 Rejects if inconsistency detected.
 Otherwise, returns with high probability
a value for LDE()(x), consistent among
all points x.

14
Consistency
A simple procedure: interpolate value from a
set of (h+1)d points.
This, however, requires (h+1)d points, while
we would need a consistent-reader which
accesses only a very small (preferably
poly-log(n), ultimately constant) number of
variables.
15
Consistency Test
A consistency test requires only that value
for a random xV corresponds to a global
degree-h polynomial.
Notice that this is a weaker requirement
than the one stated in the consistent
reader definition, since it allows some x’s
to be accepted with high probability
although they do not agree with the global
consistency, as long as the probability over
all x’s remains low.
16
Consistency Test (2)

Fix a representation: a set of variables.

A test is a family of boolean functions over
representation variables, each depending
on a small set of variables, hence referred
to as a local test – which may:
 Reject if inconsistency detected.
 Accept with high probability values
conform to global consistency.
17
Consistency Test (3)
P(0,0,0) P(0,0,1) P(0,0,2) P(0,0,3) P(0,0,4) P(0,0,5) P(0,0,6)
3
P(0,1,0)
P(0,1,1) P(0,1,2) P(0,1,3) P(0,1,4) P(0,1,5) P(0,1,6)
P(0,2,0) P(0,2,1) P(0,2,2)
5 P(0,2,3) P(0,2,4) P(0,2,5) P(0,2,6)
P(0,3,0) P(0,3,1) P(0,3,2) P(0,3,3) P(0,3,4) P(0,3,5) P(0,3,6)
P(6,6,0) P(6,6,1) P(6,6,2) P(6,6,3) P(6,6,4)
2 P(6,6,5) P(6,6,6)
18
Global Consistency
Definition (pure global consistency): Pure
global consistency would be for all xV to
be assigned values consistent with a single
low degree polynomial.
This cannot be detected by a local test, since
changing the values in a small fraction of
points will be detected only with low
probability.
19
Corresponding Game
Prover sets values to all variables in the
representation.
 Verifier picks randomly a single local-test
and accepts or rejects according to its
output.
 The error-probability of a test is the
fraction of local tests that may accept
although the assigned values do not
conform to global consistency.

20