Karin`s slides about Section 4.1
Download
Report
Transcript Karin`s slides about Section 4.1
Derandomized DP
Thus far, the DP-test was over sets of size k
For instance, the Z-Test required three
random sets: a set of size k, a set of size k-k’
and a set of size k’
When k q the input size is exponential in d
d
Derandomized DP
It is possible to have input size of d and still
get all the results (or almost all) as presented
in section 3 (with input size of k)
The domain is U Fqm
The function stays the same: f : U R
For example R could be R 0,1 for a Booleanfunction
Derandomized DP
The k-wise DP of a function f is: f
Where k is all the points in a subspace A
A is a d-dimensional linear subspace of U
k
A
Thus, we have k q d points in A with input size of d
Since now, we only need to know the d-vectors that
define the subspace A (and not k items of a set A)
Derandomized Z-Test
The operator “+” is: A B a b a A b B
A and B are subspace of U, a and b are vectors and
a+b is the component-wise addition of those vectors
The test requires four random subspaces;
d0-dimensional subspaces and (d-d0)-dimensional
subspaces
Where d 25 and d0 d
and k q d
25
Derandomized Z-Test
The test is (as presented in the paper)
Pick a random d0-dimensional subspace A0 and a
random (d-d0)-dimensional subspace B0 of U that is
linearly independent from A0
Pick a random (d-d0)-dimensional subspace B1 of U
that is linearly independent from A0. Reject if
C
. A0 B0 A C A0 B1 A , else continue
0
0
Pick a random d0-dimensional subspace A1 of U that
is linearly independent from B1. Reject if
. A0 B1 B1 C A1 B1 B1 , else accept
C
Derandomized Z-Test
Theorem 1.2: (equivalent to Theorem 1.1 for the
non-derandomized Z-Test)
Suppose the derandomized Z-Test accepts with
probability , for 1
1
k
Then there is a function g : U R such that, for
each of at least 4 fraction of d-dimensional
subspaces S from U, the oracle value C(S) agrees
with the direct product g k S for all but at most k 1
fraction of elements in S
Section 4
The proof of Theorem 1.2
Derandomized Z-Test
The proof of this Theorem is on section 4
B consistent with a pair (A0,B0)
C A0 , B0
A0
C A0 , B
A0
Where the subspace A0 is linearly independent from
B and B0
The set Cons A0 , B0 (defined as before) – its members are
all the B’s that are consistent with a pair (A0,B0)
Good/Excellent pair
Pair (A0,B0) is good The size of the set Cons A0 , B0 ,
m d0
2
d
d
0
is at least
;i.e. has a measure at least 2
Pair (A0,B0) is (,γ)-excellent The pair (A0,B0)
is good and
E D Cons
i
PrE , D1 , D2
C A0 E D1
A0 , B0
, i 1, 2
A0 E
C A0 E D2
A0 E
Where (1) the subspace A0 is linearly independent from E, D1
and D2, and (2) the subspace E is linearly independent from
D1 and D2 and (3) E is a d0-dimensional subspace (as A0)
Excellence - Lemma 4.1
Lemma 4.1 (analogues of Lemma 3.2) –
Assume that
PrA , B , B C A0 B0 A C A0 B1 A
Then a random pair (A0,B0) is good with
probability at least 2
0
0
1
0
0
Proof: Nothing really changed from the proof
of Lemma 3.2
Excellence - Lemma 4.2
Lemma 4.2 (analogues of Lemma 3.3) –
PrA0 , B0 A0 , B0 is good but not excellent '
2
'
O
q
a k '
where
Proof:
(1) Let the event 1 A0 , B0 be the event good
but not excellent; i.e. the pair (A0,B0) is good and
E Di Cons A , B , i 1, 2
PrE , D1 , D2
C A0 E D1
0
0
'
A0 E
C A0 E D2
A0 E
Excellence - Lemma 4.2
Proof – continue:
(2) Let the event 2 A0 , B0 , E, D1 , D2 (A0,B0) is
good and E Di ConsA , B , i 1, 2 and
C A0 E D1
'
A0 E
0
0
C A0 E D2
A0 E
(3) By using Lemma 2.2 we get Pr 2 '
(4) According to (2) + (1) Pr 2 1
Excellence - Lemma 4.2
Proof – continue:
(5) According to (3) - Pr 2 ' then it is clear
that Pr 2 1 Pr 2 '
(6) Since Pr 2 1 Pr 2 1 Pr 1 , then
according to (4) + (5) we’ll get:
Pr 2 1 Pr 2 1 Pr 1 ' Pr 1
' Pr 1
Pr 1 '
Excellence - Corollary 4.3
Corollary 4.3 (analogues of Corollary 3.4) –
Assume that
PrA , B , B C A0 B0 A C A0 B1 A
Then we have
PrA , B A0 , B0 is , excellent A0 , B0 is good 1 2
where and γ are such that k ' poly 1 3
0
0
0
1
0
0
0
Proof: By using Lemma 4.2 and where c0 1
2q 2
Excellence implies Local
Agreement
Subsection 4.2
Subsection 4.2 – Local Agreement
In this section we set: (for some fixed , excellent A , B )
0
0
Cons to be Cons A , B
0 0
A0 and E are d0-dimensional subspaces
D1 and D2 are (d-2d0)-dimensional subspaces
The function g is now:
C A0 B0 x
g x PluralityBCons:x A0 B
0
x A0
x U A0
B Cons x A0 B
else
Local Agreement - Lemma 4.4
Lemma 4.4 (analogues of Lemma 3.5) –
2
v
O
fraction of
There are fewer than
.B Cons such as that C A0 B0 x g x for
more than 40 fraction of x A0 B
Proof by contradiction: By assuming that
PrBCons C A0 B g A0 B v
Local Agreement - Lemma 4.4
Proof – continue:
Since A0 , B0 is excellent and therefore is good
then we can assume now that also
PrB B cons C A0 B g A0 B v ' v
2
From now on, the sampling procedures are changing,
thus instead of taking one subspace to be linearly
independent from the other one we will take the
subspace to be orthogonal to the other one
Sampling Procedure
For every d0-dimensional subspace A0, thus A0 U.
The set of all the vectors orthogonal to A0 is a
subspace of U, we denote this set as A0
Denote B A0 a subspace orthogonal to A0
Every subspace B has an orthogonal basis B’ where
.span B ' span B and thus we may define Si as the
equivalence class:
Si B B A0 span Bi' span B
Sampling Procedure
For every subspace B linearly independent from A0,
let B denote the dual of A0 inside A0+B
Since B is also a subspace it has as well an
orthogonal basis B’, thus span B span B ' span B
Therefore – A0 B A0 B
For those subspaces B, we may define Ti as the
equivalence class:
Ti B span B span B B Si
Sampling Procedure
The claims 4.5-4.7 refer to any random event E(B)
which depends on the subspace A0+B rather then B
itself
Thus the probability of the this event is the same
when We uniformly choose a subspace B linearly
independent from A0
Or when we uniformly choose a subspace B
orthogonal to A0
Sampling Procedure
Set B: all the (d-d0)-dimensional subspaces
linearly independent from A0 thus Cons B
Set B: all the (d-d0)-dimensional subspaces
orthogonal to A0
Defining Cons= Cons B
Sampling Procedure
Claim 4.5 - |Cons|/|B| = |Cons|/|B|
Proof:
Sampling Procedure
Set Bx: all the (d-d0)-dimensional subspaces
linearly independent from A0 such as that
x A0 B
Defining Consx Cons Bx
Claim 4.6 - |Consx|/|Bx| = |(Consx)|/|(Bx)|
Proof: Proved for every x U \ A0
Sampling Procedure
Set BE: all the (d-d0)-dimensional subspaces linearly
independent from A0 and contain the subspace E
Set (BE): all the (d-d0)-dimensional subspaces
orthogonal to A0 that contain E
Defining ConsE Cons BE
Defining (ConsE) Cons (BE)
Sampling Procedure
Claim 4.7 - |ConsE|/|BE| = |(ConsE)|/|(BE)|
Proof: Pretty much the same as the others…
so I’ll skip it
Sampling Procedure
Say a pair (A0,B0) is good for a subspace B0 linearly
independent from A0 then Cons has a measure of μ
By using claim 4.5, since there is B such as that
.A0 B0 A0 B , we will get that Cons has also
a measure of μ
Thus, if the pair (A0,B0) is good then also the pair
(A0,B) is good
Sampling Procedure
For an , excellent A0 , B pair, the measure of
Cons stays the same, and by using claim 4.7
the probability in the equation
E Di Cons A , B , i 1, 2
PrE , D1 , D2
C A0 E D1
0
0
'
A0 E
C A0 E D2
A0 E
The definition of function g(x) stays the same
by using claim 4.6
Sampling Procedure
Since good, excellent and g(x) remains the same we
may use this method of sampling in order to prove
Lemma 4.4
Thus, assuming PrBCons C A0 B g A0 B v
and since also good (previews
slide) then by
assuming
PrB B cons C A0 B g A0 B v ' v
2
we will get a contradiction
Proof of lemma 4.4
Claims 4.8 – 4.12 are needed for this proof and they
are analogue of Claims 3.8-3.12 respectively
Claim 4.8 – For all but at most 1 k 1 5 fraction of the
input x U \ A0, we have |Consx|/|Bx| 6
Proof: Referring to (Bx) as Bx and to Consx as
(Consx) and proving it to at most 1 k 0.20 fractions
Proof of lemma 4.4
Claim 4.9 – Let x be any input such as that
Consx has measure at least /6 in Bx. Then for
all but at most O 1 k1 4 fraction of linear
subspace E orthogonal to A0 as such that
x A0 E, we get that
PrBConsE C A0 B x g x 1
10
Proof:
Proof of lemma 4.4
Claim 4.10 – For O 1 k 1 5 ,
PrE , x A0 E \ A0 PrBConsE C A0 B x g x 1 1
10
where E is a random d0-dimensinal linear
subspace orthogonal to A0
Proof: By using claim 4.8 and 4.9, for x where
xA0+E such as that Consx is large.
Proof of lemma 4.4
Claim 4.11 – For ' O 1 k 3 25 ,
x A0 E \ A0
1 '
PrE
PrBConsE C A0 B x g x 110
where E is a random d0-dimensinal linear
subspace orthogonal to A0
Proof: If we have enough time…
Proof of lemma 4.4
Claim 4.12 – For all but at most 1 k 1 4
fraction of d0-dimensinal linear subspaces E,
orthogonal to A0, we have |ConsE|/|BE| 6
Proof: Analogue of Claim 4.8, almost the
same proof, but except of choosing x such as
xA0+E, we pick E – a random d0-dimensinal
linear subspace orthogonal to A0
Proof of lemma 4.4
Proof:
Local Agreement implies
Global Agreement
Subsection 4.3 – The proof of theorem 1.2
Global Agreement - Lemma 4.13
Lemma 4.13 (analogues of Lemma 3.13) – If
the derandomized Z-test accepts with
probability at least , then there is a function
g:U→R such as that for at least ’= /4
fraction of all subspaces S, the oracle C(S)
agrees with g(S) in all but at most ’=81
fraction of points x S
Proof: