Transcript No Slide Title

1
Introduction

We are going to use several consistency
tests for Consistent Readers.
2
Plane Vs. Point Test Representation
Representation:

One variable for each plane p of
planes(), supposedly assigned the
restriction of ƒ to p. (Values of the
variables rang over all 2-dimensional,
degree-r polynomials).

One variable for each point x  .
(Values of the variables rang over the field
).
3
Plane Vs. Point Test - Test
Test:

One local-test for every:
plane p and a point x on p.

Accept if

A’s value on x, and

A’s value on p restricted to x are consistent.
Reminder:
A: planes  dimension-2 degree-r polynomial
4
Plane Vs. Point Test: Error
Probability
Claim:
The error probability of this test is very small, i.e.
< c’/2 , for some known 0<c’<1.
The error probability is the fraction* of pairs <x, p> for a
point x and plane p whose:
 A’s value are consistent, and yet
 Do not agree with any -permissible degree-r
polynomial (on the planes),
* fraction from the set of all combination of (point, plane)
5
Plane Vs. Point Test: Error
Probability - Proof
Proof:
By reduction to Plane-Vs.-Plane test:
replace every

by a

Local-test for p1 & p2 that intersect by a
line l,
Set of local-tests, one for each point x on l,
that compares p1’s & p2’s values on x.
Let’s denote this test by PPx-Test
What is its error-probability?
6
Plane Vs. Point Test: Error
Probability - Proof Cont.
Proposition: The error-probability of PPx-Test is
“almost the same“ as Plane-Vs.-Plane’s.
Proof:
The test errs in one of two cases:
 First case:



p1 & p2 agree on l, but
Have impermissible values (i.e. they do not
represent restrictions of 2 -permissible
polynomials).
Second case:


p1 & p2 do not agree on l, but
Agree on the (randomly) chosen point x on l.
7
Plane Vs. Point Test: Error
Probability - Proof Cont.

In the first case Plane-Vs.-Plane also errs, so
according to [RaSa], for some constant 0<c<1
Pr(First-Case Error) c

For the second case, recall that:

r
= #points, that two r-degree, 1-dimensional
polynomials can agree on.
|| = #points on the line l.
So Pr(Second-Case Error) r/||

PPx-Test’s error-probability  c + r/||
8
Plane Vs. Point Test: Error
Probability - Proof Cont.
For an appropriate  (namely: cO(r/||)):
c + r/|| = O(c)
So, PPx-Test’s error-probability is
 c’, for some 0<c’<1
9
Plane Vs. Point Test: Error
Probability - Proof Cont.
Back to Plane-Vs.-Point:

Let pplanes, x(points on p), such that:
 A(p) and A(x) are impermissible.

Let llines such that x  l

