Transcript Code Test

Analysis of Boolean Functions
Fourier Analysis,
Projections,
Influence,
Junta,
Etc…
Slides prepared with help of Ricky Rosen
Codes and Boolean Functions
Def: an m-bit binary code is a subset of the
set of all m-binary strings
C{-1,1}m
The distance of a code C, is the minimum, over
all pairs of legal-words (in C), of the
Hamming distance between the two words
A Boolean function over n binary
variables, is a 2n-bit string
Hence, a set of Boolean functions can be
considered as a 2n-bits code
Hadamard Code
In the Hadamard code the set of legalwords consists of all multiplicative
functions.
(linear if over {0,1})
C={S | S  [n]}
namely all characters
Hadamard Test
Given a Boolean f, choose
random x and y; check that
f(x)f(y)=f(xy)
Prop(perfect completeness): a
legal Hadamard word (a
character) always passes this
test
Hadamard Test – Soundness
Prop(soundness):
1+
Pr[f(x)  f(y)  f(xy)]>
 S  [n], f S   
2
Proof:
if f(x)f(y)=f(xy) , then f(x)f(y)f(xy)=1
else f(x)f(y)f(xy)=-1
x,y[f(x)f(y)f(xy)]=
1Pr[f(x)f(y)=f(xy)] -1Pr[f(x)f(y)f(xy)] 
½(1+) -½(1-)= 
6
proof
 <Ex,y [f(x)  f(y)  f(xy)]=
Exy f  x  = Ex S fˆ S  S  x   = S fˆ S  Ex S  x 


=
 f S  f S  f S  E [ (x)   (y)   (xy)]=
S  x  y   S  x   S  y 
1
S1 ,S2 ,S3
=
3
x,y
 f S  f S  f S  E
1
S1 ,S2 ,S3
=
2
2
3
x,y
1
= f  S 
3
S
S2
S3
[S1 (x)  S2 (y)  S3 (x)  S3 (y)]=
Exy  S  x  S  y    Ex  S  x   Ey  S  y  
 f S  f S  f S  E [
S1 ,S2 ,S3
S1
2
3
x
S1
(x)  S3 (x)]  Ey [S2 (y)  S3 (y)]=
S1  S2 = 1 if S1  S2 else S1  S2 = 0 (orthonormal basis)
Proof cont.



S  [n], f S  
Conclusion:
Proof 1: (probabilistic method) –
consider random variables that with
2
probability f S are valued f S
And its expectation is > then one of its
variables > .
Proof 2: (algebraic): if S  [n], f S  
then  f S    f S   
3
S

How large can
2
S
S  [n] f S   
be?
Juntas

A function is a J-junta if its value
depends on only J variables.
-1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1

1 -1 1
A Dictatorship is 1-junta
-1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1
1 -1 1
-1
Long-Code
In the long-code the set of legal-words consists of all
monotone dictatorships
This is the most extensive binary code, as its bits
represent all possible binary values over n elements
Long-Code


Encoding an element e[n] :
Ee legally-encodes an element e if Ee = fe
F
F
T
T
T
Testing Long-code
Def(a long-code list-test): given a code-word f,
probe it in a constant number of entries, and


Completeness (not perfect):
accept almost always if f is a monotone dictatorship
Soundness:
reject w.h.p if f does not have a sizeable fraction of
its Fourier weight concentrated on a small set of
variables, that is, if  a semi-Junta J[n] s.t.
2
 f S  
S J
Note: a long-code list-test, distinguishes
between the case f is a dictatorship, to the
case f is far from a junta.
Motivation – Testing Long-code


The long-code list-test are essential tools in
proving hardness results.
Hence finding simple sufficient-conditions for
a function to be a junta is important.
What about a Hadamar like test?


completeness?
yes
Soundness?
We would like something like:
2
1+
Pr f  x   f  y   f  xy   >
 J  n ,  f S >
2
S J
 Which functions will pass the test?


all the characters for start
and many more…
no
Perturbation
Def: denote by p the
distribution over all subsets of
[n], which assigns probability to
a subset x as follows:
independently, for each i[n], let


ix with probability 1-p
ix with probability p
Long-Code Test
Given a Boolean f, choose
random x and y, and choose
z; check that
f(x)f(y)=f(xyz)
Prop(completeness): a legal longcode word (a dictatorship)
passes this test w.p. 1-
Long-code Test – Soundness
Prop(soundness):
2
1+
Pr[f(x)  f(y)  f(xyz)]>
 J  [n],  f S >  2
2
S J
Proof:
 <Ex,y,z [f(x)  f(y)  f(xyz)]=
=
 f S  f S  f S  E
[S1 (x)  S2 (y)  S3 (xyz)]=
 f S  f S  f S  E
[S1 (x)  S2 (y)  S3 (x)  S3 (y)  S3 (z)]=
 f S  f S  f S  E [
S1
1
S1 ,S2 ,S3
=
1
S1 ,S2 ,S3
=
1
S1 ,S2 ,S3
2
2
S
3
2
= f  S   1  2 
3
3
3
S
x,y,z
x,y,z
x
(x)  S3 (x)]  Ey [S2 (y)  S3 (y)]  Ez [S3 (z)]=
 S  z  =   zi   zi  1  2 
z
z
iS
iS
S
zi
17
Proof cont.

Try to find k s.t.
to get
3
 f2 S<
S k
2
< f  S   1  2  < f  S  
S
S
S

2
2
2
 f S    f S 
S k
S k
2

 <  f S
2 S k
k can be determined according to  and
the size of the character.
List decoding
This test does not allow
list-decoding a function.
Problem: the function  passes the
test, as well as functions close to it.
Solution (?) assume f is folded (odd):
f(x)=-f(-x) for every x.
(make sure you understand why this is a “solution”)
Junta Test
(1)
(2)
(3)
(4)
Definitions
Independence test
The size test
Soundness and completeness of the tests
Definitions: Variation
Def: the variation of f (extension of influence)


variationI  f   E var fI x   y 

xP I  
 yPI 
Intuition: if I is very influential on f then
the function will go “wild” on yP[I]
hence the expected variance (variation)
is large.
Variation cont.
Prop: the following is an equivalent
definitions to the variation of f:
2
2
variationI  f  f  AI f   f S 
2
Recall fI x S 
2
E fI  x   S   

xP[I ] 

 f T  
T I S
SI 
T
x


2
 E   f T  
f T1  f  T2  T1  x  T2  x  


xP[I ] 
T  I S
T1 ,T2 ,T1 T2


T1 I S,T2 I S


T  I S
2
f T 
2


E var fI  x   y     f T 
 T I 
xP I  
 yPI 

 f  
Recall the variance of f Var
 
var fI x  y   
yP I 

2
Hence
2
xP n
Sn,S
  f x  S 
SI,S
f
S
I
2




E var fI  x   y    E   fI x  S  
 xPI  SI,S
xP I  
 yP I 




S I,S 

2
E fI  x   S 
xP I 
 
S I,S  T:T I S

2
  f T 
T I 
2
f T 
Proof – Cont.


Recall
AI f 

SI 
f(S) S
Therefore (by Parseval):
2
f  AI f 
2

SI 
2
f S 
High vs Low Frequencies
Def: The section of a function f above k is
fk
 f S
S k
S
and the low-frequency portion is
fk
 f S
S k
S
Junta Test
Def: A Junta test is as follows:
A distribution over l queries  : P n  0,1
For each l-tuple, a local-test that either accepts or
rejects:
T[x1, …, xl]: {1, -1}l{T,F}
s.t. for a j-junta f
Prx1 ,..,x  T x1 ,.., x
   f   1

whereas for any f which is not (, j)-Junta
Prx1 ,..,x  T x1 ,.., x  (f)   1 2
The test (l) will be polynomial in j/
Fourier Representation of influence
Recall: consider the I-average function on P[I]
AI f (x)
E f  x  y 
yPI
which in Fourier representation is
and
AI f 