Let p1, p2 be planes through l
Plane-Vs.-Point’s error probability is:
Pr p, x ( (A(p))(x) = A(x) ) =
= Pr lx, p1 ( (A(p1))(x) = A(x) )
10
Plane Vs. Point Test: Error
Probability - Proof Cont.
Prp, x ( (A(p))(x) = A(x) )
= Prlx, P1 ( (A(p1))(x) = A(x) )
=* Elx ( Prp1 ( (A(p1))(x) = A(x) | xl ) )
=** Elx ( (Prp1, p2 ( (A(p1))(x) = (A(p2))(x) = A(x) | xl ) )1/2 )
 ( Elx (Prp1, p2 ( (A(p1))(x) = (A(p2))(x) = A(x) | xl ) )1/2
* ( Prlx, p1, p2 ( (A(p1))(x) = (A(p2))(x) = A(x) )1/2
*** (c’)1/2
*
event A, and random variable Y, Pr(A) = EY( Pr(A|Y) )
Prp1, p2 ( (A(p1))(x) = (A(p2))(x) = A(x) | xL ) ) = (p1,p2 are independent)
(Prp1 ( (A(p1))(x) = A(x) | xl ) )* (Prp1 ( (A(p2))(x) = A(x) | xl ) ) =
(Prp1 ( (A(p1))(x) = A(x) | xl ) )2
*** PPx-Test
**
11
Plane Vs. Point Test: Error
Probability - Proof Cont.
Conclusion:
We’ve established that:
Plane-Vs.-Point error probability, i.e.,
The probability that p (which is random) is
 Assigned an impermissible value, and
 This value agrees with the value assigned
to x (which is also random),
is < c’/2.
Note: This proof is only valid as long as the point x
whose value we would like to read is random. 12
Reading an Arbitrary Point
Can we have similar procedure that
would work for any arbitrary point x?
i.e., a set of evaluating functions, where the function
returns an impermissible value with only a small (<c’)
probability.
Such procedure is called:
consistent-reader.
13
Consistent Reader for Arbitrary
Point

Representation: As in Plane-Vs-Point test.

local-readers: Instead of local-tests, we have a
set of (non Boolean) functions, [x] = {1,...,m},
referred to as: local-readers.
A local reader, can either reject or return a value
from the field .
[supposedly the value is ƒ(x), with ƒ a degree-r polynomial].
14
3-Planes Consistent Reader
for a Point x
Representation: One variable for each plane.
Consistent-Reader:


For a point x, [x] has one local-reader [p2, p3] for
every pair of planes p2 & p3 that intersects by a line l.
Let p1 be the plane spanned by x and l, [p2, p3]

rejects, unless A’s values on p1, p2 & p3 agree on l,

otherwise: returns A’s value on p1 restricted to x.
15
Consistency Claim
Claim: With high probability (  1-c’)
 R [x] either rejects or returns a
permissible value for x.
[i.e., consistent with one of the permissible polynomials].
Remarks:


The sign R is used for “randomly select from…”.
Note that randomly selecting X and using it with l to
span P1 is equal to randomly selecting l in P1 .
16
with high probability
Consistency Proof
Proof:


The value A assigns l, according to p2 & p3’s
values, is permissible w.h.p. (1-c’).
On the other hand, l is a random line in p1 and
if p1 is assigned an impermissible value (by A),
then that value restricted to most l’s would
be impermissible.
17
Consistent-Reader for Arbitrary k
points
How can we read consistently more
than one value ?
Note: Using the point-consistent-reader, we need to
invoke the reader several times, and the received values
may correspond to different permissible polynomials.


Let  = {x1, .., xk} be tuple of k point of the
domain ,
[  ] = { 1, .., m } is now set of functions, which
can either reject or evaluate an assignment to
18
x1, .., xk.
Hyper-Cube-Vs.-Point ConsistentReader For k Points
Representation:

One variable for every cube (affine
subspace) of dimension k+2, containing .
(Values of the variables rang over all degree-r,
dimension k+2 polynomials )

one variable for every point x .
(Values of the variables rang over  ).
19
Hyper-Cube-Vs.-Point ConsistentReader For k Points

Show that the following distribution:



Choose a random cube C of dimension k+2
containing 
Choose a random plane p in C
Return p
Produces a distribution very close to uniform
over planes p
Also, p w.h.p. does not contain a point of .
20
Consistent Reader For k Values
Consistent-Reader:

- Cont.
One local-reader for every cube C containing  and
a point y  C, which


rejects if A’s value for C restricted to y
disagrees with A’s value on y,
otherwise: returns A’s values on C restricted to
x1, .., xk.
21
Proof of Consistency
Error Probability: c’/2
Suppose,
 We have, in addition, a variable for each plane,
 The test compares A’s value on the cube C

against A’s value on a plane p, and then

against a point x on that plane.
The error probability doesn’t increase.
22
Proof of Consistency - Cont.
Proposition: This test induces a
distribution over the planes p which is
almost uniform.
Lemma: Plane-Vs.-Point test works the
same if instead of assigning a single
value, one assigns each plane with a
distribution over values.
23
Summary

We saw some consistent readers and
how “accurate” they are. They will be a
useful tool in this proof.
24