SI 
f(S) S
2
2
influencei  f   1  Ai f   f (S)
2
iS
Subsets` Influence
Recall: The Variation of a subset I  [n] on a
Boolean function f is
2
2
VariationI  f  1  AI f 
2
 f S 
SI 
and the low-frequency influence
k
I
Variation
 f
VariationI  f
k
 
SI 
S k
2
f S 
Independence-Test
The I-independence-test on a Boolean function
f is, for
w  I, z1 ,z2  I
IT(w, z1 ,z2 ):
?
f  w  z1   f  w  z2 
Lemma:
Pr IT(w, z1 ,z2 )  1  21 VariationI  f 
wP I 
 
z1 ,z2 PI
proof
Pr IT(w, z1 ,z2 )  1  21 variationI  f 
wP I 
 
z1 ,z2 PI
Pr f(w â z)=1  E Pr f(w â z)=1
w,z

w  z
AI f w   E f(w â z)
z
 Pr f(w â z)=1  Pr f(w â z)=-1
z
z
Pr f(w â z)=-1  1  Pr f(w â z)=1
z
z
AI f w   1  2Pr f(w â z)=1
z
Pr IT(w, z1 ,z2 )  E 
wP[n] 
wP I 
z1 ,z2PI

1AI f w 
2
 
2

1AI f w 
2

2


2 2 AI f w   

 E 

4

wP[n] 
2
2
 21  21 AI f 2
1
1
2
1  A f 
2
I
2
What
was I
looking
for?
 1  21 variationI  f
Pr IT(w, z1 ,z2 )  1  21 variationI  f 
wP I 
 
z1 ,z2 PI
Junta Test
 The
junta-size-test JT on a
Boolean function f is
 Randomly
for r>>j2
 Run IT
t>>j2/
 Accept
partition [n] to I1, .., Ir
t times on each Ih for
if no more than j of the
Ih fail IT
Completeness
completeness: for a j-junta f only
those Ih that contain a member of
the Junta fail IT.
No more than j sets can fail the
test.
Soundness
Soundness: if f passes the test w.p. ½
then f is (,j) -junta
Proof: utilize bounds on the variation of
those Ih that pass IT.
Intuition: A set, Ih, has probability of
½Variation to fail IT once.
If Ih passes IT t times, one expects
that ½Variation(Ih) < 1/t



Formally (if you insist):
The probability of the event that Ih
fails IT is p= ½Variation.
The probability of Ih to pass IT t times
is (1-p)t.
If it happens w.h.p then
e-pt > (1-p)t > ½
-pt > ln(½)
p < 1/t(-ln(½)) < 1/t
Soundness Proof
Assume the premise. Fix >1/t and let
J  i| influencei  f    
using the bound on p we prove that if f
passes JT then f is  close to a J–junta.
Prop: if JT succeeds w.p > ½ then |J| ≤ j
Proof: otherwise,
J spreads among Ih w.h.p.
and for any Ih s.t. IhJ ≠  it must be that
VariationIh(f) > 
j spread


For a random partition, by birthday
problem, for r>j2 and fix some j
variables from J, w.h.p. no two members
of J fall in the same Ih.
Choose r s.t. w.p.  ¾ at least j+1
members of J are spread in distinct
Ih’s.
I containing one of the variables in J and a fixed iI:
VariationI  f  
2
2
 f S   f S  influence  f
SI 
i
S,iS
iI
and since I contains a variable of J, variationI>
 Since j2/<<t we can choose  s.t. >2/t[ln(j+1)+ln4]
 Now, for a random partition one (like you) can bound the
probability that one of the Ih that contain of of the j+1
members of J passes IT t times by the union bound:

t

 ln  j1 ln  4 


2
j
+
1
1<
j
+
1
e
<
j
+
1
e
= 1/4
    
 
 2
t

The probability of the size test to succeed is <
¼ +
¾¼
J does not
spread between
j+1 I’s
<½
J does spreads between j+1
I’s and IT succeeds
contradiction to the
assumption that the
test succeeds w.p >½
Where are we?
We concluded that if the JT succeeds
w.p > ½ then |J|<j
 Now what?
We will show that almost all the weight of
f is concentrated on J.
 How ?

(1) Show that the total weight on the high
frequencies is small.
(2) Show that the total weight of the low
frequencies on the characters that are not
contained in J is small.
(1)High Frequencies Contribute
Little
Prop: k >> r log r implies
f
k 2
2

2

f
S




S k
4
Proof: by the Coupon Collector Problem, a
character S of size larger than k spreads
w.h.p. (>¾) over all the Ih (namely, intersects
every Ih), hence contributes to the influence
of all parts.
2

h,VariationIh  f    f  S  
For this event:
4
S k
In every Ih  member of S
(S s.t. |S|>k)
High frequencies cont.
Use union bound to bound the probability
that one of I1 … Ij+1 to pass IT t times
test.
This probability is <
2
t


 j  1  1     j  1 e
 8
j

8
  j  1 e
8j2/  <t
 j2
1

4
J2>ln(j+1)+ln4
 w.p. at least
¾ ¾ = 9/16 JT fails.
Prob. for spreading
over all Ih
Prob. That the first
j+1 groups fail the
size test
contradiction
(2)Almost all Weight is on J
Lemma: Variationk f  
J
4
Proof: assume by way of contradiction otherwise
k
k
since
 
 Variation  f  Variation  f
i
iJ
J
for a random partition w.h.p. (>¾) ( by a Chernoff like
bound – (i influencei <)
for every h
Variationk f  

iIh
i
 
however, since for any I
100r
k
k
Variation
f

k

Variation

i  
I  f
iI

And also  VariationI  f  
100rk
iI


Similar to the last claim, the probability
to fail the test in such an event is at
least ¾.
 the test fails w.p > ½
contradiction

Note: for this union bound
t=200rk/[ln(j+1)+ln4]
Find the Close Junta
Now, since
VariationJ  f   Variation
k
J
consider the (non Boolean)
 f 
2

2
g : P J  
g
which, if rounded outside J
f
k 2
 f S
S J
S
f' x   sign AJ f x  J    rounding of g




Then f  g 2  VariationJ (f) 
2

2

f  g 2 
2
The distance of f’ from g --the closest
Boolean function to g-- is no more than
f’s
2
By the triangle inequality f  f 2  
2
Juntas

A function is a J-junta if its value
depends on only J variables.
-1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1

1 -1 1
A Dictatorship is 1-junta
-1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1
1 -1 1
-1
 - Noise sensitivity

The noise sensitivity of a function f is the probability
that f changes its value when changing a subset of its
variables according to the p distribution.
-1
1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1 1 -1 1
1 1 -1 -1 -1
-11
NS  f 
,p
x
Pr
n ,I n ,z
p

f  x   f   x \ I   z  
I
p
Noise sensitivity and juntas
Junta
-1
1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1 1 -1 1
1 1 -1 -1 -1
-11
Juntas are noise insensitive (stable)
Thm [Bourgain; Kindler & S]:
Noise insensitive (stable) Boolean functions are Juntas

Noise-Sensitivity – Cont.


Advantage: very efficiently testable (using
only two queries) by a perturbation-test.
Def (perturbation-test): choose x~p, and
y~,p,x, check whether f(x)=f(y)
The success is proportional to the noisesensitivity of f.

Prop: the -noise-sensitivity is given by
2
2  ns f =1   1    f S 
S
S
Relation between Parameters
Prop: small ns small high-freq weight
S 2
Proof: 2  ns f =1   1    f S 
S
therefore:
S 2
if ns is small, then  1    f S  ~ 1
S
Hence the high frequencies must have
2
small weights (as  f S   1 ).
S
Prop: small as small high-freq weight
2
Proof: as  f    f (S) S
S
High vs. Low Frequencies
Def: The section of a function f above k is
f
k
 f S
S k
S
and the low-frequency portion is
f
k
 f S
S k
S
Low-degree B.f are Juntas [KS]
Theorem:
 constant >0 s.t. any Boolean function
k 2
f:P([n]){-1,1} satisfying f 2  O  k2
is an [,j]-junta for j=O(-2k32k)
 
Corollary:
fix a p-biased distribution p over P([n])
Let >0 be any parameter.
Set k=log1-(½)
Then  constant >0 s.t. any Boolean function
2
f:P([n]){-1,1} satisfying ns  f   O 
k
is an [,j]-junta for j=O(-2k32k)
 
Freidgut Theorem
Thm: any Boolean f is an [, j]-junta for
O as f /  
j =2
Proof:
1.
2.
Specify the junta J
Show the complement of J has little influence
Codes and Boolean Functions
Def: an m-bit code is a subset of the set of all
the m-binary string
C{-1,1}m
The distance of a code C is the minimum, over
all pairs of legal-words (in C), of the
Hamming distance between the two words
Note: A Boolean function over n binary
variables is a 2n-bit string
Hence, a set of Boolean functions can be
considered as a 2n-bits code
Long-Code  Monotone-Dictatorship

In the long-code, the legal code-words
are all monotone dictatorships
C={{i} | i [n]}
namely, all the singleton characters
Open Questions


Mechanism Design: show a non truth-revealing
protocol in which the pay is smaller (Nash
equilibrium when all agents tell the truth?)
Hardness of Approximation:





MAX-CUT
Coloring a 3-colorable graph with fewest colors
Graph Properties: find sharp-thresholds for
properties
Analysis: show weakest condition for a
function to be a Junta
Apply Concentration of Measure techniques to
other problems in Complexity Theory
Specify the Junta
Set k=(as(f)/), and =2-(k)
Let
J  i| influencei  f    
We’ll prove:
and let
2
AJ f  1  
2
2
f'(x)  sign AJ f  x  J  
hence, J is a [,j]-junta, and |J|=2O(k)
Hadamard Code
In the Hadamard code the
set of legal-words consists of
all multiplicative (linear if over
{0,1}) functions
C={S | S  [n]}
namely all characters
Hadamard Test – Soundness
Prop(soundness):
1+
Pr[f(x)  f(y)  f(xy)]>
 S  [n], f S   
2
Proof:
 <Ex,y [f(x)  f(y)  f(xy)]=
=
 f S  f S  f S  E
[S1 (x)  S2 (y)  S3 (xy)]=
 f S  f S  f S  E
[S1 (x)  S2 (y)  S3 (x)  S3 (y)]=
1
S1 ,S2 ,S3
=
1
S1 ,S2 ,S3
=
2
2
3
3
x,y
x,y
 f S  f S  f S  E [
1
S1 ,S2 ,S3
2
3
x
S1
(x)  S3 (x)]  Ey [S2 (y)  S3 (y)]=
= f  S 
3
S
62
Testing Long-code
Def(a long-code list-test): given a code-word f,
probe it in a constant number of entries, and


accept almost always if f is a monotone
dictatorship
reject w.h.p if f does not have a sizeable fraction
of its Fourier weight concentrated on a small set of
variables, that is, if 
a semi-Junta J[n] s.t.
2
 f S  
S J
Note: a long-code list-test, distinguishes
between the case f is a dictatorship, to the
case f is far from a junta.
Motivation – Testing Long-code


The long-code list-test are essential tools in
proving hardness results.
Hence finding simple sufficient-conditions for
a function to be a junta is important.
High Frequencies Contribute Little
Prop: k >> r log r implies
f
k 2
2

2

f
S




S k
4
Proof: a character S of size larger than k
spreads w.h.p. over all parts Ih, hence
contributes to the influence of all parts.
If such characters were heavy (>/4), then
surely there would be more than j parts Ih
that fail the t independence-tests
Altogether
Lemma: influenceJ  f   
2
Proof:
influenceJ  f   f
k 2
2
+ influence
k
J

f

 
2
Altogether
influence
k
J
 f   influence  f
k
i
iJ
2


iJ iS, S k
f(S)  S
2
?
Beckner/Nelson/Bonami
Inequality
Def: let T be the following operator on any f,
E

T f  x 
Prop:
Proof:
T f 
T f  x  
z 1   / 2
f  x z 
  f S  
S
Sn 
 f S  
Sn 
S
S
 x E S z 
z
Beckner/Nelson/Bonami
Inequality
Def: let T be the following operator on any f,
T f  x 
E

z 1   / 2
f  x z 
Thm: for any p≥r and ≤((r-1)/(p-1))½
T f  f r
p
Beckner/Nelson/Bonami Corollary
Corollary 1: for any real f and 2≥r≥1
f
k
2
 r  1
k
2
fr
Corollary 2: for real f and r>2
f
k
k
r
 r  1
2
f2
Perturbation
Def: denote by  the
distribution over all subsets of
[n], which assigns probability to
a subset x as follows:
independently, for each i[n], let


ix with probability 1-
ix with probability 
Long-Code Test
Given a Boolean f, choose
random x and y, and choose
z; check that
f(x)f(y)=f(xyz)
Prop(completeness): a legal longcode word (a dictatorship)
passes this test w.p. 1-
Long-code Tests

Def (a long-code test): given a codeword w, probe it in a constant number of
entries, and


accept w.h.p if w is a monotone dictatorship
reject w.h.p if w is not close to any
monotone dictatorship
Efficient Long-code Tests
For some applications, it suffices if the test
may accept illegal code-words, nevertheless,
ones which have short list-decoding:
Def(a long-code list-test): given a code-word w,
probe it in 2/3 places, and


accept w.h.p if w is a monotone dictatorship,
reject w.h.p if w is not even approximately
determined by a short list of domain elements,
that is, if  a Junta J[n] s.t. f is close to f’ and
f’(x)=f’(xJ) for all x
Note: a long-code list-test, distinguishes
between the case w is a dictatorship, to the
case w is far from a junta.