49
Fooling Polytopes LiYang Tan (Stanford) Joint work with Ryan O’Donnell (CMU) and Rocco Servedio (Columbia)

Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Fooling  Polytopes  

Li-­‐Yang  Tan  (Stanford)    

Joint  work  with  Ryan  O’Donnell  (CMU)  and  Rocco  Servedio  (Columbia)  

Page 2: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Polytopes  over  {0,1}n  

=    IntersecPons  of  boolean  halfspaces  

§  Within  CS:  opPmizaPon  (            =  {0,1}-­‐integer  programs  Ax  ≤  b),  complexity  theory,  learning  theory,  …    

§  Beyond  CS:  Large  body  of  work  in  combinatorics,  high-­‐dimensional  geometry,  …          

F (x) = h1(x) ^ · · · ^ hm(x)

sign(w · x� ✓)Halfspace:    

x 2 {0, 1}n

Page 3: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Main  complexity  measure  for  this  talk:  #  of  facets  

 m  =  number  of  facets  of  polytope              =  number  of  halfspaces  

F (x) = h1(x) ^ · · · ^ hm(x)

This  talk:  can  think  of  m  =  poly(n),  say  n10  

x 2 {0, 1}n

1  ≤  m  ≤  2n  

Page 4: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

...  then  F  accepts  (Δ  +  0.01)  fracPon  of  points  

This  talk:  Discrepancy  Sets  for  Polytopes  

For  all  m-­‐facet  polytopes  F,    if  F  accepts  Δ  fracPon  of  inputs  in  {0,1}n  …  

{0,1}n  

Want  small  set  of  points            in  {0,1}n  such  that:  

Random  set  of  points  works  great.    Want  explicit  set.  

–  

Page 5: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Pseudorandom  Generators    for  Polytopes  

Truly  random  input:  

Pseudorandom  output:  

PRG  

r  bits  

n  bits  

Page 6: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Pseudorandom  Generators  

DefiniPon:  An  ε-­‐PRG  for  a  class  C  is  an  explicit  funcPon  G  :  {0,1}r            {0,1}n  such  that:  for  every  funcPon  F  in  C,    

!

Goal:  minimize  seed  length  r(n,m,ε)  

���� Ex⇠{0,1}n

[F (x)]� Es⇠{0,1}r

[F (G(s))]

���� "<latexit sha1_base64="k8Cel2XFg//cJCjmrSPBk0A27q0=">AAACk3ichVHbahsxENVu0yR1msRpoS95ETUBGxqzW5ob9MHNtS+FBOomYG2MVh7bIlppkbShRt0v6t/0rX8TreNAXFIyIOZwzsxoLmkuuLFR9DcIXyy8XFxaflVbeb26tl7fePPDqEIz6DIllL5KqQHBJXQttwKucg00SwVcpjdHlX55C9pwJb/bSQ5JRkeSDzmj1lP9+m+S8tHoFyYZtWOVu6lPU3dSln1HUiUGZpJ5536WxPCMuOhDTMprWfZOm/NyK8Hbz5cxc2V0VeasOR/QaiUPTQnA5JZqyA0XVbeNqB1NDT8CO1F8sBvjeMY00MzO+/U/ZKBYkYG0TFBjenGU28RRbTkTUNZIYSCn7IaOoOehpBmYxE2XWuItzwzwUGn/pMVT9nGGo5mpevaR1bDmX60in9J6hR3uJ47LvLAg2f1Hw0Jgq3B1ITzgGpgVEw8o09z3itmYasqsv2PNL+FhUvx/0P3YPmhHF58ancPZNpbRJnqPmihGe6iDvqJz1EUs2Aj2gk7wJXwXfg4Pw+P70DCY5bxFcxZ+uwPnlMzU</latexit><latexit sha1_base64="k8Cel2XFg//cJCjmrSPBk0A27q0=">AAACk3ichVHbahsxENVu0yR1msRpoS95ETUBGxqzW5ob9MHNtS+FBOomYG2MVh7bIlppkbShRt0v6t/0rX8TreNAXFIyIOZwzsxoLmkuuLFR9DcIXyy8XFxaflVbeb26tl7fePPDqEIz6DIllL5KqQHBJXQttwKucg00SwVcpjdHlX55C9pwJb/bSQ5JRkeSDzmj1lP9+m+S8tHoFyYZtWOVu6lPU3dSln1HUiUGZpJ5536WxPCMuOhDTMprWfZOm/NyK8Hbz5cxc2V0VeasOR/QaiUPTQnA5JZqyA0XVbeNqB1NDT8CO1F8sBvjeMY00MzO+/U/ZKBYkYG0TFBjenGU28RRbTkTUNZIYSCn7IaOoOehpBmYxE2XWuItzwzwUGn/pMVT9nGGo5mpevaR1bDmX60in9J6hR3uJ47LvLAg2f1Hw0Jgq3B1ITzgGpgVEw8o09z3itmYasqsv2PNL+FhUvx/0P3YPmhHF58ancPZNpbRJnqPmihGe6iDvqJz1EUs2Aj2gk7wJXwXfg4Pw+P70DCY5bxFcxZ+uwPnlMzU</latexit><latexit sha1_base64="k8Cel2XFg//cJCjmrSPBk0A27q0=">AAACk3ichVHbahsxENVu0yR1msRpoS95ETUBGxqzW5ob9MHNtS+FBOomYG2MVh7bIlppkbShRt0v6t/0rX8TreNAXFIyIOZwzsxoLmkuuLFR9DcIXyy8XFxaflVbeb26tl7fePPDqEIz6DIllL5KqQHBJXQttwKucg00SwVcpjdHlX55C9pwJb/bSQ5JRkeSDzmj1lP9+m+S8tHoFyYZtWOVu6lPU3dSln1HUiUGZpJ5536WxPCMuOhDTMprWfZOm/NyK8Hbz5cxc2V0VeasOR/QaiUPTQnA5JZqyA0XVbeNqB1NDT8CO1F8sBvjeMY00MzO+/U/ZKBYkYG0TFBjenGU28RRbTkTUNZIYSCn7IaOoOehpBmYxE2XWuItzwzwUGn/pMVT9nGGo5mpevaR1bDmX60in9J6hR3uJ47LvLAg2f1Hw0Jgq3B1ITzgGpgVEw8o09z3itmYasqsv2PNL+FhUvx/0P3YPmhHF58ancPZNpbRJnqPmihGe6iDvqJz1EUs2Aj2gk7wJXwXfg4Pw+P70DCY5bxFcxZ+uwPnlMzU</latexit>

G  

r  bits  

n  bits  

C  =  {  m-­‐facet  polytopes            }    This  work:  

Page 7: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Consider  {  G(s)  :  s        {0,1}r  }    

Let  G  :  {0,1}r            {0,1}n  be  an  ε-­‐PRG  for  the  class  m-­‐facet  polytopes      

Image  of  PRG  =  Discrepancy  Set    

!

2 A  set  of  2r  points            in  {0,1}n  

G  

r  bits  

n  bits  

{0,1}n  

Discrepancy  set  for  the  class  of  m-­‐facet  polytopes  

Page 8: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Our  main  result:  PRG  for  polytopes  

§  Previous  best  seed  length  had  linear  dependence  on  m  

An  ε-­‐PRG  for  m-­‐facet  polytopes  over  {0,1}n  with  seed  length:  

poly(log  m,  1/ε)      log  n      

Discrepancy  set  of  size  n                                polylog(m)  

{0,1}n  

Equivalently:    

.  

Page 9: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Analogous  results  for  other  domains  

{0,1}n  

§  Solid  cube  [0,1]n  

§  Hypergrid  {0,1,...,k}n  

§  Gaussian  space  (Rn  under  N(0,1)n)      [HKM10]  

§  ...    

Standard  reducPons  

Page 10: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

One  algorithmic  applicaPon:    CounPng  #  of  soluPons  of  {0,1}-­‐integer  programs  

Ax b

x 2 {0, 1}nsubject  to  

c

Txmaximize  

and  

Given  as  input  a  {0,1}-­‐IP  with  m  constraints,  there  is  a  determinisPc  algorithm  that  runs  in  Pme      

n  poly(log  m,  1/ε)    

and  outputs  an  esPmate  of  the  fracBon  of  feasible  soluBons,  accurate  to  +  ε.  −  

PRG  =  input-­‐oblivious  algorithm    

Average  w.r.t.  fixed  discrepancy  set  works  for  all  possible  inputs                                    (all  possible  {0,1}-­‐IPs)      

Page 11: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

IntersecPons  of  m  general  halfspaces    (This  work)  

poly(log  m,  1/ε)      log  n      

Class  of  funcBons:   Seed  length:  

Any  funcBon  of  m  general  halfspaces    [Gopalan,  O’Donnell,  Wu,  Zuckerman  10]    

Õ(m  log(1/ε))      log  n      

Comparison  with  prior  results  

.  

.  

IntersecPons  of  m  “regular”  halfspaces  [Harsha,  Klivans,  Meka  10]    

 

poly(log  m,  1/ε)      log  n  

IntersecPons  of  m  low-­‐weight  halfspaces  [Servedio,  T.  17]    

 

poly(log  m,  1/ε)      polylog  n  

.  

.  

Page 12: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

PRGs  for  halfspaces  and  their  generalizaPons  

Halfspaces  

Polynomial  threshold  funcPons   IntersecBons  of  halfspaces  

§  Diakonikolas,  Gopalan,  Jaiswal,  Servedio,  Viola  2009  §  Meka,  Zuckerman  2009  §  Karnin,  Rabani,  Shpilka  2011  §  Kothari,  Meka  2015  §  Gopalan,  Kane,  Meka  2015  

§  Meka,  Zuckerman  2009  §  Diakonikolas,  Kane,  Nelson  2009  §  Kane  2011  §  Kane  2011  §  Kane,  Meka  2013  §  Kane  2014  

§  Harsha,  Klivans,  Meka  2010    §  Gopalan,  O’Donnell,  Wu,  Zuckerman  2010  §  Servedio,  T.  2017  §  This  work    

Page 13: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Structure  of  this  talk  

§  Part  I:  The  connecPon  to  Central  Limit  Theorems    

§  VersaPle  and  powerful  framework  for  designing  PRGs  

             [Meka,  Zuckerman  09]  [Harsha,  Klivans,  Meka  10]  

§  Especially  effecPve  for  analyzing  “regular”  halfspaces  

§  Part  II:  Our  work  

§  Challenges  in  dealing  with  general  halfspaces  §  New  ideas  and  ingredients  in  our  work    

§  New  Litlewood–Offord  theorem  for  polytopes  

Page 14: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Part  I:  Background  and  Context  PRGs  via  Central  Limit  Theorems      

IllustraPve  example:  Fooling  a  single  “regular”  halfspace  [MZ10]  

Page 15: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Central  Limit  Theorems  

The  sum  of  many  independent  random  variables    converges  to  Gaussian  (of  same  mean  and  variance).  

CDF  distance  (=  Kolmogorov  distance):        For  all  θ  in  R,  

CDFs  of  S  vs.  Gaussian  

S = X1 + · · ·+Xn ⇡ N (µ,�2)

Pr⇥S ✓

⇤⇡ Pr

⇥N ✓

⇤<latexit sha1_base64="ly0+zZH1upYYaSthDZ0Ut9N2NWI=">AAACTnicdVFNb9NAEF2nFEKgNMCRy4oIiVNkV/0gtwgunFAQhESKrWi8GSerrL3W7rhqZOUf9tLe+BtcOLQI1kmQAmlHWu3Te/O0M2/jXElLvv/dq+092H/4qP648eTpwbPD5vMX36wujMC+0EqbYQwWlcywT5IUDnODkMYKB/H8Q6UPztFYqbOvtMgxSmGayUQKIEeNm0mYAs1MWvbMMozldMTDWKuJXaTuKr8seaiQhzRDgkqOeAh5bvQFb+waK0KAKj/tusbNlt/2V8W3wIkfdE4DHmyYFttUb9y8DidaFClmJBRYOwr8nKISDEmhcNkIC4s5iDlMceRgBinaqFzlseRvHDPhiTbuZMRX7LajhNRWG7rOamb7v1aRd2mjgpJ3USmzvCDMxPqhpFCcNK/C5RNpUJBaOADCSDcrFzMwIMh9QcOF8HdTfj/oH7U77eDzcav7fpNGnb1ir9lbFrAz1mUfWY/1mWCX7Ae7YbfelffT++X9XrfWvI3nJfunavU/GYW2MA==</latexit><latexit sha1_base64="ly0+zZH1upYYaSthDZ0Ut9N2NWI=">AAACTnicdVFNb9NAEF2nFEKgNMCRy4oIiVNkV/0gtwgunFAQhESKrWi8GSerrL3W7rhqZOUf9tLe+BtcOLQI1kmQAmlHWu3Te/O0M2/jXElLvv/dq+092H/4qP648eTpwbPD5vMX36wujMC+0EqbYQwWlcywT5IUDnODkMYKB/H8Q6UPztFYqbOvtMgxSmGayUQKIEeNm0mYAs1MWvbMMozldMTDWKuJXaTuKr8seaiQhzRDgkqOeAh5bvQFb+waK0KAKj/tusbNlt/2V8W3wIkfdE4DHmyYFttUb9y8DidaFClmJBRYOwr8nKISDEmhcNkIC4s5iDlMceRgBinaqFzlseRvHDPhiTbuZMRX7LajhNRWG7rOamb7v1aRd2mjgpJ3USmzvCDMxPqhpFCcNK/C5RNpUJBaOADCSDcrFzMwIMh9QcOF8HdTfj/oH7U77eDzcav7fpNGnb1ir9lbFrAz1mUfWY/1mWCX7Ae7YbfelffT++X9XrfWvI3nJfunavU/GYW2MA==</latexit><latexit sha1_base64="ly0+zZH1upYYaSthDZ0Ut9N2NWI=">AAACTnicdVFNb9NAEF2nFEKgNMCRy4oIiVNkV/0gtwgunFAQhESKrWi8GSerrL3W7rhqZOUf9tLe+BtcOLQI1kmQAmlHWu3Te/O0M2/jXElLvv/dq+092H/4qP648eTpwbPD5vMX36wujMC+0EqbYQwWlcywT5IUDnODkMYKB/H8Q6UPztFYqbOvtMgxSmGayUQKIEeNm0mYAs1MWvbMMozldMTDWKuJXaTuKr8seaiQhzRDgkqOeAh5bvQFb+waK0KAKj/tusbNlt/2V8W3wIkfdE4DHmyYFttUb9y8DidaFClmJBRYOwr8nKISDEmhcNkIC4s5iDlMceRgBinaqFzlseRvHDPhiTbuZMRX7LajhNRWG7rOamb7v1aRd2mjgpJ3USmzvCDMxPqhpFCcNK/C5RNpUJBaOADCSDcrFzMwIMh9QcOF8HdTfj/oH7U77eDzcav7fpNGnb1ir9lbFrAz1mUfWY/1mWCX7Ae7YbfelffT++X9XrfWvI3nJfunavU/GYW2MA==</latexit><latexit sha1_base64="ly0+zZH1upYYaSthDZ0Ut9N2NWI=">AAACTnicdVFNb9NAEF2nFEKgNMCRy4oIiVNkV/0gtwgunFAQhESKrWi8GSerrL3W7rhqZOUf9tLe+BtcOLQI1kmQAmlHWu3Te/O0M2/jXElLvv/dq+092H/4qP648eTpwbPD5vMX36wujMC+0EqbYQwWlcywT5IUDnODkMYKB/H8Q6UPztFYqbOvtMgxSmGayUQKIEeNm0mYAs1MWvbMMozldMTDWKuJXaTuKr8seaiQhzRDgkqOeAh5bvQFb+waK0KAKj/tusbNlt/2V8W3wIkfdE4DHmyYFttUb9y8DidaFClmJBRYOwr8nKISDEmhcNkIC4s5iDlMceRgBinaqFzlseRvHDPhiTbuZMRX7LajhNRWG7rOamb7v1aRd2mjgpJ3USmzvCDMxPqhpFCcNK/C5RNpUJBaOADCSDcrFzMwIMh9QcOF8HdTfj/oH7U77eDzcav7fpNGnb1ir9lbFrAz1mUfWY/1mWCX7Ae7YbfelffT++X9XrfWvI3nJfunavU/GYW2MA==</latexit>

Page 16: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

DefiniPon:    An  “ε-­‐regular”  linear  form  S  :  Rn                R    

Regularity  and  the  Berry–Esséen  CLT  

is  one  in  which  no  weight  is  too  dominant:    

S(x) = w1x1 + · · ·+ wnxn

Berry–Esséen  CLT:    For  x  uniform  from  {−1,1}n,  

ObservaPon:    Regularity  crucial;  consider  S(x)  =  x1  

   

!

CDF  of  x1  ≈  Gaussian    

|wi| " · kwk2

S(x) ⇡"

N (µ,�2)

Page 17: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

The  connecPon  between  CLTs  and  pseudorandomness  

CLT:  S(x)  converges  to  Gaussian  in  CDF  distance  

Pseudorandomness:  Fool  the  regular  halfspace  sign(S(x)−θ)  

versus  

(for  all  θ)  

Pseudorandom  version  of  Berry–Esséen  CLT?      

S(x) = w1x1 + · · ·+ wnxnRegular  linear  form:   (x  uniform  {−1,1}n)  

   

Pruniform x ⇠ {±1}n

⇥S(x) ✓

⇤⇡ Pr

⇥N ✓

⇤<latexit sha1_base64="Ac1l5Pfcv4tfIglYJmgzAZgpD5o=">AAACjXicdVFbixMxFM6Mt7XrpeqjLwe7wvpSZkRXV0UWfdAnqWjdhWYsmTRtwyaTkJyRljA/xz/km//GzLRC18uBkI/vfB/nVlolPWbZzyS9dPnK1Wt713v7N27eut2/c/eLN7XjYsyNMu6sZF4oWYkxSlTizDrBdKnEaXn+ts2ffhPOS1N9xrUVhWaLSs4lZxipaf871QyXxobudzqMXNNMA0WxwlBHpXEaDmhp1MyvdfzCqgHqpQYaqNWQ0+ZrddA0tJSLCXw6vKh8BFQJoLgUyFpFAZRZ68wKejv1Nt6O4EyFD81frml/kA2zLmAHPM3y46Mc8i0zINsYTfs/6MzwWosKuWLeT/LMYhGYQ8mVaHq09sIyfs4WYhJhxbTwRejW2cDDyMwgTh5fhdCxu47AtG9HjMq2Z/9nriX/lZvUOH9eBFnZGkXFN4XmtQI00N4GZtIJjmodAeNOxl6BL5ljHOMFe3EJvyeF/4Px4+HxMP/4ZHDyZruNPXKfPCCHJCfPyAl5T0ZkTHiyn+TJi+Rl2k+P0lfp6400Tbaee+RCpO9+ARMIyRo=</latexit><latexit sha1_base64="Ac1l5Pfcv4tfIglYJmgzAZgpD5o=">AAACjXicdVFbixMxFM6Mt7XrpeqjLwe7wvpSZkRXV0UWfdAnqWjdhWYsmTRtwyaTkJyRljA/xz/km//GzLRC18uBkI/vfB/nVlolPWbZzyS9dPnK1Wt713v7N27eut2/c/eLN7XjYsyNMu6sZF4oWYkxSlTizDrBdKnEaXn+ts2ffhPOS1N9xrUVhWaLSs4lZxipaf871QyXxobudzqMXNNMA0WxwlBHpXEaDmhp1MyvdfzCqgHqpQYaqNWQ0+ZrddA0tJSLCXw6vKh8BFQJoLgUyFpFAZRZ68wKejv1Nt6O4EyFD81frml/kA2zLmAHPM3y46Mc8i0zINsYTfs/6MzwWosKuWLeT/LMYhGYQ8mVaHq09sIyfs4WYhJhxbTwRejW2cDDyMwgTh5fhdCxu47AtG9HjMq2Z/9nriX/lZvUOH9eBFnZGkXFN4XmtQI00N4GZtIJjmodAeNOxl6BL5ljHOMFe3EJvyeF/4Px4+HxMP/4ZHDyZruNPXKfPCCHJCfPyAl5T0ZkTHiyn+TJi+Rl2k+P0lfp6400Tbaee+RCpO9+ARMIyRo=</latexit><latexit sha1_base64="Ac1l5Pfcv4tfIglYJmgzAZgpD5o=">AAACjXicdVFbixMxFM6Mt7XrpeqjLwe7wvpSZkRXV0UWfdAnqWjdhWYsmTRtwyaTkJyRljA/xz/km//GzLRC18uBkI/vfB/nVlolPWbZzyS9dPnK1Wt713v7N27eut2/c/eLN7XjYsyNMu6sZF4oWYkxSlTizDrBdKnEaXn+ts2ffhPOS1N9xrUVhWaLSs4lZxipaf871QyXxobudzqMXNNMA0WxwlBHpXEaDmhp1MyvdfzCqgHqpQYaqNWQ0+ZrddA0tJSLCXw6vKh8BFQJoLgUyFpFAZRZ68wKejv1Nt6O4EyFD81frml/kA2zLmAHPM3y46Mc8i0zINsYTfs/6MzwWosKuWLeT/LMYhGYQ8mVaHq09sIyfs4WYhJhxbTwRejW2cDDyMwgTh5fhdCxu47AtG9HjMq2Z/9nriX/lZvUOH9eBFnZGkXFN4XmtQI00N4GZtIJjmodAeNOxl6BL5ljHOMFe3EJvyeF/4Px4+HxMP/4ZHDyZruNPXKfPCCHJCfPyAl5T0ZkTHiyn+TJi+Rl2k+P0lfp6400Tbaee+RCpO9+ARMIyRo=</latexit><latexit sha1_base64="Ac1l5Pfcv4tfIglYJmgzAZgpD5o=">AAACjXicdVFbixMxFM6Mt7XrpeqjLwe7wvpSZkRXV0UWfdAnqWjdhWYsmTRtwyaTkJyRljA/xz/km//GzLRC18uBkI/vfB/nVlolPWbZzyS9dPnK1Wt713v7N27eut2/c/eLN7XjYsyNMu6sZF4oWYkxSlTizDrBdKnEaXn+ts2ffhPOS1N9xrUVhWaLSs4lZxipaf871QyXxobudzqMXNNMA0WxwlBHpXEaDmhp1MyvdfzCqgHqpQYaqNWQ0+ZrddA0tJSLCXw6vKh8BFQJoLgUyFpFAZRZ68wKejv1Nt6O4EyFD81frml/kA2zLmAHPM3y46Mc8i0zINsYTfs/6MzwWosKuWLeT/LMYhGYQ8mVaHq09sIyfs4WYhJhxbTwRejW2cDDyMwgTh5fhdCxu47AtG9HjMq2Z/9nriX/lZvUOH9eBFnZGkXFN4XmtQI00N4GZtIJjmodAeNOxl6BL5ljHOMFe3EJvyeF/4Px4+HxMP/4ZHDyZruNPXKfPCCHJCfPyAl5T0ZkTHiyn+TJi+Rl2k+P0lfp6400Tbaee+RCpO9+ARMIyRo=</latexit>

Pruniform x ⇠ {±1}n

⇥S(x) ✓

⇤⇡ Pr

pseudo y ⇠ {±1}n

⇥S(y) ✓

⇤<latexit sha1_base64="h3sVoNExaRBazf9PCVFQ+ziYycI=">AAACzXicjVJLbxMxEPYurxJeAY5cRqRI5RLtVrx6q+CCxCUIQivFS+R1JolVe21sb5XFLFf+Hzd+AP8DbxqkhpcYyZrRN9/om4dLI4XzWfYtSS9cvHT5ys7V3rXrN27e6t++887p2nIccy21PS6ZQykqHHvhJR4bi0yVEo/Kkxdd/ugUrRO6eusbg4Vii0rMBWc+QtP+d6qYX2oT1t6qMLJtOw3U48qHOjK1VbBLSy1nrlHRhVUL1AkFNFCjIKft+2q3bWkpFhN4s7fNfAhUIlC/RM86RgGUGWP1Cnr/0jUO65nelm3+W7b5XXbaH2TDbG1wLnic5QdPcsg3yIBsbDTtf6UzzWuFleeSOTfJM+OLwKwXXGLbo7VDw/gJW+AkhhVT6IqwPkcLDyIyg7i5+CoPa/R8RWDKdb1GZje8+zXXgX/KTWo/f1YEUZnaY8XPhOa1BK+huy3MhEXuZRMDxq2IvQJfMsu4jz+gF5fwc1L4ezDeHx4M89ePBofPN9vYIffIfbJHcvKUHJKXZETGhCevkg/JxySko/Q0/ZR+PqOmyabmLtmy9MsPC2Lk2g==</latexit><latexit sha1_base64="h3sVoNExaRBazf9PCVFQ+ziYycI=">AAACzXicjVJLbxMxEPYurxJeAY5cRqRI5RLtVrx6q+CCxCUIQivFS+R1JolVe21sb5XFLFf+Hzd+AP8DbxqkhpcYyZrRN9/om4dLI4XzWfYtSS9cvHT5ys7V3rXrN27e6t++887p2nIccy21PS6ZQykqHHvhJR4bi0yVEo/Kkxdd/ugUrRO6eusbg4Vii0rMBWc+QtP+d6qYX2oT1t6qMLJtOw3U48qHOjK1VbBLSy1nrlHRhVUL1AkFNFCjIKft+2q3bWkpFhN4s7fNfAhUIlC/RM86RgGUGWP1Cnr/0jUO65nelm3+W7b5XXbaH2TDbG1wLnic5QdPcsg3yIBsbDTtf6UzzWuFleeSOTfJM+OLwKwXXGLbo7VDw/gJW+AkhhVT6IqwPkcLDyIyg7i5+CoPa/R8RWDKdb1GZje8+zXXgX/KTWo/f1YEUZnaY8XPhOa1BK+huy3MhEXuZRMDxq2IvQJfMsu4jz+gF5fwc1L4ezDeHx4M89ePBofPN9vYIffIfbJHcvKUHJKXZETGhCevkg/JxySko/Q0/ZR+PqOmyabmLtmy9MsPC2Lk2g==</latexit><latexit sha1_base64="h3sVoNExaRBazf9PCVFQ+ziYycI=">AAACzXicjVJLbxMxEPYurxJeAY5cRqRI5RLtVrx6q+CCxCUIQivFS+R1JolVe21sb5XFLFf+Hzd+AP8DbxqkhpcYyZrRN9/om4dLI4XzWfYtSS9cvHT5ys7V3rXrN27e6t++887p2nIccy21PS6ZQykqHHvhJR4bi0yVEo/Kkxdd/ugUrRO6eusbg4Vii0rMBWc+QtP+d6qYX2oT1t6qMLJtOw3U48qHOjK1VbBLSy1nrlHRhVUL1AkFNFCjIKft+2q3bWkpFhN4s7fNfAhUIlC/RM86RgGUGWP1Cnr/0jUO65nelm3+W7b5XXbaH2TDbG1wLnic5QdPcsg3yIBsbDTtf6UzzWuFleeSOTfJM+OLwKwXXGLbo7VDw/gJW+AkhhVT6IqwPkcLDyIyg7i5+CoPa/R8RWDKdb1GZje8+zXXgX/KTWo/f1YEUZnaY8XPhOa1BK+huy3MhEXuZRMDxq2IvQJfMsu4jz+gF5fwc1L4ezDeHx4M89ePBofPN9vYIffIfbJHcvKUHJKXZETGhCevkg/JxySko/Q0/ZR+PqOmyabmLtmy9MsPC2Lk2g==</latexit><latexit sha1_base64="h3sVoNExaRBazf9PCVFQ+ziYycI=">AAACzXicjVJLbxMxEPYurxJeAY5cRqRI5RLtVrx6q+CCxCUIQivFS+R1JolVe21sb5XFLFf+Hzd+AP8DbxqkhpcYyZrRN9/om4dLI4XzWfYtSS9cvHT5ys7V3rXrN27e6t++887p2nIccy21PS6ZQykqHHvhJR4bi0yVEo/Kkxdd/ugUrRO6eusbg4Vii0rMBWc+QtP+d6qYX2oT1t6qMLJtOw3U48qHOjK1VbBLSy1nrlHRhVUL1AkFNFCjIKft+2q3bWkpFhN4s7fNfAhUIlC/RM86RgGUGWP1Cnr/0jUO65nelm3+W7b5XXbaH2TDbG1wLnic5QdPcsg3yIBsbDTtf6UzzWuFleeSOTfJM+OLwKwXXGLbo7VDw/gJW+AkhhVT6IqwPkcLDyIyg7i5+CoPa/R8RWDKdb1GZje8+zXXgX/KTWo/f1YEUZnaY8XPhOa1BK+huy3MhEXuZRMDxq2IvQJfMsu4jz+gF5fwc1L4ezDeHx4M89ePBofPN9vYIffIfbJHcvKUHJKXZETGhCevkg/JxySko/Q0/ZR+PqOmyabmLtmy9MsPC2Lk2g==</latexit>

Page 18: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Meka–Zuckerman:  PRGs  for  regular  halfspaces  via  CLTs  

Berry–Esséen  CLT  

 

Gaussian  

[MZ]’s  derandomizaBon  of  BE  

S(x) S(y)

Uniform  

 

Pseudorandom  

 

CDF-­‐close  

 

CDF-­‐close  by  Δ-­‐inequality    

 

x ⇠ {�1, 1}n y ⇠ {�1, 1}n

CDF-­‐close  

 

 

N (µ,�2)<latexit sha1_base64="7Kp9U4wcDqRJrTLBAN5TCDzZUFU=">AAACAXicdVDLSsNAFJ3UV62vqCtxM1iEClKS4qu7ohtXUsFooYllMp20Q2eSMDMRSihu/BU3LlTc+hfu/BsnbYQqeuDC4Zx7ufceP2ZUKsv6NAozs3PzC8XF0tLyyuqaub5xLaNEYOLgiEWi5SNJGA2Jo6hipBULgrjPyI0/OMv8mzsiJI3CKzWMicdRL6QBxUhpqWNuuRypPkYsvRhVXJ7su5L2OLqt7XXMslW1xoBT5NCy60c2tHOlDHI0O+aH241wwkmoMENStm0rVl6KhKKYkVHJTSSJER6gHmlrGiJOpJeOXxjBXa10YRAJXaGCY3V6IkVcyiH3dWd2sPztZeJfXjtRwYmX0jBOFAnxZFGQMKgimOUBu1QQrNhQE4QF1bdC3EcCYaVTK+kQvj+F/xOnVq1XrcuDcuM0T6MItsEOqAAbHIMGOAdN4AAM7sEjeAYvxoPxZLwab5PWgpHPbIIfMN6/AAz/lsI=</latexit><latexit sha1_base64="7Kp9U4wcDqRJrTLBAN5TCDzZUFU=">AAACAXicdVDLSsNAFJ3UV62vqCtxM1iEClKS4qu7ohtXUsFooYllMp20Q2eSMDMRSihu/BU3LlTc+hfu/BsnbYQqeuDC4Zx7ufceP2ZUKsv6NAozs3PzC8XF0tLyyuqaub5xLaNEYOLgiEWi5SNJGA2Jo6hipBULgrjPyI0/OMv8mzsiJI3CKzWMicdRL6QBxUhpqWNuuRypPkYsvRhVXJ7su5L2OLqt7XXMslW1xoBT5NCy60c2tHOlDHI0O+aH241wwkmoMENStm0rVl6KhKKYkVHJTSSJER6gHmlrGiJOpJeOXxjBXa10YRAJXaGCY3V6IkVcyiH3dWd2sPztZeJfXjtRwYmX0jBOFAnxZFGQMKgimOUBu1QQrNhQE4QF1bdC3EcCYaVTK+kQvj+F/xOnVq1XrcuDcuM0T6MItsEOqAAbHIMGOAdN4AAM7sEjeAYvxoPxZLwab5PWgpHPbIIfMN6/AAz/lsI=</latexit><latexit sha1_base64="7Kp9U4wcDqRJrTLBAN5TCDzZUFU=">AAACAXicdVDLSsNAFJ3UV62vqCtxM1iEClKS4qu7ohtXUsFooYllMp20Q2eSMDMRSihu/BU3LlTc+hfu/BsnbYQqeuDC4Zx7ufceP2ZUKsv6NAozs3PzC8XF0tLyyuqaub5xLaNEYOLgiEWi5SNJGA2Jo6hipBULgrjPyI0/OMv8mzsiJI3CKzWMicdRL6QBxUhpqWNuuRypPkYsvRhVXJ7su5L2OLqt7XXMslW1xoBT5NCy60c2tHOlDHI0O+aH241wwkmoMENStm0rVl6KhKKYkVHJTSSJER6gHmlrGiJOpJeOXxjBXa10YRAJXaGCY3V6IkVcyiH3dWd2sPztZeJfXjtRwYmX0jBOFAnxZFGQMKgimOUBu1QQrNhQE4QF1bdC3EcCYaVTK+kQvj+F/xOnVq1XrcuDcuM0T6MItsEOqAAbHIMGOAdN4AAM7sEjeAYvxoPxZLwab5PWgpHPbIIfMN6/AAz/lsI=</latexit>

Page 19: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Meka–Zuckerman’s  PRG  for  regular  halfspaces  

1.  Pseudorandomly  hash  n  variables  into  1/ε2  buckets    2.  Assign  values  within  each  bucket  according  to  O(1)-­‐wise  independent  

distribuPon  (independently  across  buckets)  

[Meka–Zuckerman  10]  

§  Theorem:  Berry–Esséen  CLT  holds  for  this  distribuPon  §  Corollary:  This  is  an  ε-­‐PRG  for  ε-­‐regular  halfspaces  with  seed  length  

O((log  n)/ε2).      

.  .  .      y10  y2  y6   y3  

y12   y9  y11  y4  

y7  

This  talk:  All  PRGs  =  this  [MZ]  generator  (possibly  with  different  parameters)      

1/ε2  buckets    

Page 20: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Next:  Fooling  IntersecBons  of  regular  halfspaces  

Regular  halfspaces   IntersecBons  of  regular  halfspaces  

Same  overall  framework,  but  many  cool  new  ideas  and  ingredients...  

[Meka,  Zuckerman  09]   [Harsha,  Klivans,  Meka  10]  

   

Page 21: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

1  regular  halfspace  

IntersecPon  of  m  regular  halfspaces  

Sum  of  real-­‐valued  r.v.’s,  none  too  dominant    

Berry-­‐Esséen  CLT  

[HKM10]  mulBdimensional  CLT    nX

i=1

~Xi �! N (~µ,⌃)

Sum  of  Rm-­‐valued  r.v.’s,  none  too  dominant  

convergence  in  mulPdimensional  CDF  distance  

nX

i=1

Xi �! N (µ,�2)<latexit sha1_base64="/VLuZsnV5AmsxUnYUED4TjW5frk=">AAACMnicdVBdSxtBFJ2N36nVqI++DIaChRJ2xc8HQfRF+iAWmhrIJsvdyWQzOB/LzKwSlv1PvvhHfBDEB1v66o/obJJClPbAMIdz7uXee+KUM2N9/8mrzMzOzS8sLlU/LH9cWa2trf8wKtOENoniSrdiMJQzSZuWWU5bqaYgYk6v4uuz0r+6odowJb/bYUo7AhLJ+oyAdVJU+xqaTEQ5Ow6KrsRhrHjPDIX78lYRMRzikCuZaJYMLGitbp0gwA4I8Pyi2A5F9iU0LBHQ3fkc1ep+wx8BT5E9PzjaD3AwUepogsuo9hD2FMkElZZwMKYd+Knt5KAtI5wW1TAzNAVyDQltOypBUNPJRzcX+JNTerivtHvS4pE63ZGDMOUlrrJc2Lz3SvFfXjuz/cNOzmSaWSrJeFA/49gqXAaIe0xTYvnQESCauV0xGYAGYl3MVRfC30vx/0lzp3HU8L/t1k9OJ2ksok20hbZRgA7QCTpHl6iJCLpDj+gF/fTuvWfvl/d7XFrxJj0b6A281z9iWKuP</latexit><latexit sha1_base64="/VLuZsnV5AmsxUnYUED4TjW5frk=">AAACMnicdVBdSxtBFJ2N36nVqI++DIaChRJ2xc8HQfRF+iAWmhrIJsvdyWQzOB/LzKwSlv1PvvhHfBDEB1v66o/obJJClPbAMIdz7uXee+KUM2N9/8mrzMzOzS8sLlU/LH9cWa2trf8wKtOENoniSrdiMJQzSZuWWU5bqaYgYk6v4uuz0r+6odowJb/bYUo7AhLJ+oyAdVJU+xqaTEQ5Ow6KrsRhrHjPDIX78lYRMRzikCuZaJYMLGitbp0gwA4I8Pyi2A5F9iU0LBHQ3fkc1ep+wx8BT5E9PzjaD3AwUepogsuo9hD2FMkElZZwMKYd+Knt5KAtI5wW1TAzNAVyDQltOypBUNPJRzcX+JNTerivtHvS4pE63ZGDMOUlrrJc2Lz3SvFfXjuz/cNOzmSaWSrJeFA/49gqXAaIe0xTYvnQESCauV0xGYAGYl3MVRfC30vx/0lzp3HU8L/t1k9OJ2ksok20hbZRgA7QCTpHl6iJCLpDj+gF/fTuvWfvl/d7XFrxJj0b6A281z9iWKuP</latexit><latexit sha1_base64="/VLuZsnV5AmsxUnYUED4TjW5frk=">AAACMnicdVBdSxtBFJ2N36nVqI++DIaChRJ2xc8HQfRF+iAWmhrIJsvdyWQzOB/LzKwSlv1PvvhHfBDEB1v66o/obJJClPbAMIdz7uXee+KUM2N9/8mrzMzOzS8sLlU/LH9cWa2trf8wKtOENoniSrdiMJQzSZuWWU5bqaYgYk6v4uuz0r+6odowJb/bYUo7AhLJ+oyAdVJU+xqaTEQ5Ow6KrsRhrHjPDIX78lYRMRzikCuZaJYMLGitbp0gwA4I8Pyi2A5F9iU0LBHQ3fkc1ep+wx8BT5E9PzjaD3AwUepogsuo9hD2FMkElZZwMKYd+Knt5KAtI5wW1TAzNAVyDQltOypBUNPJRzcX+JNTerivtHvS4pE63ZGDMOUlrrJc2Lz3SvFfXjuz/cNOzmSaWSrJeFA/49gqXAaIe0xTYvnQESCauV0xGYAGYl3MVRfC30vx/0lzp3HU8L/t1k9OJ2ksok20hbZRgA7QCTpHl6iJCLpDj+gF/fTuvWfvl/d7XFrxJj0b6A281z9iWKuP</latexit>

[Meka,  Zuckerman  09]  

[Harsha,  Klivans,  Meka  10]  

Page 22: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

CDF-­‐close  

 

 

HKM’s  PRG  via  their  mulPdimensional  CLT    

Uniform  

 

Pseudorandom  

 

x ⇠ {�1, 1}n y ⇠ {�1, 1}n

Let  A  be  an  m  x  n  matrix,  where  every  row  of  A  is  regular    

Ax

<latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit><latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit><latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit>

Ay<latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit><latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit><latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit>CDF-­‐close  by  Δ-­‐inequality    

 

m-­‐dimensional  Gaussian  

(row  =  weights  of  a  regular  halfspace)    

y10  y2  y6   y3  

y12   y12  y22  y1  

CDF-­‐close  

 

 ...      

Page 23: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Regular  halfspaces   IntersecPons  of  regular  halfspaces  

Part  I:  

Part  II:  

IntersecPons  of  general  halfspaces  

[Meka,  Zuckerman  09]   [Harsha,  Klivans,  Meka  10]  

(Our  work)  

PRGs  via  Central  Limit  Theorems      

Page 24: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

IntersecPons  of  m  general  halfspaces  

Regular  halfspaces   IntersecPons  of  m  regular  halfspaces  

Other  relevant  works  not  discussed  in  Part  I:  

§  1  general  halfspace                                                                                                  [Meka,  Zuckerman  09]  

§  Any  funcBon  of  m  general  halfspaces,  but  seed  length  Õ(m)                          [Gopalan,  O’Donnell,  Wu,  Zuckerman  10]    

§  IntersecPon  of  m  low-­‐weight  halfspaces,  seed  length  polylog(m)                                          [Servedio,  T.  17]    

Part  I:   Part  II:  

Page 25: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Main  challenge:  CLTs  and  regularity  go  hand  in  hand  

Central  Limit  Theorem  false  without  regularity  assumpPon  

S(x) = w1x1 + · · ·+ wnxn N (µ,�2)

if  there  are  dominant  wi’s  

Recall  simple  example:  S(x)  =  x1  

Not  close  to  CDF  of  any  Gaussian  

Page 26: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Not  CDF-­‐close  

 

 

Not  CDF-­‐close  

 

 

Uniform  

 

Pseudorandom  

 

x ⇠ {�1, 1}n y ⇠ {�1, 1}n

Ax

<latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit><latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit><latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit>

Ay<latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit><latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit><latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit>

CDF-­‐close?  

 

m-­‐dimensional  Gaussian  

This  work:  bypassing  Gaussian  middleperson  (by  necessity)  Let  A  be  general  m  x  n  matrix  

(row  =  weights  of  general  halfspace,  not  necessarily  regular)    

Page 27: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

But—will  sPll  employ  CLT  proof  techniques  (even  though  CLT  does  not  hold!)  

§  Lindeberg  replacement  method      

§  Powerful  technique  for  proving  CLTs    [Lindeberg  22]  §  [MZ,  HKM]’s  strategy  for  the  all-­‐regular  case    

§  Non-­‐regularity  necessitates  new  ideas  and  ingredients:  §  PRGs  for  CNF  formulas    [AW85,  Nis92,  Baz07,  Raz09,  DETT10,  GMR13,  ...  ]    §  New  Litlewood–Offord  theorem  for  polytopes  

Ax

<latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit><latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit><latexit sha1_base64="UYzBDXfZIuBYgNNhpUnk+LtVyY4=">AAAB+HicdVDLSgMxFL1TX7W+Rl26CRbBVZkRX91V3bis4FihHUomk2lDM5MhyRTL0D9x40LFrZ/izr8xbUeoogdCDufcS05OkHKmtON8WqWFxaXllfJqZW19Y3PL3t65UyKThHpEcCHvA6woZwn1NNOc3qeS4jjgtBUMriZ+a0ilYiK51aOU+jHuJSxiBGsjdW37AnUCwUM1is2VP4y7dtWpOVOgOXLiuPVTF7mFUoUCza790QkFyWKaaMKxUm3XSbWfY6kZ4XRc6WSKppgMcI+2DU1wTJWfT5OP0YFRQhQJaU6i0VSd38hxrCbRzGSMdV/99ibiX14709G5n7MkzTRNyOyhKONICzSpAYVMUqL5yBBMJDNZEeljiYk2ZVVMCd8/Rf8T76hWrzk3x9XGZdFGGfZgHw7BhTNowDU0wQMCQ3iEZ3ixcuvJerXeZqMlq9jZhR+w3r8ANLKTmA==</latexit>

Uniform  x        {−1,1}n  ~  

Ay<latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit><latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit><latexit sha1_base64="4Io0uGfokJz1bKhb+lmPLNeO4y4=">AAAB+HicdVDNS8MwHE3n15xfVY9egkPwNFrxa7epF48TrBtsZaRpuoWlSUnSQSn7T7x4UPHqn+LN/8Z0qzBFH4Q83vv9yMsLEkaVdpxPq7K0vLK6Vl2vbWxube/Yu3sPSqQSEw8LJmQ3QIowyomnqWakm0iC4oCRTjC+KfzOhEhFBb/XWUL8GA05jShG2kgD276C/UCwUGWxufJsOrDrTsOZAS6QM8dtnrvQLZU6KNEe2B/9UOA0JlxjhpTquU6i/RxJTTEj01o/VSRBeIyGpGcoRzFRfj5LPoVHRglhJKQ5XMOZuriRo1gV0cxkjPRI/fYK8S+vl+ro0s8pT1JNOJ4/FKUMagGLGmBIJcGaZYYgLKnJCvEISYS1KatmSvj+KfyfeCeNZsO5O623rss2quAAHIJj4IIL0AK3oA08gMEEPIJn8GLl1pP1ar3NRytWubMPfsB6/wI2NpOZ</latexit>

Pseudorandom  y        {−1,1}n  ~  

CDF-­‐close?  

 

Page 28: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Outline  of  the  rest  of  the  talk    (=  the  structure  of  our  proof)  

1.  A  useful  decomposiPon  of  polytopes  

2.  “Smooth  version”  of  the  problem  

3.  Proving  the  smooth  version  

4.  Going  from  smooth  version  to  actual  version  

Page 29: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Regularity  lemma  for  a  single  halfspace  

Weights  of  regular  halfspace:  

Weights  of  general  halfspace:  

(No  weight  too  dominant)   Halfspace  Regularity  Lemma    [Servedio  07]    

Every  halfspace  can  be  made  regular*  by  restricPng  a  small  

number  of  variables  

*or  very  close  to  constant  

Page 30: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Halfspace  Regularity  Lemma  as  a  picture  

ε-­‐regular  “tail”  

Õ(1/ε2)  “head”  variables  

Weights  of  a  general  halfspace  sorted  by  magnitude  

Page 31: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Applying  the  regularity  lemma  to  m  halfspaces  

1st  halfspace   2nd  halfspace   mth  halfspace  (m-­‐1)st  halfspace  .  .  .    

§  Each  head  small,  but  union  of  all  m  heads  could  cover  [n]    

§  So  the  natural  strategy  of  reducing  to  the  all-­‐regular  case  –  by  “restricPng  away”  all  head  variables  –  does  not  work  

Remark:  

Page 32: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

A  useful  mental  picture:  

m  

n  

A  

1st  halfspace  

2nd  halfspace  

mth  halfspace  

.  .  .    

.  .  .      y10  y2  y6   y3  

y12   y9  y11  y4  

y7  

§  x        {−1,1}n  uniform    §  y        {−1,1}n  pseudorandom:    Goal:  Ax  and  Ay  are  close  in  

mulPdimensional  CDF  distance  

~  ~  

(Each  halfspace  has  few  head  variables)  

Page 33: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Outline  of  the  rest  of  the  talk    (=  the  structure  of  our  proof)  

1.  A  useful  decomposiPon  of  polytopes  

2.   “Smooth  version”  of  the  problem  

3.  Proving  the  smooth  version  

4.  Going  from  smooth  version  to  actual  version  

Page 34: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

A  smooth  version  of  CDF  distance  

b  

Ax  

()<latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit><latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit><latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit>

Ob  =  {0,1}-­‐indictor  of  orthant  defined  by  b    

E[ eOb(Ax)] ⇡ E[ eOb(Ay)]<latexit sha1_base64="d2hQoln80YjBgpH9m51pJWkwb3k=">AAACXniclVFdS8MwFE3rx+ambuqL4EtwCPoyWvFrb1MRfFPB6WAtI03vXFjalCTVjdI/6Zvgi//EdA78fPFCyOHce7gnJ0HCmdKO82LZc/MLi6XyUqW6vLJaq6+t3ymRSgodKriQ3YAo4CyGjmaaQzeRQKKAw30wOi/6948gFRPxrZ4k4EfkIWYDRok2VL/+6EVED4Mgu8h73hMLQTMeQjZlKeHZVZ73g91TLxA8VJPIXNk43/OxR5JEijGu/F8/Mfp+veE0Dx23deRip+lM6xO4M9BAs7ru15+9UNA0glhTTpTquU6i/YxIzSiHvOKlChJCR+QBegbGJALlZ9N8crxjmBAPhDQn1njKflVkJFKFOTNZ+FY/ewX5V6+X6sGJn7E4STXE9GPRIOVYC1yEjUMmgWo+MYBQyYxXTIdEEqrNl1RMCO7PJ/8Gnf1mq+ncHDTaZ7M0ymgLbaNd5KJj1EaX6Bp1EEWvlm1VrWXrzS7ZK3btY9S2ZpoN9K3szXdmori6</latexit><latexit sha1_base64="d2hQoln80YjBgpH9m51pJWkwb3k=">AAACXniclVFdS8MwFE3rx+ambuqL4EtwCPoyWvFrb1MRfFPB6WAtI03vXFjalCTVjdI/6Zvgi//EdA78fPFCyOHce7gnJ0HCmdKO82LZc/MLi6XyUqW6vLJaq6+t3ymRSgodKriQ3YAo4CyGjmaaQzeRQKKAw30wOi/6948gFRPxrZ4k4EfkIWYDRok2VL/+6EVED4Mgu8h73hMLQTMeQjZlKeHZVZ73g91TLxA8VJPIXNk43/OxR5JEijGu/F8/Mfp+veE0Dx23deRip+lM6xO4M9BAs7ru15+9UNA0glhTTpTquU6i/YxIzSiHvOKlChJCR+QBegbGJALlZ9N8crxjmBAPhDQn1njKflVkJFKFOTNZ+FY/ewX5V6+X6sGJn7E4STXE9GPRIOVYC1yEjUMmgWo+MYBQyYxXTIdEEqrNl1RMCO7PJ/8Gnf1mq+ncHDTaZ7M0ymgLbaNd5KJj1EaX6Bp1EEWvlm1VrWXrzS7ZK3btY9S2ZpoN9K3szXdmori6</latexit><latexit sha1_base64="d2hQoln80YjBgpH9m51pJWkwb3k=">AAACXniclVFdS8MwFE3rx+ambuqL4EtwCPoyWvFrb1MRfFPB6WAtI03vXFjalCTVjdI/6Zvgi//EdA78fPFCyOHce7gnJ0HCmdKO82LZc/MLi6XyUqW6vLJaq6+t3ymRSgodKriQ3YAo4CyGjmaaQzeRQKKAw30wOi/6948gFRPxrZ4k4EfkIWYDRok2VL/+6EVED4Mgu8h73hMLQTMeQjZlKeHZVZ73g91TLxA8VJPIXNk43/OxR5JEijGu/F8/Mfp+veE0Dx23deRip+lM6xO4M9BAs7ru15+9UNA0glhTTpTquU6i/YxIzSiHvOKlChJCR+QBegbGJALlZ9N8crxjmBAPhDQn1njKflVkJFKFOTNZ+FY/ewX5V6+X6sGJn7E4STXE9GPRIOVYC1yEjUMmgWo+MYBQyYxXTIdEEqrNl1RMCO7PJ/8Gnf1mq+ncHDTaZ7M0ymgLbaNd5KJj1EaX6Bp1EEWvlm1VrWXrzS7ZK3btY9S2ZpoN9K3szXdmori6</latexit>

eOb : Rm ! [0, 1]<latexit sha1_base64="5HN1hMLB4ArVqmMWX4iu+k4/XF0=">AAACG3icbVDLSgMxFM3Ud32NunQTLIILKRnfuhLduPOB1UJnLJnMbRuaeZBklDLMh7jxV9y4UHEluPBvTB+gVg8EDufcS+45fiK40oR8WoWR0bHxicmp4vTM7Ny8vbB4peJUMqiwWMSy6lMFgkdQ0VwLqCYSaOgLuPbbx13/+hak4nF0qTsJeCFtRrzBGdVGqtub7h0PQHMRQOaGVLcYFdlpntd9fIB7gu9nF/lNiF0d4xpZdzxct0ukvE2c/R0HkzLp4Zs4A1JCA5zV7Xc3iFkaQqSZoErVHJJoL6NScyYgL7qpgoSyNm1CzdCIhqC8rBcux6tGCXAjluZFGvfUnxsZDZXqhL6Z7J6rhr2u+J9XS3Vjz8t4lKQaItb/qJEKbHJ2m8IBl8C06BhCmeTmVsxaVFKmTZ9FU4IzHPkvqWyU98vkfKt0eDRoYxItoxW0hhy0iw7RCTpDFcTQPXpEz+jFerCerFfrrT9asAY7S+gXrI8vdHShHA==</latexit><latexit sha1_base64="5HN1hMLB4ArVqmMWX4iu+k4/XF0=">AAACG3icbVDLSgMxFM3Ud32NunQTLIILKRnfuhLduPOB1UJnLJnMbRuaeZBklDLMh7jxV9y4UHEluPBvTB+gVg8EDufcS+45fiK40oR8WoWR0bHxicmp4vTM7Ny8vbB4peJUMqiwWMSy6lMFgkdQ0VwLqCYSaOgLuPbbx13/+hak4nF0qTsJeCFtRrzBGdVGqtub7h0PQHMRQOaGVLcYFdlpntd9fIB7gu9nF/lNiF0d4xpZdzxct0ukvE2c/R0HkzLp4Zs4A1JCA5zV7Xc3iFkaQqSZoErVHJJoL6NScyYgL7qpgoSyNm1CzdCIhqC8rBcux6tGCXAjluZFGvfUnxsZDZXqhL6Z7J6rhr2u+J9XS3Vjz8t4lKQaItb/qJEKbHJ2m8IBl8C06BhCmeTmVsxaVFKmTZ9FU4IzHPkvqWyU98vkfKt0eDRoYxItoxW0hhy0iw7RCTpDFcTQPXpEz+jFerCerFfrrT9asAY7S+gXrI8vdHShHA==</latexit><latexit sha1_base64="5HN1hMLB4ArVqmMWX4iu+k4/XF0=">AAACG3icbVDLSgMxFM3Ud32NunQTLIILKRnfuhLduPOB1UJnLJnMbRuaeZBklDLMh7jxV9y4UHEluPBvTB+gVg8EDufcS+45fiK40oR8WoWR0bHxicmp4vTM7Ny8vbB4peJUMqiwWMSy6lMFgkdQ0VwLqCYSaOgLuPbbx13/+hak4nF0qTsJeCFtRrzBGdVGqtub7h0PQHMRQOaGVLcYFdlpntd9fIB7gu9nF/lNiF0d4xpZdzxct0ukvE2c/R0HkzLp4Zs4A1JCA5zV7Xc3iFkaQqSZoErVHJJoL6NScyYgL7qpgoSyNm1CzdCIhqC8rBcux6tGCXAjluZFGvfUnxsZDZXqhL6Z7J6rhr2u+J9XS3Vjz8t4lKQaItb/qJEKbHJ2m8IBl8C06BhCmeTmVsxaVFKmTZ9FU4IzHPkvqWyU98vkfKt0eDRoYxItoxW0hhy0iw7RCTpDFcTQPXpEz+jFerCerFfrrT9asAY7S+gXrI8vdHShHA==</latexit>

Ob : Rm ! {0, 1}<latexit sha1_base64="UvAyLDMLDrRfq85GBGvxrfTMxBQ=">AAACEXicdVDLSsNAFJ3UV62vqEs3g0VQkJKIr7oqunFnFWMLTQyT6bQdOnkwMxFKyDe48VfcuFBx686df+MkjVBFDwycOede7r3HixgV0jA+tdLU9MzsXHm+srC4tLyir67diDDmmFg4ZCFve0gQRgNiSSoZaUecIN9jpOUNzzK/dUe4oGFwLUcRcXzUD2iPYiSV5Oo7to/kACOWXKSuB09g/ve85Cq99aEtQ2gnxq5pp9DVq0bNyAEnyIFh1g9NaBZKFRRouvqH3Q1x7JNAYoaE6JhGJJ0EcUkxI2nFjgWJEB6iPukoGiCfCCfJT0rhllK6sBdy9QIJc3WyI0G+ECPfU5XZwuK3l4l/eZ1Y9o6dhAZRLEmAx4N6MYPq0iwf2KWcYMlGiiDMqdoV4gHiCEuVYkWF8H0p/J9Ye7V6zbjcrzZOizTKYANsgm1ggiPQAOegCSyAwT14BM/gRXvQnrRX7W1cWtKKnnXwA9r7FwvSnKE=</latexit><latexit sha1_base64="UvAyLDMLDrRfq85GBGvxrfTMxBQ=">AAACEXicdVDLSsNAFJ3UV62vqEs3g0VQkJKIr7oqunFnFWMLTQyT6bQdOnkwMxFKyDe48VfcuFBx686df+MkjVBFDwycOede7r3HixgV0jA+tdLU9MzsXHm+srC4tLyir67diDDmmFg4ZCFve0gQRgNiSSoZaUecIN9jpOUNzzK/dUe4oGFwLUcRcXzUD2iPYiSV5Oo7to/kACOWXKSuB09g/ve85Cq99aEtQ2gnxq5pp9DVq0bNyAEnyIFh1g9NaBZKFRRouvqH3Q1x7JNAYoaE6JhGJJ0EcUkxI2nFjgWJEB6iPukoGiCfCCfJT0rhllK6sBdy9QIJc3WyI0G+ECPfU5XZwuK3l4l/eZ1Y9o6dhAZRLEmAx4N6MYPq0iwf2KWcYMlGiiDMqdoV4gHiCEuVYkWF8H0p/J9Ye7V6zbjcrzZOizTKYANsgm1ggiPQAOegCSyAwT14BM/gRXvQnrRX7W1cWtKKnnXwA9r7FwvSnKE=</latexit><latexit sha1_base64="UvAyLDMLDrRfq85GBGvxrfTMxBQ=">AAACEXicdVDLSsNAFJ3UV62vqEs3g0VQkJKIr7oqunFnFWMLTQyT6bQdOnkwMxFKyDe48VfcuFBx686df+MkjVBFDwycOede7r3HixgV0jA+tdLU9MzsXHm+srC4tLyir67diDDmmFg4ZCFve0gQRgNiSSoZaUecIN9jpOUNzzK/dUe4oGFwLUcRcXzUD2iPYiSV5Oo7to/kACOWXKSuB09g/ve85Cq99aEtQ2gnxq5pp9DVq0bNyAEnyIFh1g9NaBZKFRRouvqH3Q1x7JNAYoaE6JhGJJ0EcUkxI2nFjgWJEB6iPukoGiCfCCfJT0rhllK6sBdy9QIJc3WyI0G+ECPfU5XZwuK3l4l/eZ1Y9o6dhAZRLEmAx4N6MYPq0iwf2KWcYMlGiiDMqdoV4gHiCEuVYkWF8H0p/J9Ye7V6zbjcrzZOizTKYANsgm1ggiPQAOegCSyAwT14BM/gRXvQnrRX7W1cWtKKnnXwA9r7FwvSnKE=</latexit>

Orthant  Ob  

Ax  ≤  b  iff:  We  will  first  show:  

where    

is  smooth  approximator  of    

()<latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit><latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit><latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit>

E[Ob(Ax)] ⇡ E[Ob(Ay)] for all b 2 Rm<latexit sha1_base64="oLS5iLfO2JtqZesN4g6QKIF0B+c=">AAACa3icjVFNTxRBEO0ZQXEFWcUDqIcOCwleNjOGD7mhhMSbaFgg2Rk31b090KGne9JdQ3YzmZP/kBs/wQu/wZ5lJWA0sfrQL6/qVVe9ZoWSDqPoOggfzcw+fjL3tPVsfuH5YvvFy2NnSstFjxtl7CkDJ5TUoocSlTgtrICcKXHCLvab/MmlsE4afYTjQqQ5nGmZSQ7oqUH7R5IDnjNWHdT9CeSgqi/1gG18TJhRQzfO/VWN6ncpTaAorBnR/5OMvSSh/qAYYZUZS0EpusYSqe86fKu/52v1oN2JutEk6D2wFcW72zGNp0yHTONw0L5KhoaXudDIFTjXj6MC0wosSq5E3UpKJwrgF3Am+h5qyIVLq4lZNV33zJA282RGI52w9xUV5K5ZwVc2U7o/cw35t1y/xOxDWkldlCg0v30oKxVFQxvn6VBawVGNPQBupZ+V8nOwwNH/T8ub8HtT+m/Qe9/d7UZfNzt7n6ZuzJE3ZJVskJjskD3ymRySHuHkZ7AYLAcrwU34Knwdvr0tDYOpZok8iHD9F+LHvME=</latexit><latexit sha1_base64="oLS5iLfO2JtqZesN4g6QKIF0B+c=">AAACa3icjVFNTxRBEO0ZQXEFWcUDqIcOCwleNjOGD7mhhMSbaFgg2Rk31b090KGne9JdQ3YzmZP/kBs/wQu/wZ5lJWA0sfrQL6/qVVe9ZoWSDqPoOggfzcw+fjL3tPVsfuH5YvvFy2NnSstFjxtl7CkDJ5TUoocSlTgtrICcKXHCLvab/MmlsE4afYTjQqQ5nGmZSQ7oqUH7R5IDnjNWHdT9CeSgqi/1gG18TJhRQzfO/VWN6ncpTaAorBnR/5OMvSSh/qAYYZUZS0EpusYSqe86fKu/52v1oN2JutEk6D2wFcW72zGNp0yHTONw0L5KhoaXudDIFTjXj6MC0wosSq5E3UpKJwrgF3Am+h5qyIVLq4lZNV33zJA282RGI52w9xUV5K5ZwVc2U7o/cw35t1y/xOxDWkldlCg0v30oKxVFQxvn6VBawVGNPQBupZ+V8nOwwNH/T8ub8HtT+m/Qe9/d7UZfNzt7n6ZuzJE3ZJVskJjskD3ymRySHuHkZ7AYLAcrwU34Knwdvr0tDYOpZok8iHD9F+LHvME=</latexit><latexit sha1_base64="oLS5iLfO2JtqZesN4g6QKIF0B+c=">AAACa3icjVFNTxRBEO0ZQXEFWcUDqIcOCwleNjOGD7mhhMSbaFgg2Rk31b090KGne9JdQ3YzmZP/kBs/wQu/wZ5lJWA0sfrQL6/qVVe9ZoWSDqPoOggfzcw+fjL3tPVsfuH5YvvFy2NnSstFjxtl7CkDJ5TUoocSlTgtrICcKXHCLvab/MmlsE4afYTjQqQ5nGmZSQ7oqUH7R5IDnjNWHdT9CeSgqi/1gG18TJhRQzfO/VWN6ncpTaAorBnR/5OMvSSh/qAYYZUZS0EpusYSqe86fKu/52v1oN2JutEk6D2wFcW72zGNp0yHTONw0L5KhoaXudDIFTjXj6MC0wosSq5E3UpKJwrgF3Am+h5qyIVLq4lZNV33zJA282RGI52w9xUV5K5ZwVc2U7o/cw35t1y/xOxDWkldlCg0v30oKxVFQxvn6VBawVGNPQBupZ+V8nOwwNH/T8ub8HtT+m/Qe9/d7UZfNzt7n6ZuzJE3ZJVskJjskD3ymRySHuHkZ7AYLAcrwU34Knwdvr0tDYOpZok8iHD9F+LHvME=</latexit>

Pr[Ax b] ⇡ Pr[Ay b] for all b 2 Rm<latexit sha1_base64="+/l1gssPw2ZXacEgA3FHCUbSjlM=">AAACWXicdVFNbxMxEPUupU3DRwM9crGaInGKdhEUeivlwjFFhFbKLpHtzLZW/bHYsyjRav9kL1Ul/goS3mQrFdSOD356854888xLJT0myU0UP9p4vLnV2+4/efrs+c7gxcvv3lZOwERYZd0ZZx6UNDBBiQrOSgdMcwWn/PJz2z/9Bc5La77hsoRcs3MjCykYBmo2+JlphhdO12PXTD9l3Kq5X+pw1YsmU0B5TjNWls4u6IPKZafMaDgIC6wL6yhTiu7zTJq1kfP6a/ND7zezwTAZJauid8D7JD08SGnaMUPS1Xg2uMrmVlQaDArFvJ+mSYl5zRxKoaDpZ5WHkolLdg7TAA3T4PN6FU1DXwdmTtt5CmuQrti7jppp364RlO2U/v9eS97Xm1ZYfMxracoKwYj1Q0WlKFra5kzn0oFAtQyACSfDrFRcMMcEht/ohxBuN6UPg8nb0eEoOXk3PDru0uiRV2SPvCEp+UCOyBcyJhMiyDX5E21GW9HvOI57cX8tjaPOs0v+qXj3L0nmtnw=</latexit><latexit sha1_base64="+/l1gssPw2ZXacEgA3FHCUbSjlM=">AAACWXicdVFNbxMxEPUupU3DRwM9crGaInGKdhEUeivlwjFFhFbKLpHtzLZW/bHYsyjRav9kL1Ul/goS3mQrFdSOD356854888xLJT0myU0UP9p4vLnV2+4/efrs+c7gxcvv3lZOwERYZd0ZZx6UNDBBiQrOSgdMcwWn/PJz2z/9Bc5La77hsoRcs3MjCykYBmo2+JlphhdO12PXTD9l3Kq5X+pw1YsmU0B5TjNWls4u6IPKZafMaDgIC6wL6yhTiu7zTJq1kfP6a/ND7zezwTAZJauid8D7JD08SGnaMUPS1Xg2uMrmVlQaDArFvJ+mSYl5zRxKoaDpZ5WHkolLdg7TAA3T4PN6FU1DXwdmTtt5CmuQrti7jppp364RlO2U/v9eS97Xm1ZYfMxracoKwYj1Q0WlKFra5kzn0oFAtQyACSfDrFRcMMcEht/ohxBuN6UPg8nb0eEoOXk3PDru0uiRV2SPvCEp+UCOyBcyJhMiyDX5E21GW9HvOI57cX8tjaPOs0v+qXj3L0nmtnw=</latexit><latexit sha1_base64="+/l1gssPw2ZXacEgA3FHCUbSjlM=">AAACWXicdVFNbxMxEPUupU3DRwM9crGaInGKdhEUeivlwjFFhFbKLpHtzLZW/bHYsyjRav9kL1Ul/goS3mQrFdSOD356854888xLJT0myU0UP9p4vLnV2+4/efrs+c7gxcvv3lZOwERYZd0ZZx6UNDBBiQrOSgdMcwWn/PJz2z/9Bc5La77hsoRcs3MjCykYBmo2+JlphhdO12PXTD9l3Kq5X+pw1YsmU0B5TjNWls4u6IPKZafMaDgIC6wL6yhTiu7zTJq1kfP6a/ND7zezwTAZJauid8D7JD08SGnaMUPS1Xg2uMrmVlQaDArFvJ+mSYl5zRxKoaDpZ5WHkolLdg7TAA3T4PN6FU1DXwdmTtt5CmuQrti7jppp364RlO2U/v9eS97Xm1ZYfMxracoKwYj1Q0WlKFra5kzn0oFAtQyACSfDrFRcMMcEht/ohxBuN6UPg8nb0eEoOXk3PDru0uiRV2SPvCEp+UCOyBcyJhMiyDX5E21GW9HvOI57cX8tjaPOs0v+qXj3L0nmtnw=</latexit>

Ax and Ay are CDF-close

<latexit sha1_base64="LaBvPiC7CPWLnZxDN7twbkUwT9I=">AAACJHicdZBNSwMxEIazflu/qh69BKvgxbIrfoKHakU8KlgV2lKy2akGs8mSzIpl6Z/x4l/x4kHFgxd/i9laQUUHQl6emWFm3jCRwqLvv3kDg0PDI6Nj44WJyanpmeLs3JnVqeFQ41pqcxEyC1IoqKFACReJARaHEs7D62qeP78BY4VWp9hJoBmzSyXagjN0qFXcbSDcYra01wi1jGwndl92212iTEX0J+3k1ACtHhyucqktdFvFkl/2e0G/iQ0/2NkMaNAnJdKP41bxuRFpnsagkEtmbT3wE2xmzKDgErqFRmohYfyaXULdScVisM2sd2WXLjsS0bY27imkPfq9I2OxzVd1lTHDK/s7l8O/cvUU29vNTKgkRVD8c1A7lRQ1zS2jkTDAUXacYNwItyvlV8wwjs7YgjPh61L6v6itlXfK/sl6qbLfd2OMLJBFskICskUq5Igckxrh5I48kCfy7N17j96L9/pZOuD1e+bJj/DePwDsmaUZ</latexit><latexit sha1_base64="LaBvPiC7CPWLnZxDN7twbkUwT9I=">AAACJHicdZBNSwMxEIazflu/qh69BKvgxbIrfoKHakU8KlgV2lKy2akGs8mSzIpl6Z/x4l/x4kHFgxd/i9laQUUHQl6emWFm3jCRwqLvv3kDg0PDI6Nj44WJyanpmeLs3JnVqeFQ41pqcxEyC1IoqKFACReJARaHEs7D62qeP78BY4VWp9hJoBmzSyXagjN0qFXcbSDcYra01wi1jGwndl92212iTEX0J+3k1ACtHhyucqktdFvFkl/2e0G/iQ0/2NkMaNAnJdKP41bxuRFpnsagkEtmbT3wE2xmzKDgErqFRmohYfyaXULdScVisM2sd2WXLjsS0bY27imkPfq9I2OxzVd1lTHDK/s7l8O/cvUU29vNTKgkRVD8c1A7lRQ1zS2jkTDAUXacYNwItyvlV8wwjs7YgjPh61L6v6itlXfK/sl6qbLfd2OMLJBFskICskUq5Igckxrh5I48kCfy7N17j96L9/pZOuD1e+bJj/DePwDsmaUZ</latexit><latexit sha1_base64="LaBvPiC7CPWLnZxDN7twbkUwT9I=">AAACJHicdZBNSwMxEIazflu/qh69BKvgxbIrfoKHakU8KlgV2lKy2akGs8mSzIpl6Z/x4l/x4kHFgxd/i9laQUUHQl6emWFm3jCRwqLvv3kDg0PDI6Nj44WJyanpmeLs3JnVqeFQ41pqcxEyC1IoqKFACReJARaHEs7D62qeP78BY4VWp9hJoBmzSyXagjN0qFXcbSDcYra01wi1jGwndl92212iTEX0J+3k1ACtHhyucqktdFvFkl/2e0G/iQ0/2NkMaNAnJdKP41bxuRFpnsagkEtmbT3wE2xmzKDgErqFRmohYfyaXULdScVisM2sd2WXLjsS0bY27imkPfq9I2OxzVd1lTHDK/s7l8O/cvUU29vNTKgkRVD8c1A7lRQ1zS2jkTDAUXacYNwItyvlV8wwjs7YgjPh61L6v6itlXfK/sl6qbLfd2OMLJBFskICskUq5Igckxrh5I48kCfy7N17j96L9/pZOuD1e+bJj/DePwDsmaUZ</latexit>

“mollifier”  

Rm<latexit sha1_base64="zPdAsyhTX1468yfc7dxQYy7M8cE=">AAAB8nicdVDLSgMxFM3UV62vqks3wSK4GjLiq7uiG5dVHFvojCWTZtrQJDMkGaEM/Q03LlTc+jXu/BszbRUVPRA4nHMv9+REKWfaIPTulObmFxaXysuVldW19Y3q5taNTjJFqE8Snqh2hDXlTFLfMMNpO1UUi4jTVjQ8L/zWHVWaJfLajFIaCtyXLGYEGysFgcBmEEX51fhWdKs15B4hr37sQeSiCeCX4s2UGpih2a2+Bb2EZIJKQzjWuuOh1IQ5VoYRTseVINM0xWSI+7RjqcSC6jCfZB7DPav0YJwo+6SBE/X7Ro6F1iMR2ckio/7tFeJfXicz8WmYM5lmhkoyPRRnHJoEFgXAHlOUGD6yBBPFbFZIBlhhYmxNFVvC50/h/8Q/cOsuujysNc5mbZTBDtgF+8ADJ6ABLkAT+ICAFNyDR/DkZM6D8+y8TEdLzmxnG/yA8/oB7KyR0A==</latexit><latexit sha1_base64="zPdAsyhTX1468yfc7dxQYy7M8cE=">AAAB8nicdVDLSgMxFM3UV62vqks3wSK4GjLiq7uiG5dVHFvojCWTZtrQJDMkGaEM/Q03LlTc+jXu/BszbRUVPRA4nHMv9+REKWfaIPTulObmFxaXysuVldW19Y3q5taNTjJFqE8Snqh2hDXlTFLfMMNpO1UUi4jTVjQ8L/zWHVWaJfLajFIaCtyXLGYEGysFgcBmEEX51fhWdKs15B4hr37sQeSiCeCX4s2UGpih2a2+Bb2EZIJKQzjWuuOh1IQ5VoYRTseVINM0xWSI+7RjqcSC6jCfZB7DPav0YJwo+6SBE/X7Ro6F1iMR2ckio/7tFeJfXicz8WmYM5lmhkoyPRRnHJoEFgXAHlOUGD6yBBPFbFZIBlhhYmxNFVvC50/h/8Q/cOsuujysNc5mbZTBDtgF+8ADJ6ABLkAT+ICAFNyDR/DkZM6D8+y8TEdLzmxnG/yA8/oB7KyR0A==</latexit><latexit sha1_base64="zPdAsyhTX1468yfc7dxQYy7M8cE=">AAAB8nicdVDLSgMxFM3UV62vqks3wSK4GjLiq7uiG5dVHFvojCWTZtrQJDMkGaEM/Q03LlTc+jXu/BszbRUVPRA4nHMv9+REKWfaIPTulObmFxaXysuVldW19Y3q5taNTjJFqE8Snqh2hDXlTFLfMMNpO1UUi4jTVjQ8L/zWHVWaJfLajFIaCtyXLGYEGysFgcBmEEX51fhWdKs15B4hr37sQeSiCeCX4s2UGpih2a2+Bb2EZIJKQzjWuuOh1IQ5VoYRTseVINM0xWSI+7RjqcSC6jCfZB7DPav0YJwo+6SBE/X7Ro6F1iMR2ckio/7tFeJfXicz8WmYM5lmhkoyPRRnHJoEFgXAHlOUGD6yBBPFbFZIBlhhYmxNFVvC50/h/8Q/cOsuujysNc5mbZTBDtgF+8ADJ6ABLkAT+ICAFNyDR/DkZM6D8+y8TEdLzmxnG/yA8/oB7KyR0A==</latexit>

DisconPnuous  funcPon!  

Page 35: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Smooth  approximators  of  orthants  

Two  important  properPes  of  Õb  [Bentkus  90]:    

eOb(v) = EG⇠N (0,1)m

[Ob(v + �G)]<latexit sha1_base64="a17BU7N19FojprmI9WBFHkGnY1s=">AAACcXicdVHbihQxEE23t3W8jYovClrsIMywy9At3vZBWBTRJ13BcRem2yZJ1+yGTTpNkh4ZQn+Av+ebX+GLH2B6ZpRZ0YKQwzlVlaoTVkthXZJ8j+Jz5y9cvLR1uXfl6rXrN/o3b32yujEcJ1xLbY4YtShFhRMnnMSj2iBVTOIhO33V6YdzNFbo6qNb1JgrelyJmeDUBarof82+iBKdkCX6TFF3wqn079u28KwdzkfwApasrlcqY/51J2ZMy9IuVLj8mxYyKxT8KX/XDpPddPRZtdONlgUbzmEHMhmGKymc7TDKoegPknGyDNgAT5J072kK6ZoZkHUcFP1vWal5o7ByXFJrp2lSu9xT4wSX2PayxmJN+Sk9xmmAFVVoc7+0rIWHgSlhpk04lYMlu1nhqbLddCGzW8H+rXXkv7Rp42bPcy+qunFY8dVDs0aC09D5D6UwyJ1cBEC5EWFW4CfUUO7CL/WCCb83hf+DyaPx3jj58Hiw/3Ltxha5R7bJkKTkGdknb8kBmRBOfkR3ovvRg+hnfDeGeHuVGkfrmtvkTMQ7vwBLd76M</latexit><latexit sha1_base64="a17BU7N19FojprmI9WBFHkGnY1s=">AAACcXicdVHbihQxEE23t3W8jYovClrsIMywy9At3vZBWBTRJ13BcRem2yZJ1+yGTTpNkh4ZQn+Av+ebX+GLH2B6ZpRZ0YKQwzlVlaoTVkthXZJ8j+Jz5y9cvLR1uXfl6rXrN/o3b32yujEcJ1xLbY4YtShFhRMnnMSj2iBVTOIhO33V6YdzNFbo6qNb1JgrelyJmeDUBarof82+iBKdkCX6TFF3wqn079u28KwdzkfwApasrlcqY/51J2ZMy9IuVLj8mxYyKxT8KX/XDpPddPRZtdONlgUbzmEHMhmGKymc7TDKoegPknGyDNgAT5J072kK6ZoZkHUcFP1vWal5o7ByXFJrp2lSu9xT4wSX2PayxmJN+Sk9xmmAFVVoc7+0rIWHgSlhpk04lYMlu1nhqbLddCGzW8H+rXXkv7Rp42bPcy+qunFY8dVDs0aC09D5D6UwyJ1cBEC5EWFW4CfUUO7CL/WCCb83hf+DyaPx3jj58Hiw/3Ltxha5R7bJkKTkGdknb8kBmRBOfkR3ovvRg+hnfDeGeHuVGkfrmtvkTMQ7vwBLd76M</latexit><latexit sha1_base64="a17BU7N19FojprmI9WBFHkGnY1s=">AAACcXicdVHbihQxEE23t3W8jYovClrsIMywy9At3vZBWBTRJ13BcRem2yZJ1+yGTTpNkh4ZQn+Av+ebX+GLH2B6ZpRZ0YKQwzlVlaoTVkthXZJ8j+Jz5y9cvLR1uXfl6rXrN/o3b32yujEcJ1xLbY4YtShFhRMnnMSj2iBVTOIhO33V6YdzNFbo6qNb1JgrelyJmeDUBarof82+iBKdkCX6TFF3wqn079u28KwdzkfwApasrlcqY/51J2ZMy9IuVLj8mxYyKxT8KX/XDpPddPRZtdONlgUbzmEHMhmGKymc7TDKoegPknGyDNgAT5J072kK6ZoZkHUcFP1vWal5o7ByXFJrp2lSu9xT4wSX2PayxmJN+Sk9xmmAFVVoc7+0rIWHgSlhpk04lYMlu1nhqbLddCGzW8H+rXXkv7Rp42bPcy+qunFY8dVDs0aC09D5D6UwyJ1cBEC5EWFW4CfUUO7CL/WCCb83hf+DyaPx3jj58Hiw/3Ltxha5R7bJkKTkGdknb8kBmRBOfkR3ovvRg+hnfDeGeHuVGkfrmtvkTMQ7vwBLd76M</latexit>

Standard  way  of  mollifying  a  funcPon:  adding  Gaussian  noise  

1.  Good  approximaPon  of  Ob  

2.  Small  derivaPves:  for  all  c  >  1,  

sup

v2Rm

(X

|↵|=c

|@↵ eOb(v)|)

. (logm)

c/2

�c

<latexit sha1_base64="zcnErT6IswuVo5XUaOgLms06khg=">AAACe3icdVHLjtMwFHXCayivAksWWBSkFqGSjBhgFkijYcOOAVFmpLqNbhwntcZ2rNgpqlx/BX/Gjk9hg3DaIg0IjmTp6NyH7z0314IbmyTfo/jS5StXr+1d7924eev2nf7de59N3TaUTWgt6uYsB8MEV2xiuRXsTDcMZC7YaX7+toufLlljeK0+2ZVmMwmV4iWnYIOU9b8S0+rMLTHhChMJdpHn7qOfS0+OeVURh0OCzNyagNALWL+hfk00NJaDyNxW9OQLL5jlomBu04KCcO+9z/LhcrTe9vEYE8GMMVxiUjZA3ZCIusJyNHf0+b73jogwdQFz6rP+IBknG+AL5CBJD1+mON0pA7TDSdb/RoqatpIpSwUYM00TbWeum5IK5nukNUwDPYeKTQNVIJmZuY15Hj8JSoHLuglPWbxRL1Y4kMasZB4yu93M37FO/Fds2try9cxxpVvLFN1+VLYC2xp3l8AFbxi1YhUI0IaHWTFdQLDGhnv1ggm/N8X/J5P98eE4+fBicHS8c2MPPUCP0BCl6BU6Qu/QCZogin5ED6NhNIp+xo/jp/GzbWoc7Wruoz8QH/wChofEbg==</latexit><latexit sha1_base64="zcnErT6IswuVo5XUaOgLms06khg=">AAACe3icdVHLjtMwFHXCayivAksWWBSkFqGSjBhgFkijYcOOAVFmpLqNbhwntcZ2rNgpqlx/BX/Gjk9hg3DaIg0IjmTp6NyH7z0314IbmyTfo/jS5StXr+1d7924eev2nf7de59N3TaUTWgt6uYsB8MEV2xiuRXsTDcMZC7YaX7+toufLlljeK0+2ZVmMwmV4iWnYIOU9b8S0+rMLTHhChMJdpHn7qOfS0+OeVURh0OCzNyagNALWL+hfk00NJaDyNxW9OQLL5jlomBu04KCcO+9z/LhcrTe9vEYE8GMMVxiUjZA3ZCIusJyNHf0+b73jogwdQFz6rP+IBknG+AL5CBJD1+mON0pA7TDSdb/RoqatpIpSwUYM00TbWeum5IK5nukNUwDPYeKTQNVIJmZuY15Hj8JSoHLuglPWbxRL1Y4kMasZB4yu93M37FO/Fds2try9cxxpVvLFN1+VLYC2xp3l8AFbxi1YhUI0IaHWTFdQLDGhnv1ggm/N8X/J5P98eE4+fBicHS8c2MPPUCP0BCl6BU6Qu/QCZogin5ED6NhNIp+xo/jp/GzbWoc7Wruoz8QH/wChofEbg==</latexit><latexit sha1_base64="zcnErT6IswuVo5XUaOgLms06khg=">AAACe3icdVHLjtMwFHXCayivAksWWBSkFqGSjBhgFkijYcOOAVFmpLqNbhwntcZ2rNgpqlx/BX/Gjk9hg3DaIg0IjmTp6NyH7z0314IbmyTfo/jS5StXr+1d7924eev2nf7de59N3TaUTWgt6uYsB8MEV2xiuRXsTDcMZC7YaX7+toufLlljeK0+2ZVmMwmV4iWnYIOU9b8S0+rMLTHhChMJdpHn7qOfS0+OeVURh0OCzNyagNALWL+hfk00NJaDyNxW9OQLL5jlomBu04KCcO+9z/LhcrTe9vEYE8GMMVxiUjZA3ZCIusJyNHf0+b73jogwdQFz6rP+IBknG+AL5CBJD1+mON0pA7TDSdb/RoqatpIpSwUYM00TbWeum5IK5nukNUwDPYeKTQNVIJmZuY15Hj8JSoHLuglPWbxRL1Y4kMasZB4yu93M37FO/Fds2try9cxxpVvLFN1+VLYC2xp3l8AFbxi1YhUI0IaHWTFdQLDGhnv1ggm/N8X/J5P98eE4+fBicHS8c2MPPUCP0BCl6BU6Qu/QCZogin5ED6NhNIp+xo/jp/GzbWoc7Wruoz8QH/wChofEbg==</latexit>

mc  many  parPal  derivaPves  

small  error  region  

≈  1  

≈  0  

Orthant  Ob  

Rm<latexit sha1_base64="zPdAsyhTX1468yfc7dxQYy7M8cE=">AAAB8nicdVDLSgMxFM3UV62vqks3wSK4GjLiq7uiG5dVHFvojCWTZtrQJDMkGaEM/Q03LlTc+jXu/BszbRUVPRA4nHMv9+REKWfaIPTulObmFxaXysuVldW19Y3q5taNTjJFqE8Snqh2hDXlTFLfMMNpO1UUi4jTVjQ8L/zWHVWaJfLajFIaCtyXLGYEGysFgcBmEEX51fhWdKs15B4hr37sQeSiCeCX4s2UGpih2a2+Bb2EZIJKQzjWuuOh1IQ5VoYRTseVINM0xWSI+7RjqcSC6jCfZB7DPav0YJwo+6SBE/X7Ro6F1iMR2ckio/7tFeJfXicz8WmYM5lmhkoyPRRnHJoEFgXAHlOUGD6yBBPFbFZIBlhhYmxNFVvC50/h/8Q/cOsuujysNc5mbZTBDtgF+8ADJ6ABLkAT+ICAFNyDR/DkZM6D8+y8TEdLzmxnG/yA8/oB7KyR0A==</latexit><latexit sha1_base64="zPdAsyhTX1468yfc7dxQYy7M8cE=">AAAB8nicdVDLSgMxFM3UV62vqks3wSK4GjLiq7uiG5dVHFvojCWTZtrQJDMkGaEM/Q03LlTc+jXu/BszbRUVPRA4nHMv9+REKWfaIPTulObmFxaXysuVldW19Y3q5taNTjJFqE8Snqh2hDXlTFLfMMNpO1UUi4jTVjQ8L/zWHVWaJfLajFIaCtyXLGYEGysFgcBmEEX51fhWdKs15B4hr37sQeSiCeCX4s2UGpih2a2+Bb2EZIJKQzjWuuOh1IQ5VoYRTseVINM0xWSI+7RjqcSC6jCfZB7DPav0YJwo+6SBE/X7Ro6F1iMR2ckio/7tFeJfXicz8WmYM5lmhkoyPRRnHJoEFgXAHlOUGD6yBBPFbFZIBlhhYmxNFVvC50/h/8Q/cOsuujysNc5mbZTBDtgF+8ADJ6ABLkAT+ICAFNyDR/DkZM6D8+y8TEdLzmxnG/yA8/oB7KyR0A==</latexit><latexit sha1_base64="zPdAsyhTX1468yfc7dxQYy7M8cE=">AAAB8nicdVDLSgMxFM3UV62vqks3wSK4GjLiq7uiG5dVHFvojCWTZtrQJDMkGaEM/Q03LlTc+jXu/BszbRUVPRA4nHMv9+REKWfaIPTulObmFxaXysuVldW19Y3q5taNTjJFqE8Snqh2hDXlTFLfMMNpO1UUi4jTVjQ8L/zWHVWaJfLajFIaCtyXLGYEGysFgcBmEEX51fhWdKs15B4hr37sQeSiCeCX4s2UGpih2a2+Bb2EZIJKQzjWuuOh1IQ5VoYRTseVINM0xWSI+7RjqcSC6jCfZB7DPav0YJwo+6SBE/X7Ro6F1iMR2ckio/7tFeJfXicz8WmYM5lmhkoyPRRnHJoEFgXAHlOUGD6yBBPFbFZIBlhhYmxNFVvC50/h/8Q/cOsuujysNc5mbZTBDtgF+8ADJ6ABLkAT+ICAFNyDR/DkZM6D8+y8TEdLzmxnG/yA8/oB7KyR0A==</latexit>

Page 36: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Outline  of  the  rest  of  the  talk    (=  the  structure  of  our  proof)  

1.  A  useful  decomposiPon  of  polytopes  

2.  “Smooth  version”  of  the  problem  

3.   Proving  the  smooth  version  

4.  Going  from  smooth  version  to  actual  version  

Page 37: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Proving  the  smooth  version  via  a  hybrid  argument  

.  .  .      y10  y2  y6   y3  

y12   y9  y11  y4  

y7  

Ex

[ eOb(Ax)] ⇡ Ey

[ eOb(Ay)]<latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit><latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit><latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit>

Bucket-­‐wise  hybrid  argument  [MZ,  HKM]:    

§  Start  will  all  buckets  filled  in  uniformly  (i.e.  start  with  x)    

§  Bucket  by  bucket,  “swap  out”  uniform  bits  for  r-­‐wise  independent  bits  

§  Argue  that  each  swap  incurs  small  error  

.  .  .      x10  x2  x6   x3  

x12   x9  x11  x4  

x7  

Goal  is  to  “fool”  the  orthant  mollifier:    

y  pseudorandom:  x  uniform:  

r-­‐wise   r-­‐wise   r-­‐wise  uniform   uniform   uniform  

Page 38: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Single  swap  in  the  hybrid  argument  

Ex

[ eOb(ABx)] ⇡ E

y

[ eOb(ABy)]

<latexit sha1_base64="UEvCo29lKmYnEq5Ge3GLhsGT58U=">AAACl3iclVFbS+QwFE676rrjbXZlX/QlOAj6MrTiXmRfxiu+rYKjwrQ7pOmZMZg2IUlXS+hv8r/45r8xnRlBF2XxQDgf3/nOJeckkjNtguDB8z9MTc98nP3UmJtfWFxqfv5yrkWhKHSp4EJdJkQDZzl0DTMcLqUCkiUcLpLr/Tp+8ReUZiI/M6WEOCPDnA0YJcZR/eZdlBFzJaQd+SSxh1XVt1EieKrLzDl7W1W96IalYBhPYayjhNvfTphs7P7ZeynejHFEpFTiFjf+W7t8T+2yrt1vtoJ2MDL8DHwLwp3vIQ4nTAtN7KTfvI9SQYsMckM50boXBtLElijDKIeqERUaJKHXZAg9B3OSgY7taLEVXndMigdCuZcbPGKfZ1iS6Xo6p6xH1//GavK1WK8wg5+xZbksDOR03GhQcGwErq+EU6aAGl46QKhiblZMr4gi1LhbNtwSnn6K3wbdrfZOOzjdbnX2JtuYRatoDW2gEP1AHXSMTlAXUe+r98s78A79Fb/jH/nHY6nvTXKW0QvzTx8BDovQxQ==</latexit><latexit sha1_base64="UEvCo29lKmYnEq5Ge3GLhsGT58U=">AAACl3iclVFbS+QwFE676rrjbXZlX/QlOAj6MrTiXmRfxiu+rYKjwrQ7pOmZMZg2IUlXS+hv8r/45r8xnRlBF2XxQDgf3/nOJeckkjNtguDB8z9MTc98nP3UmJtfWFxqfv5yrkWhKHSp4EJdJkQDZzl0DTMcLqUCkiUcLpLr/Tp+8ReUZiI/M6WEOCPDnA0YJcZR/eZdlBFzJaQd+SSxh1XVt1EieKrLzDl7W1W96IalYBhPYayjhNvfTphs7P7ZeynejHFEpFTiFjf+W7t8T+2yrt1vtoJ2MDL8DHwLwp3vIQ4nTAtN7KTfvI9SQYsMckM50boXBtLElijDKIeqERUaJKHXZAg9B3OSgY7taLEVXndMigdCuZcbPGKfZ1iS6Xo6p6xH1//GavK1WK8wg5+xZbksDOR03GhQcGwErq+EU6aAGl46QKhiblZMr4gi1LhbNtwSnn6K3wbdrfZOOzjdbnX2JtuYRatoDW2gEP1AHXSMTlAXUe+r98s78A79Fb/jH/nHY6nvTXKW0QvzTx8BDovQxQ==</latexit><latexit sha1_base64="UEvCo29lKmYnEq5Ge3GLhsGT58U=">AAACl3iclVFbS+QwFE676rrjbXZlX/QlOAj6MrTiXmRfxiu+rYKjwrQ7pOmZMZg2IUlXS+hv8r/45r8xnRlBF2XxQDgf3/nOJeckkjNtguDB8z9MTc98nP3UmJtfWFxqfv5yrkWhKHSp4EJdJkQDZzl0DTMcLqUCkiUcLpLr/Tp+8ReUZiI/M6WEOCPDnA0YJcZR/eZdlBFzJaQd+SSxh1XVt1EieKrLzDl7W1W96IalYBhPYayjhNvfTphs7P7ZeynejHFEpFTiFjf+W7t8T+2yrt1vtoJ2MDL8DHwLwp3vIQ4nTAtN7KTfvI9SQYsMckM50boXBtLElijDKIeqERUaJKHXZAg9B3OSgY7taLEVXndMigdCuZcbPGKfZ1iS6Xo6p6xH1//GavK1WK8wg5+xZbksDOR03GhQcGwErq+EU6aAGl46QKhiblZMr4gi1LhbNtwSnn6K3wbdrfZOOzjdbnX2JtuYRatoDW2gEP1AHXSMTlAXUe+r98s78A79Fb/jH/nHY6nvTXKW0QvzTx8BDovQxQ==</latexit>

AB  m  

|B|  

B  

Ex

[ eOb(Hx+ Tx)] ⇡ Ey

[ eOb(Hy + Ty)]<latexit sha1_base64="YFcG8cc/PjqVil5VCzeWBjntlpQ=">AAACtnicjVFdS+QwFE2rrjrq7ug++hIcBEUY2sWveRNlwbdVcFZxWkqa3hmDaROSdNcS+hd98G3/zaYzs+D4gXsh5HDuuZz7kUrOtAmCP54/N7/waXFpubWyuvb5S3t946cWpaLQp4ILdZMSDZwV0DfMcLiRCkiecrhO78+a/PUvUJqJ4spUEuKcjAo2ZJQYRyXtxygn5k5IO/7T1H6v68RGqeCZrnL32Ye6HkS/WQaG8QwmOkq4/eGE6c75rBTv4atZZjfGEZFSiYfWh1bV/1tVr6yqxippd4JuMA78DBwEYe8wxOGU6aBpXCTtpygTtMyhMJQTrQdhIE1siTKMcqhbUalBEnpPRjBwsCA56NiO917jbcdkeCiUe4XBY/Z5hSW5brpzymYU/TLXkG/lBqUZHseWFbI0UNCJ0bDk2AjcHBFnTAE1vHKAUMVcr5jeEUWocaduuSX8mxS/D/rfur1ucLnfOTmdbmMJbaIttINCdIRO0Dm6QH1EvX3v1qNe5vf8xAd/NJH63rTmK5oJX/4FcL3eLg==</latexit><latexit sha1_base64="YFcG8cc/PjqVil5VCzeWBjntlpQ=">AAACtnicjVFdS+QwFE2rrjrq7ug++hIcBEUY2sWveRNlwbdVcFZxWkqa3hmDaROSdNcS+hd98G3/zaYzs+D4gXsh5HDuuZz7kUrOtAmCP54/N7/waXFpubWyuvb5S3t946cWpaLQp4ILdZMSDZwV0DfMcLiRCkiecrhO78+a/PUvUJqJ4spUEuKcjAo2ZJQYRyXtxygn5k5IO/7T1H6v68RGqeCZrnL32Ye6HkS/WQaG8QwmOkq4/eGE6c75rBTv4atZZjfGEZFSiYfWh1bV/1tVr6yqxippd4JuMA78DBwEYe8wxOGU6aBpXCTtpygTtMyhMJQTrQdhIE1siTKMcqhbUalBEnpPRjBwsCA56NiO917jbcdkeCiUe4XBY/Z5hSW5brpzymYU/TLXkG/lBqUZHseWFbI0UNCJ0bDk2AjcHBFnTAE1vHKAUMVcr5jeEUWocaduuSX8mxS/D/rfur1ucLnfOTmdbmMJbaIttINCdIRO0Dm6QH1EvX3v1qNe5vf8xAd/NJH63rTmK5oJX/4FcL3eLg==</latexit><latexit sha1_base64="YFcG8cc/PjqVil5VCzeWBjntlpQ=">AAACtnicjVFdS+QwFE2rrjrq7ug++hIcBEUY2sWveRNlwbdVcFZxWkqa3hmDaROSdNcS+hd98G3/zaYzs+D4gXsh5HDuuZz7kUrOtAmCP54/N7/waXFpubWyuvb5S3t946cWpaLQp4ILdZMSDZwV0DfMcLiRCkiecrhO78+a/PUvUJqJ4spUEuKcjAo2ZJQYRyXtxygn5k5IO/7T1H6v68RGqeCZrnL32Ye6HkS/WQaG8QwmOkq4/eGE6c75rBTv4atZZjfGEZFSiYfWh1bV/1tVr6yqxippd4JuMA78DBwEYe8wxOGU6aBpXCTtpygTtMyhMJQTrQdhIE1siTKMcqhbUalBEnpPRjBwsCA56NiO917jbcdkeCiUe4XBY/Z5hSW5brpzymYU/TLXkG/lBqUZHseWFbI0UNCJ0bDk2AjcHBFnTAE1vHKAUMVcr5jeEUWocaduuSX8mxS/D/rfur1ucLnfOTmdbmMJbaIttINCdIRO0Dm6QH1EvX3v1qNe5vf8xAd/NJH63rTmK5oJX/4FcL3eLg==</latexit>

Write  AB  =  H  +  T,  where:    

§  H  contains  only  the  head  variables  §  T  contains  only  the  tail  variables  

()<latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit><latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit><latexit sha1_base64="kk6CTAFESn4xIuVViVil2pS3V7g=">AAAB+3icdVDLSgNBEJyNrxhf0Ry9DAbBU9gVX7kFvXjwEME1gWQJs5PZZMjszDLTq4Ql/ooXDype/RFv/o2ThxBFCxqKqm66u8JEcAOu++nkFhaXllfyq4W19Y3NreL2zq1RqabMp0oo3QyJYYJL5gMHwZqJZiQOBWuEg4ux37hj2nAlb2CYsCAmPckjTglYqVMsta+U7AkWgea9PhCt1X2nWHYr7gR4jhy7XvXEw95MKaMZ6p3iR7uraBozCVQQY1qem0CQEQ2cCjYqtFPDEkIHpMdalkoSMxNkk+NHeN8qXRwpbUsCnqjzExmJjRnGoe2MCfTNb28s/uW1UojOgozLJAUm6XRRlAoMCo+TwF2uGQUxtIRQze2tmPaJJhRsXgUbwven+H/iH1aqFff6qFw7n6WRR7toDx0gD52iGrpEdeQjioboET2jF+fBeXJenbdpa86ZzZTQDzjvX/wvlTI=</latexit>

Fix  bucket  B          [n]  of  variables.    Let  AB  =  A  restricted  to  columns  in  B.  ✓<latexit sha1_base64="PnZf/mQVWYP7yPcejOC6GMtajH4=">AAAB/nicdVDLSgMxFM3UV62vUcGNm2ARXJUZ8dVd0Y3LCo4tdIaSydxpQzMPk4xQxi78FTcuVNz6He78GzNthSp6IORwzr3k5PgpZ1JZ1qdRmptfWFwqL1dWVtfWN8zNrRuZZIKCQxOeiLZPJHAWg6OY4tBOBZDI59DyBxeF37oDIVkSX6thCl5EejELGSVKS11zx/UTHshhpK/clZkvQcHtqGtWrZo1Bp4hx5ZdP7GxPVWqaIpm1/xwg4RmEcSKciJlx7ZS5eVEKEY5jCpuJiEldEB60NE0JhFILx/nH+F9rQQ4TIQ+scJjdXYjJ5EsIurJiKi+/O0V4l9eJ1PhmZezOM0UxHTyUJhxrBJclIEDJoAqPtSEUMF0Vkz7RBCqdGUVXcL3T/H/xDms1WvW1VG1cT5to4x20R46QDY6RQ10iZrIQRTdo0f0jF6MB+PJeDXeJqMlY7qzjX7AeP8CuE6Www==</latexit><latexit sha1_base64="PnZf/mQVWYP7yPcejOC6GMtajH4=">AAAB/nicdVDLSgMxFM3UV62vUcGNm2ARXJUZ8dVd0Y3LCo4tdIaSydxpQzMPk4xQxi78FTcuVNz6He78GzNthSp6IORwzr3k5PgpZ1JZ1qdRmptfWFwqL1dWVtfWN8zNrRuZZIKCQxOeiLZPJHAWg6OY4tBOBZDI59DyBxeF37oDIVkSX6thCl5EejELGSVKS11zx/UTHshhpK/clZkvQcHtqGtWrZo1Bp4hx5ZdP7GxPVWqaIpm1/xwg4RmEcSKciJlx7ZS5eVEKEY5jCpuJiEldEB60NE0JhFILx/nH+F9rQQ4TIQ+scJjdXYjJ5EsIurJiKi+/O0V4l9eJ1PhmZezOM0UxHTyUJhxrBJclIEDJoAqPtSEUMF0Vkz7RBCqdGUVXcL3T/H/xDms1WvW1VG1cT5to4x20R46QDY6RQ10iZrIQRTdo0f0jF6MB+PJeDXeJqMlY7qzjX7AeP8CuE6Www==</latexit><latexit sha1_base64="PnZf/mQVWYP7yPcejOC6GMtajH4=">AAAB/nicdVDLSgMxFM3UV62vUcGNm2ARXJUZ8dVd0Y3LCo4tdIaSydxpQzMPk4xQxi78FTcuVNz6He78GzNthSp6IORwzr3k5PgpZ1JZ1qdRmptfWFwqL1dWVtfWN8zNrRuZZIKCQxOeiLZPJHAWg6OY4tBOBZDI59DyBxeF37oDIVkSX6thCl5EejELGSVKS11zx/UTHshhpK/clZkvQcHtqGtWrZo1Bp4hx5ZdP7GxPVWqaIpm1/xwg4RmEcSKciJlx7ZS5eVEKEY5jCpuJiEldEB60NE0JhFILx/nH+F9rQQ4TIQ+scJjdXYjJ5EsIurJiKi+/O0V4l9eJ1PhmZezOM0UxHTyUJhxrBJclIEDJoAqPtSEUMF0Vkz7RBCqdGUVXcL3T/H/xDms1WvW1VG1cT5to4x20R46QDY6RQ10iZrIQRTdo0f0jF6MB+PJeDXeJqMlY7qzjX7AeP8CuE6Www==</latexit>

CLTs  (e.g.  [HKM])  deal  with  regular  linear  forms;  Presence  of  H  =  our  main  challenge  

Want  to  show:  

Part  I  

Page 39: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Ex

[ eOb(Hx+ Tx)] ⇡ Ey

[ eOb(Hy + Ty)]<latexit sha1_base64="YFcG8cc/PjqVil5VCzeWBjntlpQ=">AAACtnicjVFdS+QwFE2rrjrq7ug++hIcBEUY2sWveRNlwbdVcFZxWkqa3hmDaROSdNcS+hd98G3/zaYzs+D4gXsh5HDuuZz7kUrOtAmCP54/N7/waXFpubWyuvb5S3t946cWpaLQp4ILdZMSDZwV0DfMcLiRCkiecrhO78+a/PUvUJqJ4spUEuKcjAo2ZJQYRyXtxygn5k5IO/7T1H6v68RGqeCZrnL32Ye6HkS/WQaG8QwmOkq4/eGE6c75rBTv4atZZjfGEZFSiYfWh1bV/1tVr6yqxippd4JuMA78DBwEYe8wxOGU6aBpXCTtpygTtMyhMJQTrQdhIE1siTKMcqhbUalBEnpPRjBwsCA56NiO917jbcdkeCiUe4XBY/Z5hSW5brpzymYU/TLXkG/lBqUZHseWFbI0UNCJ0bDk2AjcHBFnTAE1vHKAUMVcr5jeEUWocaduuSX8mxS/D/rfur1ucLnfOTmdbmMJbaIttINCdIRO0Dm6QH1EvX3v1qNe5vf8xAd/NJH63rTmK5oJX/4FcL3eLg==</latexit><latexit sha1_base64="YFcG8cc/PjqVil5VCzeWBjntlpQ=">AAACtnicjVFdS+QwFE2rrjrq7ug++hIcBEUY2sWveRNlwbdVcFZxWkqa3hmDaROSdNcS+hd98G3/zaYzs+D4gXsh5HDuuZz7kUrOtAmCP54/N7/waXFpubWyuvb5S3t946cWpaLQp4ILdZMSDZwV0DfMcLiRCkiecrhO78+a/PUvUJqJ4spUEuKcjAo2ZJQYRyXtxygn5k5IO/7T1H6v68RGqeCZrnL32Ye6HkS/WQaG8QwmOkq4/eGE6c75rBTv4atZZjfGEZFSiYfWh1bV/1tVr6yqxippd4JuMA78DBwEYe8wxOGU6aBpXCTtpygTtMyhMJQTrQdhIE1siTKMcqhbUalBEnpPRjBwsCA56NiO917jbcdkeCiUe4XBY/Z5hSW5brpzymYU/TLXkG/lBqUZHseWFbI0UNCJ0bDk2AjcHBFnTAE1vHKAUMVcr5jeEUWocaduuSX8mxS/D/rfur1ucLnfOTmdbmMJbaIttINCdIRO0Dm6QH1EvX3v1qNe5vf8xAd/NJH63rTmK5oJX/4FcL3eLg==</latexit><latexit sha1_base64="YFcG8cc/PjqVil5VCzeWBjntlpQ=">AAACtnicjVFdS+QwFE2rrjrq7ug++hIcBEUY2sWveRNlwbdVcFZxWkqa3hmDaROSdNcS+hd98G3/zaYzs+D4gXsh5HDuuZz7kUrOtAmCP54/N7/waXFpubWyuvb5S3t946cWpaLQp4ILdZMSDZwV0DfMcLiRCkiecrhO78+a/PUvUJqJ4spUEuKcjAo2ZJQYRyXtxygn5k5IO/7T1H6v68RGqeCZrnL32Ye6HkS/WQaG8QwmOkq4/eGE6c75rBTv4atZZjfGEZFSiYfWh1bV/1tVr6yqxippd4JuMA78DBwEYe8wxOGU6aBpXCTtpygTtMyhMJQTrQdhIE1siTKMcqhbUalBEnpPRjBwsCA56NiO917jbcdkeCiUe4XBY/Z5hSW5brpzymYU/TLXkG/lBqUZHseWFbI0UNCJ0bDk2AjcHBFnTAE1vHKAUMVcr5jeEUWocaduuSX8mxS/D/rfur1ucLnfOTmdbmMJbaIttINCdIRO0Dm6QH1EvX3v1qNe5vf8xAd/NJH63rTmK5oJX/4FcL3eLg==</latexit>

H  

T  

Entries  are  small  

Rows  are  sparse  

Equivalently,  y  fools  the  funcPon    z 7! eOb(Hz + Tz)<latexit sha1_base64="0n//+HXi/Bo3CnKHqeLmLSzZu7s=">AAACFHicdZDLSgMxFIYz9VbrrerSTbAIFaXMiLfuim66s0JrC20pmcxpG5q5kGSUduhLuPFV3LhQcevCnW9jph2hiv4Q+PnOOeSc3w44k8o0P43U3PzC4lJ6ObOyura+kd3cupF+KCjUqM990bCJBM48qCmmODQCAcS1OdTtwWVcr9+CkMz3qmoYQNslPY91GSVKo072cIRbLgmk8nHrjjmgGHcg0kj1KeHR1XjcsfPlET7A1dF+J5szC+ZEeMacmFbx1MJWQnIoUaWT/Wg5Pg1d8BTlRMqmZQaqHRGhGOUwzrRCCQGhA9KDprYecUG2o8lVY7yniYO7vtDPU3hCZyci4ko5dG3dGa8rf9di+FetGarueTtiXhAq8Oj0o27Isc4gjgg7TABVfKgNoYLpXTHtE0Go0kFmdAjfl+L/Te2oUCyY18e50kWSRhrtoF2URxY6QyVURhVUQxTdo0f0jF6MB+PJeDXepq0pI5nZRj9kvH8Bd4Wejw==</latexit><latexit sha1_base64="0n//+HXi/Bo3CnKHqeLmLSzZu7s=">AAACFHicdZDLSgMxFIYz9VbrrerSTbAIFaXMiLfuim66s0JrC20pmcxpG5q5kGSUduhLuPFV3LhQcevCnW9jph2hiv4Q+PnOOeSc3w44k8o0P43U3PzC4lJ6ObOyura+kd3cupF+KCjUqM990bCJBM48qCmmODQCAcS1OdTtwWVcr9+CkMz3qmoYQNslPY91GSVKo072cIRbLgmk8nHrjjmgGHcg0kj1KeHR1XjcsfPlET7A1dF+J5szC+ZEeMacmFbx1MJWQnIoUaWT/Wg5Pg1d8BTlRMqmZQaqHRGhGOUwzrRCCQGhA9KDprYecUG2o8lVY7yniYO7vtDPU3hCZyci4ko5dG3dGa8rf9di+FetGarueTtiXhAq8Oj0o27Isc4gjgg7TABVfKgNoYLpXTHtE0Go0kFmdAjfl+L/Te2oUCyY18e50kWSRhrtoF2URxY6QyVURhVUQxTdo0f0jF6MB+PJeDXepq0pI5nZRj9kvH8Bd4Wejw==</latexit><latexit sha1_base64="0n//+HXi/Bo3CnKHqeLmLSzZu7s=">AAACFHicdZDLSgMxFIYz9VbrrerSTbAIFaXMiLfuim66s0JrC20pmcxpG5q5kGSUduhLuPFV3LhQcevCnW9jph2hiv4Q+PnOOeSc3w44k8o0P43U3PzC4lJ6ObOyura+kd3cupF+KCjUqM990bCJBM48qCmmODQCAcS1OdTtwWVcr9+CkMz3qmoYQNslPY91GSVKo072cIRbLgmk8nHrjjmgGHcg0kj1KeHR1XjcsfPlET7A1dF+J5szC+ZEeMacmFbx1MJWQnIoUaWT/Wg5Pg1d8BTlRMqmZQaqHRGhGOUwzrRCCQGhA9KDprYecUG2o8lVY7yniYO7vtDPU3hCZyci4ko5dG3dGa8rf9di+FetGarueTtiXhAq8Oj0o27Isc4gjgg7TABVfKgNoYLpXTHtE0Go0kFmdAjfl+L/Te2oUCyY18e50kWSRhrtoF2URxY6QyVURhVUQxTdo0f0jF6MB+PJeDXepq0pI5nZRj9kvH8Bd4Wejw==</latexit>

MulPdimensional  Taylor  expansion  

Claim:  

MulPdimensional  Taylor  expansion:  

Ex

[ eOb(Hx)] ⇡ Ey

[ eOb(Hy)]<latexit sha1_base64="euzEJ3J5IC5AHo6nZnRXp9WDm0c=">AAACknicjVFba9swFJbdXbKsF69jT3sRC4P0Jdhj7Vb60Gxl0IfBOljWQGyCLJ8kIrIlJLmNEf5D+zl727+ZnGSQlI3ugDgf3/nOReekkjNtwvCX5+88ePjocetJ++nu3v5B8OzwuxalojCgggs1TIkGzgoYGGY4DKUCkqccrtP5RRO/vgGlmSi+mUpCkpNpwSaMEuOocfAjzomZCWmXPk3tp7oe2zgVPNNV7pxd1PUovmUZGMYzWOko4faLE6bdy23pUYJjIqUSi/a9hav/L1w1hcdBJ+yFS8Mb4DiMTk8iHK2ZDlrb1Tj4GWeCljkUhnKi9SgKpUksUYZRDnU7LjVIQudkCiMHC5KDTuxypzV+7ZgMT4RyrzB4yW5mWJLrZjqnbAbXd2MN+bfYqDST94llhSwNFHTVaFJybARuDoQzpoAaXjlAqGJuVkxnRBFq3Bnbbgl/for/DQZveqe98OvbTv/jehst9BK9Ql0UoXeojy7RFRog6gXeiXfu9f0X/pn/wb9YSX1vnfMcbZn/+Tcj5s9B</latexit><latexit sha1_base64="euzEJ3J5IC5AHo6nZnRXp9WDm0c=">AAACknicjVFba9swFJbdXbKsF69jT3sRC4P0Jdhj7Vb60Gxl0IfBOljWQGyCLJ8kIrIlJLmNEf5D+zl727+ZnGSQlI3ugDgf3/nOReekkjNtwvCX5+88ePjocetJ++nu3v5B8OzwuxalojCgggs1TIkGzgoYGGY4DKUCkqccrtP5RRO/vgGlmSi+mUpCkpNpwSaMEuOocfAjzomZCWmXPk3tp7oe2zgVPNNV7pxd1PUovmUZGMYzWOko4faLE6bdy23pUYJjIqUSi/a9hav/L1w1hcdBJ+yFS8Mb4DiMTk8iHK2ZDlrb1Tj4GWeCljkUhnKi9SgKpUksUYZRDnU7LjVIQudkCiMHC5KDTuxypzV+7ZgMT4RyrzB4yW5mWJLrZjqnbAbXd2MN+bfYqDST94llhSwNFHTVaFJybARuDoQzpoAaXjlAqGJuVkxnRBFq3Bnbbgl/for/DQZveqe98OvbTv/jehst9BK9Ql0UoXeojy7RFRog6gXeiXfu9f0X/pn/wb9YSX1vnfMcbZn/+Tcj5s9B</latexit><latexit sha1_base64="euzEJ3J5IC5AHo6nZnRXp9WDm0c=">AAACknicjVFba9swFJbdXbKsF69jT3sRC4P0Jdhj7Vb60Gxl0IfBOljWQGyCLJ8kIrIlJLmNEf5D+zl727+ZnGSQlI3ugDgf3/nOReekkjNtwvCX5+88ePjocetJ++nu3v5B8OzwuxalojCgggs1TIkGzgoYGGY4DKUCkqccrtP5RRO/vgGlmSi+mUpCkpNpwSaMEuOocfAjzomZCWmXPk3tp7oe2zgVPNNV7pxd1PUovmUZGMYzWOko4faLE6bdy23pUYJjIqUSi/a9hav/L1w1hcdBJ+yFS8Mb4DiMTk8iHK2ZDlrb1Tj4GWeCljkUhnKi9SgKpUksUYZRDnU7LjVIQudkCiMHC5KDTuxypzV+7ZgMT4RyrzB4yW5mWJLrZjqnbAbXd2MN+bfYqDST94llhSwNFHTVaFJybARuDoQzpoAaXjlAqGJuVkxnRBFq3Bnbbgl/for/DQZveqe98OvbTv/jehst9BK9Ql0UoXeojy7RFRog6gXeiXfu9f0X/pn/wb9YSX1vnfMcbZn/+Tcj5s9B</latexit>

Warmup:  Does  y  fool  the  zeroth-­‐order  term?    

eOb(Hz) +c�1X

|↵|=1

1

↵!@↵ eOb(Hz)(Tz)↵ ± err

<latexit sha1_base64="Qxt43DEEU0RDEFP5g9dIKBViTYg=">AAACfXicfVFNT9wwEHXSL7r92pZjL4ZVq6W0q6TioxyQEL1wg0psQdos0cSZsBZ2EtkOaDH5Gf1j3PgtXHB2g0SrtiNZen7zZjx+k5SCaxMEN57/6PGTp88WnndevHz1+k337bufuqgUwyErRKGOE9AoeI5Dw43A41IhyETgUXL2vckfnaPSvMgPzbTEsYTTnGecgXFU3P0VXfAUDRcp2kiCmTAQdr+u46S/d7lCV2mkKxnbqwhEOYGr7bA+sexLWNMoU8BCO+eX3L0EZTiIuKXq/zfuH16unNxLXbGkM5GSFpWq424vGASzoA/AehBubYQ0bJkeaeMg7l5HacEqiblhArQehUFpxrYZiQmsO1GlsQR2Bqc4cjAHiXpsZ/bV9INjUpoVyp3c0Bn7sMKC1HoqE6dsZtR/5hryb7lRZbJvY8vzsjKYs/lDWSWoKWizC5pyhcyIqQPAFHezUjYB56txG+s4E+5/Sv8Nhl8HW4Pgx1pvZ7d1Y4G8J8ukT0KySXbIHjkgQ8LIrbfkffJWfeJ/9D/7g7nU99qaRfJb+Jt3stHC/A==</latexit><latexit sha1_base64="Qxt43DEEU0RDEFP5g9dIKBViTYg=">AAACfXicfVFNT9wwEHXSL7r92pZjL4ZVq6W0q6TioxyQEL1wg0psQdos0cSZsBZ2EtkOaDH5Gf1j3PgtXHB2g0SrtiNZen7zZjx+k5SCaxMEN57/6PGTp88WnndevHz1+k337bufuqgUwyErRKGOE9AoeI5Dw43A41IhyETgUXL2vckfnaPSvMgPzbTEsYTTnGecgXFU3P0VXfAUDRcp2kiCmTAQdr+u46S/d7lCV2mkKxnbqwhEOYGr7bA+sexLWNMoU8BCO+eX3L0EZTiIuKXq/zfuH16unNxLXbGkM5GSFpWq424vGASzoA/AehBubYQ0bJkeaeMg7l5HacEqiblhArQehUFpxrYZiQmsO1GlsQR2Bqc4cjAHiXpsZ/bV9INjUpoVyp3c0Bn7sMKC1HoqE6dsZtR/5hryb7lRZbJvY8vzsjKYs/lDWSWoKWizC5pyhcyIqQPAFHezUjYB56txG+s4E+5/Sv8Nhl8HW4Pgx1pvZ7d1Y4G8J8ukT0KySXbIHjkgQ8LIrbfkffJWfeJ/9D/7g7nU99qaRfJb+Jt3stHC/A==</latexit><latexit sha1_base64="Qxt43DEEU0RDEFP5g9dIKBViTYg=">AAACfXicfVFNT9wwEHXSL7r92pZjL4ZVq6W0q6TioxyQEL1wg0psQdos0cSZsBZ2EtkOaDH5Gf1j3PgtXHB2g0SrtiNZen7zZjx+k5SCaxMEN57/6PGTp88WnndevHz1+k337bufuqgUwyErRKGOE9AoeI5Dw43A41IhyETgUXL2vckfnaPSvMgPzbTEsYTTnGecgXFU3P0VXfAUDRcp2kiCmTAQdr+u46S/d7lCV2mkKxnbqwhEOYGr7bA+sexLWNMoU8BCO+eX3L0EZTiIuKXq/zfuH16unNxLXbGkM5GSFpWq424vGASzoA/AehBubYQ0bJkeaeMg7l5HacEqiblhArQehUFpxrYZiQmsO1GlsQR2Bqc4cjAHiXpsZ/bV9INjUpoVyp3c0Bn7sMKC1HoqE6dsZtR/5hryb7lRZbJvY8vzsjKYs/lDWSWoKWizC5pyhcyIqQPAFHezUjYB56txG+s4E+5/Sv8Nhl8HW4Pgx1pvZ7d1Y4G8J8ukT0KySXbIHjkgQ8LIrbfkffJWfeJ/9D/7g7nU99qaRfJb+Jt3stHC/A==</latexit>

(ObservaPon:  trivial  when  H  =  0)  

Page 40: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Warmup:  fooling  the  zeroth-­‐order  term  

z 7! eOb(Hz)<latexit sha1_base64="V4hk7arfP2G575E6TklSSEaHqVM=">AAACD3icdVC7SgNBFJ2Nrxhfq5Y2g0GMTdgVX+mCNumM4JpANoTZ2ZtkyOyDmVklWfIJNv6KjYWKra2df+PkIUTRAwOHc+5l7jlezJlUlvVpZObmFxaXssu5ldW19Q1zc+tGRomg4NCIR6LuEQmcheAopjjUYwEk8DjUvN7FyK/dgpAsCq9VP4ZmQDohazNKlJZa5v4AuwGJpYqwe8d8UIz7kGpJdSnh6eVw2PIKlcFBy8xbRWsMPEOOLbt0YmN7quTRFNWW+eH6EU0CCBXlRMqGbcWqmRKhGOUwzLmJhJjQHulAQ9OQBCCb6TjQEO9pxcftSOgXKjxWZzdSEkjZDzw9ObpU/vZG4l9eI1Hts2bKwjhRENLJR+2EYx1/1A72mQCqeF8TQgXTt2LaJYJQpTvM6RK+k+L/iXNYLBWtq6N8+XzaRhbtoF1UQDY6RWVUQVXkIIru0SN6Ri/Gg/FkvBpvk9GMMd3ZRj9gvH8BlmCdJA==</latexit><latexit sha1_base64="V4hk7arfP2G575E6TklSSEaHqVM=">AAACD3icdVC7SgNBFJ2Nrxhfq5Y2g0GMTdgVX+mCNumM4JpANoTZ2ZtkyOyDmVklWfIJNv6KjYWKra2df+PkIUTRAwOHc+5l7jlezJlUlvVpZObmFxaXssu5ldW19Q1zc+tGRomg4NCIR6LuEQmcheAopjjUYwEk8DjUvN7FyK/dgpAsCq9VP4ZmQDohazNKlJZa5v4AuwGJpYqwe8d8UIz7kGpJdSnh6eVw2PIKlcFBy8xbRWsMPEOOLbt0YmN7quTRFNWW+eH6EU0CCBXlRMqGbcWqmRKhGOUwzLmJhJjQHulAQ9OQBCCb6TjQEO9pxcftSOgXKjxWZzdSEkjZDzw9ObpU/vZG4l9eI1Hts2bKwjhRENLJR+2EYx1/1A72mQCqeF8TQgXTt2LaJYJQpTvM6RK+k+L/iXNYLBWtq6N8+XzaRhbtoF1UQDY6RWVUQVXkIIru0SN6Ri/Gg/FkvBpvk9GMMd3ZRj9gvH8BlmCdJA==</latexit><latexit sha1_base64="V4hk7arfP2G575E6TklSSEaHqVM=">AAACD3icdVC7SgNBFJ2Nrxhfq5Y2g0GMTdgVX+mCNumM4JpANoTZ2ZtkyOyDmVklWfIJNv6KjYWKra2df+PkIUTRAwOHc+5l7jlezJlUlvVpZObmFxaXssu5ldW19Q1zc+tGRomg4NCIR6LuEQmcheAopjjUYwEk8DjUvN7FyK/dgpAsCq9VP4ZmQDohazNKlJZa5v4AuwGJpYqwe8d8UIz7kGpJdSnh6eVw2PIKlcFBy8xbRWsMPEOOLbt0YmN7quTRFNWW+eH6EU0CCBXlRMqGbcWqmRKhGOUwzLmJhJjQHulAQ9OQBCCb6TjQEO9pxcftSOgXKjxWZzdSEkjZDzw9ObpU/vZG4l9eI1Hts2bKwjhRENLJR+2EYx1/1A72mQCqeF8TQgXTt2LaJYJQpTvM6RK+k+L/iXNYLBWtq6N8+XzaRhbtoF1UQDY6RWVUQVXkIIru0SN6Ri/Gg/FkvBpvk9GMMd3ZRj9gvH8BlmCdJA==</latexit>

y  fools  the  funcPon    

H  

Rows  are  sparse  eOb(Hz) = EG[Ob(Hz + �G)]

<latexit sha1_base64="IfLLKbahMtFEiozzS9VzjU4sLVk=">AAACXHicdVHRahQxFM2MrrZba7cKffEluChbhGVGtNqHQqmIfbOCaws7w5Bk7u6GZiZDckfZhvlJ39qX/kozuytsRS+EHM65h9x7wislLUbRdRA+eNh59Hhjs7v1ZPvpTm/32Q+rayNgJLTS5oIzC0qWMEKJCi4qA6zgCs755adWP/8Jxkpdfsd5BWnBpqWcSMHQU1kPk18yB5QqB5cUDGeCKfe1aTLHm8Hp1T59fUQXvK6WOufucysnXKvczgt/uS9NM14zZ9w76RuaKD9Hzuj91v2UZr1+NIwWRdfA+yg+PIhpvGL6ZFVnWe93kmtRF1CiUMzacRxVmDpmUAoFTTepLVRMXLIpjD0sWQE2dYt0GvrKMzmdaONPiXTBrjscK2w7ne9sd7B/ay35L21c4+Rj6mRZ1QilWD40qRVFTduoaS4NCFRzD5gw0s9KxYwZJtB/SNeH8GdT+n8wejs8HEbf3vWPT1ZpbJAX5CUZkJh8IMfklJyRERHkJiDBZtANbsNOuBVuL1vDYOV5Tu5VuHcHOGS2bg==</latexit><latexit sha1_base64="IfLLKbahMtFEiozzS9VzjU4sLVk=">AAACXHicdVHRahQxFM2MrrZba7cKffEluChbhGVGtNqHQqmIfbOCaws7w5Bk7u6GZiZDckfZhvlJ39qX/kozuytsRS+EHM65h9x7wislLUbRdRA+eNh59Hhjs7v1ZPvpTm/32Q+rayNgJLTS5oIzC0qWMEKJCi4qA6zgCs755adWP/8Jxkpdfsd5BWnBpqWcSMHQU1kPk18yB5QqB5cUDGeCKfe1aTLHm8Hp1T59fUQXvK6WOufucysnXKvczgt/uS9NM14zZ9w76RuaKD9Hzuj91v2UZr1+NIwWRdfA+yg+PIhpvGL6ZFVnWe93kmtRF1CiUMzacRxVmDpmUAoFTTepLVRMXLIpjD0sWQE2dYt0GvrKMzmdaONPiXTBrjscK2w7ne9sd7B/ay35L21c4+Rj6mRZ1QilWD40qRVFTduoaS4NCFRzD5gw0s9KxYwZJtB/SNeH8GdT+n8wejs8HEbf3vWPT1ZpbJAX5CUZkJh8IMfklJyRERHkJiDBZtANbsNOuBVuL1vDYOV5Tu5VuHcHOGS2bg==</latexit><latexit sha1_base64="IfLLKbahMtFEiozzS9VzjU4sLVk=">AAACXHicdVHRahQxFM2MrrZba7cKffEluChbhGVGtNqHQqmIfbOCaws7w5Bk7u6GZiZDckfZhvlJ39qX/kozuytsRS+EHM65h9x7wislLUbRdRA+eNh59Hhjs7v1ZPvpTm/32Q+rayNgJLTS5oIzC0qWMEKJCi4qA6zgCs755adWP/8Jxkpdfsd5BWnBpqWcSMHQU1kPk18yB5QqB5cUDGeCKfe1aTLHm8Hp1T59fUQXvK6WOufucysnXKvczgt/uS9NM14zZ9w76RuaKD9Hzuj91v2UZr1+NIwWRdfA+yg+PIhpvGL6ZFVnWe93kmtRF1CiUMzacRxVmDpmUAoFTTepLVRMXLIpjD0sWQE2dYt0GvrKMzmdaONPiXTBrjscK2w7ne9sd7B/ay35L21c4+Rj6mRZ1QilWD40qRVFTduoaS4NCFRzD5gw0s9KxYwZJtB/SNeH8GdT+n8wejs8HEbf3vWPT1ZpbJAX5CUZkJh8IMfklJyRERHkJiDBZtANbsNOuBVuL1vDYOV5Tu5VuHcHOGS2bg==</latexit>

Recalling  the  definiPon  of  Õb  ,  

⌘mY

i=1

1[(Hz + �G)i bi]<latexit sha1_base64="19D6xTg8+8M8Kqu0yhWXNIQMdRk=">AAACMnicdVDLSgMxFM3Ud31VXboJFkERyoz4XAiiC8WVgtVCZxwymds2NDMZk4xQh/knN/6IC0FcqLj1I0xrhSp6IORwzr3JvSdIOFPatp+swtDwyOjY+ERxcmp6ZrY0N3+hRCopVKngQtYCooCzGKqaaQ61RAKJAg6XQfuw61/egFRMxOe6k4AXkWbMGowSbSS/dOLCdcpusJtIEfoZ23Pyqwi7geCh6kTmypy8vnJ8u+Zy82hIBp2jfNVn2OWAA5952C+V7YrdAx4gm7azu+Vgp6+UUR+nfunBDQVNI4g15USpumMn2suI1IxyyItuqiAhtE2aUDc0JhEoL+vtnONlo4S4IaQ5scY9dbAjI5HqzmkqI6Jb6rfXFf/y6qlu7HgZi5NUQ0y/PmqkHGuBuwHikEmgmncMIVQyMyumLSIJ1Sbmognhe1P8P6muV3Yr9tlGef+gn8Y4WkRLaAU5aBvto2N0iqqIojv0iF7Qq3VvPVtv1vtXacHq9yygH7A+PgGHXqsI</latexit><latexit sha1_base64="19D6xTg8+8M8Kqu0yhWXNIQMdRk=">AAACMnicdVDLSgMxFM3Ud31VXboJFkERyoz4XAiiC8WVgtVCZxwymds2NDMZk4xQh/knN/6IC0FcqLj1I0xrhSp6IORwzr3JvSdIOFPatp+swtDwyOjY+ERxcmp6ZrY0N3+hRCopVKngQtYCooCzGKqaaQ61RAKJAg6XQfuw61/egFRMxOe6k4AXkWbMGowSbSS/dOLCdcpusJtIEfoZ23Pyqwi7geCh6kTmypy8vnJ8u+Zy82hIBp2jfNVn2OWAA5952C+V7YrdAx4gm7azu+Vgp6+UUR+nfunBDQVNI4g15USpumMn2suI1IxyyItuqiAhtE2aUDc0JhEoL+vtnONlo4S4IaQ5scY9dbAjI5HqzmkqI6Jb6rfXFf/y6qlu7HgZi5NUQ0y/PmqkHGuBuwHikEmgmncMIVQyMyumLSIJ1Sbmognhe1P8P6muV3Yr9tlGef+gn8Y4WkRLaAU5aBvto2N0iqqIojv0iF7Qq3VvPVtv1vtXacHq9yygH7A+PgGHXqsI</latexit><latexit sha1_base64="19D6xTg8+8M8Kqu0yhWXNIQMdRk=">AAACMnicdVDLSgMxFM3Ud31VXboJFkERyoz4XAiiC8WVgtVCZxwymds2NDMZk4xQh/knN/6IC0FcqLj1I0xrhSp6IORwzr3JvSdIOFPatp+swtDwyOjY+ERxcmp6ZrY0N3+hRCopVKngQtYCooCzGKqaaQ61RAKJAg6XQfuw61/egFRMxOe6k4AXkWbMGowSbSS/dOLCdcpusJtIEfoZ23Pyqwi7geCh6kTmypy8vnJ8u+Zy82hIBp2jfNVn2OWAA5952C+V7YrdAx4gm7azu+Vgp6+UUR+nfunBDQVNI4g15USpumMn2suI1IxyyItuqiAhtE2aUDc0JhEoL+vtnONlo4S4IaQ5scY9dbAjI5HqzmkqI6Jb6rfXFf/y6qlu7HgZi5NUQ0y/PmqkHGuBuwHikEmgmncMIVQyMyumLSIJ1Sbmognhe1P8P6muV3Yr9tlGef+gn8Y4WkRLaAU5aBvto2N0iqqIojv0iF7Qq3VvPVtv1vtXacHq9yygH7A+PgGHXqsI</latexit>

Product  structure  of  Õb  +  Sparsity  of  H  

Suffices  for  y  to  fool  small-­‐width  CNFs  

   

Claim:  

)<latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit><latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit><latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit>

b  

Orthant  Ob  

Simple  but  key  idea:  product  of  k-­‐juntas  =  width-­‐k  CNF    

Page 41: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Back  to  the  Taylor  expansion  

More  complicated,  but  same  key  ideas:    

§  Product  structure  of    §  Sparsity  of  H    

sup

v2Rm

(X

|↵|=c

|@↵ eOb(v)|)

. (logm)

c/2

�c

<latexit sha1_base64="zcnErT6IswuVo5XUaOgLms06khg=">AAACe3icdVHLjtMwFHXCayivAksWWBSkFqGSjBhgFkijYcOOAVFmpLqNbhwntcZ2rNgpqlx/BX/Gjk9hg3DaIg0IjmTp6NyH7z0314IbmyTfo/jS5StXr+1d7924eev2nf7de59N3TaUTWgt6uYsB8MEV2xiuRXsTDcMZC7YaX7+toufLlljeK0+2ZVmMwmV4iWnYIOU9b8S0+rMLTHhChMJdpHn7qOfS0+OeVURh0OCzNyagNALWL+hfk00NJaDyNxW9OQLL5jlomBu04KCcO+9z/LhcrTe9vEYE8GMMVxiUjZA3ZCIusJyNHf0+b73jogwdQFz6rP+IBknG+AL5CBJD1+mON0pA7TDSdb/RoqatpIpSwUYM00TbWeum5IK5nukNUwDPYeKTQNVIJmZuY15Hj8JSoHLuglPWbxRL1Y4kMasZB4yu93M37FO/Fds2try9cxxpVvLFN1+VLYC2xp3l8AFbxi1YhUI0IaHWTFdQLDGhnv1ggm/N8X/J5P98eE4+fBicHS8c2MPPUCP0BCl6BU6Qu/QCZogin5ED6NhNIp+xo/jp/GzbWoc7Wruoz8QH/wChofEbg==</latexit><latexit sha1_base64="zcnErT6IswuVo5XUaOgLms06khg=">AAACe3icdVHLjtMwFHXCayivAksWWBSkFqGSjBhgFkijYcOOAVFmpLqNbhwntcZ2rNgpqlx/BX/Gjk9hg3DaIg0IjmTp6NyH7z0314IbmyTfo/jS5StXr+1d7924eev2nf7de59N3TaUTWgt6uYsB8MEV2xiuRXsTDcMZC7YaX7+toufLlljeK0+2ZVmMwmV4iWnYIOU9b8S0+rMLTHhChMJdpHn7qOfS0+OeVURh0OCzNyagNALWL+hfk00NJaDyNxW9OQLL5jlomBu04KCcO+9z/LhcrTe9vEYE8GMMVxiUjZA3ZCIusJyNHf0+b73jogwdQFz6rP+IBknG+AL5CBJD1+mON0pA7TDSdb/RoqatpIpSwUYM00TbWeum5IK5nukNUwDPYeKTQNVIJmZuY15Hj8JSoHLuglPWbxRL1Y4kMasZB4yu93M37FO/Fds2try9cxxpVvLFN1+VLYC2xp3l8AFbxi1YhUI0IaHWTFdQLDGhnv1ggm/N8X/J5P98eE4+fBicHS8c2MPPUCP0BCl6BU6Qu/QCZogin5ED6NhNIp+xo/jp/GzbWoc7Wruoz8QH/wChofEbg==</latexit><latexit sha1_base64="zcnErT6IswuVo5XUaOgLms06khg=">AAACe3icdVHLjtMwFHXCayivAksWWBSkFqGSjBhgFkijYcOOAVFmpLqNbhwntcZ2rNgpqlx/BX/Gjk9hg3DaIg0IjmTp6NyH7z0314IbmyTfo/jS5StXr+1d7924eev2nf7de59N3TaUTWgt6uYsB8MEV2xiuRXsTDcMZC7YaX7+toufLlljeK0+2ZVmMwmV4iWnYIOU9b8S0+rMLTHhChMJdpHn7qOfS0+OeVURh0OCzNyagNALWL+hfk00NJaDyNxW9OQLL5jlomBu04KCcO+9z/LhcrTe9vEYE8GMMVxiUjZA3ZCIusJyNHf0+b73jogwdQFz6rP+IBknG+AL5CBJD1+mON0pA7TDSdb/RoqatpIpSwUYM00TbWeum5IK5nukNUwDPYeKTQNVIJmZuY15Hj8JSoHLuglPWbxRL1Y4kMasZB4yu93M37FO/Fds2try9cxxpVvLFN1+VLYC2xp3l8AFbxi1YhUI0IaHWTFdQLDGhnv1ggm/N8X/J5P98eE4+fBicHS8c2MPPUCP0BCl6BU6Qu/QCZogin5ED6NhNIp+xo/jp/GzbWoc7Wruoz8QH/wChofEbg==</latexit>

Claim:   y  fools  the  funcPon    z 7! eOb(Hz + Tz)<latexit sha1_base64="0n//+HXi/Bo3CnKHqeLmLSzZu7s=">AAACFHicdZDLSgMxFIYz9VbrrerSTbAIFaXMiLfuim66s0JrC20pmcxpG5q5kGSUduhLuPFV3LhQcevCnW9jph2hiv4Q+PnOOeSc3w44k8o0P43U3PzC4lJ6ObOyura+kd3cupF+KCjUqM990bCJBM48qCmmODQCAcS1OdTtwWVcr9+CkMz3qmoYQNslPY91GSVKo072cIRbLgmk8nHrjjmgGHcg0kj1KeHR1XjcsfPlET7A1dF+J5szC+ZEeMacmFbx1MJWQnIoUaWT/Wg5Pg1d8BTlRMqmZQaqHRGhGOUwzrRCCQGhA9KDprYecUG2o8lVY7yniYO7vtDPU3hCZyci4ko5dG3dGa8rf9di+FetGarueTtiXhAq8Oj0o27Isc4gjgg7TABVfKgNoYLpXTHtE0Go0kFmdAjfl+L/Te2oUCyY18e50kWSRhrtoF2URxY6QyVURhVUQxTdo0f0jF6MB+PJeDXepq0pI5nZRj9kvH8Bd4Wejw==</latexit><latexit sha1_base64="0n//+HXi/Bo3CnKHqeLmLSzZu7s=">AAACFHicdZDLSgMxFIYz9VbrrerSTbAIFaXMiLfuim66s0JrC20pmcxpG5q5kGSUduhLuPFV3LhQcevCnW9jph2hiv4Q+PnOOeSc3w44k8o0P43U3PzC4lJ6ObOyura+kd3cupF+KCjUqM990bCJBM48qCmmODQCAcS1OdTtwWVcr9+CkMz3qmoYQNslPY91GSVKo072cIRbLgmk8nHrjjmgGHcg0kj1KeHR1XjcsfPlET7A1dF+J5szC+ZEeMacmFbx1MJWQnIoUaWT/Wg5Pg1d8BTlRMqmZQaqHRGhGOUwzrRCCQGhA9KDprYecUG2o8lVY7yniYO7vtDPU3hCZyci4ko5dG3dGa8rf9di+FetGarueTtiXhAq8Oj0o27Isc4gjgg7TABVfKgNoYLpXTHtE0Go0kFmdAjfl+L/Te2oUCyY18e50kWSRhrtoF2URxY6QyVURhVUQxTdo0f0jF6MB+PJeDXepq0pI5nZRj9kvH8Bd4Wejw==</latexit><latexit sha1_base64="0n//+HXi/Bo3CnKHqeLmLSzZu7s=">AAACFHicdZDLSgMxFIYz9VbrrerSTbAIFaXMiLfuim66s0JrC20pmcxpG5q5kGSUduhLuPFV3LhQcevCnW9jph2hiv4Q+PnOOeSc3w44k8o0P43U3PzC4lJ6ObOyura+kd3cupF+KCjUqM990bCJBM48qCmmODQCAcS1OdTtwWVcr9+CkMz3qmoYQNslPY91GSVKo072cIRbLgmk8nHrjjmgGHcg0kj1KeHR1XjcsfPlET7A1dF+J5szC+ZEeMacmFbx1MJWQnIoUaWT/Wg5Pg1d8BTlRMqmZQaqHRGhGOUwzrRCCQGhA9KDprYecUG2o8lVY7yniYO7vtDPU3hCZyci4ko5dG3dGa8rf9di+FetGarueTtiXhAq8Oj0o27Isc4gjgg7TABVfKgNoYLpXTHtE0Go0kFmdAjfl+L/Te2oUCyY18e50kWSRhrtoF2URxY6QyVURhVUQxTdo0f0jF6MB+PJeDXepq0pI5nZRj9kvH8Bd4Wejw==</latexit>

To  bound  error  term,  use  fact  that  Õb  has  small  derivaPves  (same  as  [HKM]):    

We  consider  the  mulPdimensional  Taylor  expansion:  

Suffices  for  y  to  fool  CNFs  )<latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit><latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit><latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit>

@↵ eOb<latexit sha1_base64="miSnFXf1UjDzCzi0MX7FA6m9XBQ=">AAACBnicbVBNS8NAEN34WetX1aMgwSJ4Kon41VvRizcrWFtoQphspu3SzQe7G6WE3rz4V7x4UPHqb/Dmv3HTFtTqg4HHezPMzPMTzqSyrE9jZnZufmGxsFRcXlldWy9tbN7IOBUUGzTmsWj5IJGzCBuKKY6tRCCEPsem3z/P/eYtCsni6FoNEnRD6EaswygoLXmlHScBoRhwzwGe9MC5YwEqxgPMLoee75XKVuXIsqvHtmlVrBG+iT0hZTJB3St9OEFM0xAjRTlI2batRLlZvoNyHBadVGICtA9dbGsaQYjSzUZ/DM09rQRmJxa6ImWO1J8TGYRSDkJfd4agenLay8X/vHaqOqduxqIkVRjR8aJOyk0Vm3koZsAEUsUHmgAVTN9q0h4IoEpHV9Qh2NMv/yWNg0q1Yl0dlmtnkzQKZJvskn1ikxNSIxekThqEknvySJ7Ji/FgPBmvxtu4dcaYzGyRXzDevwB9Ipnp</latexit><latexit sha1_base64="miSnFXf1UjDzCzi0MX7FA6m9XBQ=">AAACBnicbVBNS8NAEN34WetX1aMgwSJ4Kon41VvRizcrWFtoQphspu3SzQe7G6WE3rz4V7x4UPHqb/Dmv3HTFtTqg4HHezPMzPMTzqSyrE9jZnZufmGxsFRcXlldWy9tbN7IOBUUGzTmsWj5IJGzCBuKKY6tRCCEPsem3z/P/eYtCsni6FoNEnRD6EaswygoLXmlHScBoRhwzwGe9MC5YwEqxgPMLoee75XKVuXIsqvHtmlVrBG+iT0hZTJB3St9OEFM0xAjRTlI2batRLlZvoNyHBadVGICtA9dbGsaQYjSzUZ/DM09rQRmJxa6ImWO1J8TGYRSDkJfd4agenLay8X/vHaqOqduxqIkVRjR8aJOyk0Vm3koZsAEUsUHmgAVTN9q0h4IoEpHV9Qh2NMv/yWNg0q1Yl0dlmtnkzQKZJvskn1ikxNSIxekThqEknvySJ7Ji/FgPBmvxtu4dcaYzGyRXzDevwB9Ipnp</latexit><latexit sha1_base64="miSnFXf1UjDzCzi0MX7FA6m9XBQ=">AAACBnicbVBNS8NAEN34WetX1aMgwSJ4Kon41VvRizcrWFtoQphspu3SzQe7G6WE3rz4V7x4UPHqb/Dmv3HTFtTqg4HHezPMzPMTzqSyrE9jZnZufmGxsFRcXlldWy9tbN7IOBUUGzTmsWj5IJGzCBuKKY6tRCCEPsem3z/P/eYtCsni6FoNEnRD6EaswygoLXmlHScBoRhwzwGe9MC5YwEqxgPMLoee75XKVuXIsqvHtmlVrBG+iT0hZTJB3St9OEFM0xAjRTlI2batRLlZvoNyHBadVGICtA9dbGsaQYjSzUZ/DM09rQRmJxa6ImWO1J8TGYRSDkJfd4agenLay8X/vHaqOqduxqIkVRjR8aJOyk0Vm3koZsAEUsUHmgAVTN9q0h4IoEpHV9Qh2NMv/yWNg0q1Yl0dlmtnkzQKZJvskn1ikxNSIxekThqEknvySJ7Ji/FgPBmvxtu4dcaYzGyRXzDevwB9Ipnp</latexit>

[Bentkus  90]  

eOb(Hz) +X

1|↵|c

1

↵!@↵ eOb(Hz)(Tz)↵ ± err

<latexit sha1_base64="tEWNFxXepDCbGfynkXvGvGMZN/g=">AAACgHicfVFNT9wwEHVCP+i2tAs99uKyIO0KsU0q+kFPqL1wK0hsQdos0cSZ7FrYSWQ7VIvJ/+jv6q1/pqqzGySKaEey9PzmzXj8JikF1yYIfnn+yoOHjx6vPuk8fbb2/EV3feObLirFcMQKUaizBDQKnuPIcCPwrFQIMhF4mlx8afKnl6g0L/ITMy9xImGa84wzMI6Kuz+i7zxFw0WKNpJgZgyE/VrXcdI/vBrQHRrpSsY2pJFAeh2BKGdw3WBW0yhTwEK7JF+7ewnKcBBxS9X/790/uRqc30hdsaQLkZIWlarjbi8YBougt8C7INx/H9KwZXqkjaO4+zNKC1ZJzA0ToPU4DEozsc1ITGDdiSqNJbALmOLYwRwk6oldOFjTbcekNCuUO7mhC/Z2hQWp9VwmTtnMqO/mGvK+3Lgy2ceJ5XlZGczZ8qGsEtQUtFkHTblCZsTcAWCKu1kpm4Hz1bildZwJNz+l/wajt8P9YXC81zv43LqxSl6RTdInIflADsghOSIjwshvb8vb9Yb+ij/w3/jhUup7bc1L8lf4n/4A1CXD4w==</latexit><latexit sha1_base64="tEWNFxXepDCbGfynkXvGvGMZN/g=">AAACgHicfVFNT9wwEHVCP+i2tAs99uKyIO0KsU0q+kFPqL1wK0hsQdos0cSZ7FrYSWQ7VIvJ/+jv6q1/pqqzGySKaEey9PzmzXj8JikF1yYIfnn+yoOHjx6vPuk8fbb2/EV3feObLirFcMQKUaizBDQKnuPIcCPwrFQIMhF4mlx8afKnl6g0L/ITMy9xImGa84wzMI6Kuz+i7zxFw0WKNpJgZgyE/VrXcdI/vBrQHRrpSsY2pJFAeh2BKGdw3WBW0yhTwEK7JF+7ewnKcBBxS9X/790/uRqc30hdsaQLkZIWlarjbi8YBougt8C7INx/H9KwZXqkjaO4+zNKC1ZJzA0ToPU4DEozsc1ITGDdiSqNJbALmOLYwRwk6oldOFjTbcekNCuUO7mhC/Z2hQWp9VwmTtnMqO/mGvK+3Lgy2ceJ5XlZGczZ8qGsEtQUtFkHTblCZsTcAWCKu1kpm4Hz1bildZwJNz+l/wajt8P9YXC81zv43LqxSl6RTdInIflADsghOSIjwshvb8vb9Yb+ij/w3/jhUup7bc1L8lf4n/4A1CXD4w==</latexit><latexit sha1_base64="tEWNFxXepDCbGfynkXvGvGMZN/g=">AAACgHicfVFNT9wwEHVCP+i2tAs99uKyIO0KsU0q+kFPqL1wK0hsQdos0cSZ7FrYSWQ7VIvJ/+jv6q1/pqqzGySKaEey9PzmzXj8JikF1yYIfnn+yoOHjx6vPuk8fbb2/EV3feObLirFcMQKUaizBDQKnuPIcCPwrFQIMhF4mlx8afKnl6g0L/ITMy9xImGa84wzMI6Kuz+i7zxFw0WKNpJgZgyE/VrXcdI/vBrQHRrpSsY2pJFAeh2BKGdw3WBW0yhTwEK7JF+7ewnKcBBxS9X/790/uRqc30hdsaQLkZIWlarjbi8YBougt8C7INx/H9KwZXqkjaO4+zNKC1ZJzA0ToPU4DEozsc1ITGDdiSqNJbALmOLYwRwk6oldOFjTbcekNCuUO7mhC/Z2hQWp9VwmTtnMqO/mGvK+3Lgy2ceJ5XlZGczZ8qGsEtQUtFkHTblCZsTcAWCKu1kpm4Hz1bildZwJNz+l/wajt8P9YXC81zv43LqxSl6RTdInIflADsghOSIjwshvb8vb9Yb+ij/w3/jhUup7bc1L8lf4n/4A1CXD4w==</latexit>

Previous  slide  

Page 42: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Recap  

.  .  .      y10  y2  y6   y3  

y12   y9  y11  y4  

y7  

Ex

[ eOb(Ax)] ⇡ Ey

[ eOb(Ay)]<latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit><latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit><latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit>

What  we  just  sketched  Bounding  error  incurred  by  a  single  swap:  

.  .  .      x10  x2  x6   x3  

x12   x9  x11  x4  

x7  

Goal  is  to  “fool”  the  orthant  mollifier:    

y  pseudorandom:  x  uniform:  

r-­‐wise   r-­‐wise   r-­‐wise  uniform   uniform   uniform  

x10  x2  x6  

uniform  

y10  y2  y6  

r-­‐wise  

   

Page 43: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Outline  of  the  rest  of  the  talk    (=  the  structure  of  our  proof)  

1.  A  useful  decomposiPon  of  polytopes  

2.  “Smooth  version”  of  the  problem  

3.  Proving  the  smooth  version  

4.   Going  from  smooth  version  to  actual  version  

Page 44: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

small  error  region  

≈  1  

≈  0  

 1  

0  

Ex

[Ob(Ax)] ⇡ Ey

[Ob(Ay)]<latexit sha1_base64="0ybTWB/15GkgfKOkcmcJv90GMEA=">AAACenichVHZSsQwFE3rNo7bqI+CBAdxRBhacX1zQfBNBUeFaSlpJqPBtAlJKlNCf8JP880/8UUwrSOouFwI93DO3XJvLBhV2vOeHXdkdGx8ojZZn5qemZ1rzC9cKZ5JTDqYMy5vYqQIoynpaKoZuRGSoCRm5Dq+Py716wciFeXppc4FCRN0m9I+xUhbKmo8BgnSd1yYysexOSmKyAQxZz2VJ9aZQVF0KxEjZs6KKG4dfpXXQxggISQf1P8tlv9dLC+LRY2m1/Yqg5/Atufv7/jQHzJNMLTzqPEU9DjOEpJqzJBSXd8TOjRIaooZKepBpohA+B7dkq6FKUqICk21uwKuWqYH+1zal2pYsZ8zDEpUOZ2NLOdW37WS/EnrZrq/FxqaikyTFL836mcMag7LQ8AelQRrlluAsKR2VojvkERY23PV7RI+fgp/B53N9n7bu9hqHhwNt1EDS2AFtIAPdsEBOAXnoAMweHGWnTWn5by6TXfd3XgPdZ1hziL4Yu7WG1sDxiM=</latexit><latexit sha1_base64="0ybTWB/15GkgfKOkcmcJv90GMEA=">AAACenichVHZSsQwFE3rNo7bqI+CBAdxRBhacX1zQfBNBUeFaSlpJqPBtAlJKlNCf8JP880/8UUwrSOouFwI93DO3XJvLBhV2vOeHXdkdGx8ojZZn5qemZ1rzC9cKZ5JTDqYMy5vYqQIoynpaKoZuRGSoCRm5Dq+Py716wciFeXppc4FCRN0m9I+xUhbKmo8BgnSd1yYysexOSmKyAQxZz2VJ9aZQVF0KxEjZs6KKG4dfpXXQxggISQf1P8tlv9dLC+LRY2m1/Yqg5/Atufv7/jQHzJNMLTzqPEU9DjOEpJqzJBSXd8TOjRIaooZKepBpohA+B7dkq6FKUqICk21uwKuWqYH+1zal2pYsZ8zDEpUOZ2NLOdW37WS/EnrZrq/FxqaikyTFL836mcMag7LQ8AelQRrlluAsKR2VojvkERY23PV7RI+fgp/B53N9n7bu9hqHhwNt1EDS2AFtIAPdsEBOAXnoAMweHGWnTWn5by6TXfd3XgPdZ1hziL4Yu7WG1sDxiM=</latexit><latexit sha1_base64="0ybTWB/15GkgfKOkcmcJv90GMEA=">AAACenichVHZSsQwFE3rNo7bqI+CBAdxRBhacX1zQfBNBUeFaSlpJqPBtAlJKlNCf8JP880/8UUwrSOouFwI93DO3XJvLBhV2vOeHXdkdGx8ojZZn5qemZ1rzC9cKZ5JTDqYMy5vYqQIoynpaKoZuRGSoCRm5Dq+Py716wciFeXppc4FCRN0m9I+xUhbKmo8BgnSd1yYysexOSmKyAQxZz2VJ9aZQVF0KxEjZs6KKG4dfpXXQxggISQf1P8tlv9dLC+LRY2m1/Yqg5/Atufv7/jQHzJNMLTzqPEU9DjOEpJqzJBSXd8TOjRIaooZKepBpohA+B7dkq6FKUqICk21uwKuWqYH+1zal2pYsZ8zDEpUOZ2NLOdW37WS/EnrZrq/FxqaikyTFL836mcMag7LQ8AelQRrlluAsKR2VojvkERY23PV7RI+fgp/B53N9n7bu9hqHhwNt1EDS2AFtIAPdsEBOAXnoAMweHGWnTWn5by6TXfd3XgPdZ1hziL4Yu7WG1sDxiM=</latexit>

eOb : Rm ! [0, 1]<latexit sha1_base64="1dx6Lx1GMaKrnNeKJiVqle7t6F8=">AAACGnicdVDLSgMxFM3UV62vUZdugkVwIWWm+Kqroht3VrFW6Iwlk7ltQzMPkoxShvkPN/6KGxcq7sSNf2P6EKrogcDhnHvJPceLOZPKsj6N3NT0zOxcfr6wsLi0vGKurl3JKBEU6jTikbj2iATOQqgrpjhcxwJI4HFoeL2Tgd+4BSFZFF6qfgxuQDohazNKlJZaZtm5Yz4oxn1InYCoLiU8PcuyloeP8FDwvPQiuwmwoyLctHZst2UWrZI1BJ4ge5Zd2bexPVaKaIxay3x3/IgmAYSKciJl07Zi5aZEKEY5ZAUnkRAT2iMdaGoakgCkmw6zZXhLKz5uR0K/UOGhOrmRkkDKfuDpycG18rc3EP/ymolqH7opC+NEQUhHH7UTjnXMQVHYZwKo4n1NCBVM34pplwhCla6zoEv4Tor/J/VyqVKyzneL1eNxG3m0gTbRNrLRAaqiU1RDdUTRPXpEz+jFeDCejFfjbTSaM8Y76+gHjI8vCrqg8g==</latexit><latexit sha1_base64="1dx6Lx1GMaKrnNeKJiVqle7t6F8=">AAACGnicdVDLSgMxFM3UV62vUZdugkVwIWWm+Kqroht3VrFW6Iwlk7ltQzMPkoxShvkPN/6KGxcq7sSNf2P6EKrogcDhnHvJPceLOZPKsj6N3NT0zOxcfr6wsLi0vGKurl3JKBEU6jTikbj2iATOQqgrpjhcxwJI4HFoeL2Tgd+4BSFZFF6qfgxuQDohazNKlJZaZtm5Yz4oxn1InYCoLiU8PcuyloeP8FDwvPQiuwmwoyLctHZst2UWrZI1BJ4ge5Zd2bexPVaKaIxay3x3/IgmAYSKciJl07Zi5aZEKEY5ZAUnkRAT2iMdaGoakgCkmw6zZXhLKz5uR0K/UOGhOrmRkkDKfuDpycG18rc3EP/ymolqH7opC+NEQUhHH7UTjnXMQVHYZwKo4n1NCBVM34pplwhCla6zoEv4Tor/J/VyqVKyzneL1eNxG3m0gTbRNrLRAaqiU1RDdUTRPXpEz+jFeDCejFfjbTSaM8Y76+gHjI8vCrqg8g==</latexit><latexit sha1_base64="1dx6Lx1GMaKrnNeKJiVqle7t6F8=">AAACGnicdVDLSgMxFM3UV62vUZdugkVwIWWm+Kqroht3VrFW6Iwlk7ltQzMPkoxShvkPN/6KGxcq7sSNf2P6EKrogcDhnHvJPceLOZPKsj6N3NT0zOxcfr6wsLi0vGKurl3JKBEU6jTikbj2iATOQqgrpjhcxwJI4HFoeL2Tgd+4BSFZFF6qfgxuQDohazNKlJZaZtm5Yz4oxn1InYCoLiU8PcuyloeP8FDwvPQiuwmwoyLctHZst2UWrZI1BJ4ge5Zd2bexPVaKaIxay3x3/IgmAYSKciJl07Zi5aZEKEY5ZAUnkRAT2iMdaGoakgCkmw6zZXhLKz5uR0K/UOGhOrmRkkDKfuDpycG18rc3EP/ymolqH7opC+NEQUhHH7UTjnXMQVHYZwKo4n1NCBVM34pplwhCla6zoEv4Tor/J/VyqVKyzneL1eNxG3m0gTbRNrLRAaqiU1RDdUTRPXpEz+jFeDCejFfjbTSaM8Y76+gHjI8vCrqg8g==</latexit>

Ob : Rm ! {0, 1}<latexit sha1_base64="bwg1OKOo/qSNMNQ/prYW+O2q8MM=">AAACEHicdVDLSsNAFJ3UV62vqEs3g0XoQkoivuqq6MadVYwtNDFMptN26OTBzEQoIb/gxl9x40LFrUt3/o2TNEIVPTBw5px7ufceL2JUSMP41Eozs3PzC+XFytLyyuqavr5xI8KYY2LhkIW84yFBGA2IJalkpBNxgnyPkbY3Osv89h3hgobBtRxHxPHRIKB9ipFUkqvXbB/JIUYsuUhdD57A/O95yVV660NbhtBOjF3TTl29atSNHHCKHBhm49CEZqFUQYGWq3/YvRDHPgkkZkiIrmlE0kkQlxQzklbsWJAI4REakK6iAfKJcJL8ohTuKKUH+yFXL5AwV6c7EuQLMfY9VZntK357mfiX141l/9hJaBDFkgR4MqgfM6gOzeKBPcoJlmysCMKcql0hHiKOsFQhVlQI35fC/4m1V2/Ujcv9avO0SKMMtsA2qAETHIEmOActYAEM7sEjeAYv2oP2pL1qb5PSklb0bIIf0N6/AKfAnHc=</latexit><latexit sha1_base64="bwg1OKOo/qSNMNQ/prYW+O2q8MM=">AAACEHicdVDLSsNAFJ3UV62vqEs3g0XoQkoivuqq6MadVYwtNDFMptN26OTBzEQoIb/gxl9x40LFrUt3/o2TNEIVPTBw5px7ufceL2JUSMP41Eozs3PzC+XFytLyyuqavr5xI8KYY2LhkIW84yFBGA2IJalkpBNxgnyPkbY3Osv89h3hgobBtRxHxPHRIKB9ipFUkqvXbB/JIUYsuUhdD57A/O95yVV660NbhtBOjF3TTl29atSNHHCKHBhm49CEZqFUQYGWq3/YvRDHPgkkZkiIrmlE0kkQlxQzklbsWJAI4REakK6iAfKJcJL8ohTuKKUH+yFXL5AwV6c7EuQLMfY9VZntK357mfiX141l/9hJaBDFkgR4MqgfM6gOzeKBPcoJlmysCMKcql0hHiKOsFQhVlQI35fC/4m1V2/Ujcv9avO0SKMMtsA2qAETHIEmOActYAEM7sEjeAYv2oP2pL1qb5PSklb0bIIf0N6/AKfAnHc=</latexit><latexit sha1_base64="bwg1OKOo/qSNMNQ/prYW+O2q8MM=">AAACEHicdVDLSsNAFJ3UV62vqEs3g0XoQkoivuqq6MadVYwtNDFMptN26OTBzEQoIb/gxl9x40LFrUt3/o2TNEIVPTBw5px7ufceL2JUSMP41Eozs3PzC+XFytLyyuqavr5xI8KYY2LhkIW84yFBGA2IJalkpBNxgnyPkbY3Osv89h3hgobBtRxHxPHRIKB9ipFUkqvXbB/JIUYsuUhdD57A/O95yVV660NbhtBOjF3TTl29atSNHHCKHBhm49CEZqFUQYGWq3/YvRDHPgkkZkiIrmlE0kkQlxQzklbsWJAI4REakK6iAfKJcJL8ohTuKKUH+yFXL5AwV6c7EuQLMfY9VZntK357mfiX141l/9hJaBDFkgR4MqgfM6gOzeKBPcoJlmysCMKcql0hHiKOsFQhVlQI35fC/4m1V2/Ujcv9avO0SKMMtsA2qAETHIEmOActYAEM7sEjeAYv2oP2pL1qb5PSklb0bIIf0N6/AKfAnHc=</latexit>

Ex

[ eOb(Ax)] ⇡ Ey

[ eOb(Ay)]<latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit><latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit><latexit sha1_base64="DdQ35NqPG8Ts7wvRtHDVXIeVkws=">AAACknicjVFda9swFJW9bsvSfXgre9qLaChkL8EuXbeyh6Urgz4U2kLTBmITZPmmEZEtIclbjPAf6s/Z2/7N5CSFZKxsF8Q9nHvuh+5NJWfahOEvz3+09fjJ09az9vbzFy9fBa/fXGtRKgoDKrhQw5Ro4KyAgWGGw1AqIHnK4SadnTTxm++gNBPFlakkJDm5LdiEUWIcNQ7u4pyYqZB24dPUfqvrsY1TwTNd5c7ZeV2P4h8sA8N4BksdJdyeO2HaPd6Uvk9wTKRUYt7+Z+Hq/wtXTeFx0Al74cLwGvgQRkeHEY5WTAet7GIc/IwzQcscCkM50XoUhdIklijDKIe6HZcaJKEzcgsjBwuSg07sYqc13nNMhidCuVcYvGDXMyzJdTOdUzaD6z9jDfm32Kg0k0+JZYUsDRR02WhScmwEbg6EM6aAGl45QKhiblZMp0QRatwZ224J9z/FD4PBfu+oF14edPpfV9tooXdoF3VRhD6iPjpFF2iAqBd4h94Xr++/9T/7x/7JUup7q5wdtGH+2W8LX88z</latexit>

What  we’ve  shown:  What  we’d  like  to  show:  

(closeness  in  CDF  distance)  

Page 45: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Another  conceptual  difference/challenge:    Boolean  vs.  Gaussian  anPconcentraPon  

≈  1  

≈  0  

Proofs  of  CLTs  (e.g.  [HKM]):    Gaussian  anPconcentraPon  

Since  we  are  bypassing  Gaussians:    Have  to  instead  reason  about  Boolean  anPconcentraPon  

   

(Fact:  Boolean  anPconcentraPon  

Gaussian  anPconcentraPon)  

)<latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit><latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit><latexit sha1_base64="YpFhaZHBfDESR4GPpU0Zw1k+JAM=">AAAB8XicdVBNSwMxEM3Wr1q/qh69BIvgqeyKX70VvXis4trCdinZNG1Ds8mSzCpl6c/w4kHFq//Gm//GtF2hij4YeLw3w8y8KBHcgOt+OoWFxaXlleJqaW19Y3OrvL1zZ1SqKfOpEkq3ImKY4JL5wEGwVqIZiSPBmtHwcuI375k2XMlbGCUsjElf8h6nBKwUtG94fwBEa/XQKVfcqjsFniMnrlc79bCXKxWUo9Epf7S7iqYxk0AFMSbw3ATCjGjgVLBxqZ0alhA6JH0WWCpJzEyYTU8e4wOrdHFPaVsS8FSdn8hIbMwojmxnTGBgfnsT8S8vSKF3HmZcJikwSWeLeqnAoPDkf9zlmlEQI0sI1dzeiumAaELBplSyIXx/iv8n/lG1VnWvjyv1izyNItpD++gQeegM1dEVaiAfUaTQI3pGLw44T86r8zZrLTj5zC76Aef9CxoQkVY=</latexit>

AG,      G        N(0,1)n      ~  

Page 46: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Litlewood–Offord  anPconcentraPon  inequality  

For all open intervals I ⇢ R of radius 2,

<latexit sha1_base64="gltKzb2mVrW89WLFxAVATWkF5vc=">AAACKXicdVDLThtBEJyFJIDJw5BjLi1MpBwiaxeF1w2CFCU3iGJA8lpW77gXRszOrGZ6EdbK35NLfoULByC55kcyNo5EUKhTqapbXV1ZqZXnOP4Zzcw+efpsbn6hsfj8xctXzaXlQ28rJ6kjrbbuOENPWhnqsGJNx6UjLDJNR9nZ3tg/OifnlTXfeFhSr8ATo3IlkYPUb+6mTBdcf7IOUGuwJRlQhsmdo/aw+iX1VeaJIS2QT7Os/jpaBZuDw4GqPKy9H0G/2Yrb8QRwj6zHyfZGAslUaYkp9vvNq3RgZVWQYanR+24Sl9yr0bGSmkaNtPJUojzDE+oGarAg36snr47gbVAGkIe4uTUME/X+Ro2F98MiC5PjxP6hNxb/53Urzrd6tTJlxWTk3aG80sAWxr3BQDmSrIeBoHQqZAV5ig5l6Mo3Qgl/P4XHSWetvd2ODz60dj5O25gXb8SKeCcSsSl2xGexLzpCiu/iUlyLm+hHdBXdRr/uRmei6c5r8Q+i338ACB+mkw==</latexit><latexit sha1_base64="gltKzb2mVrW89WLFxAVATWkF5vc=">AAACKXicdVDLThtBEJyFJIDJw5BjLi1MpBwiaxeF1w2CFCU3iGJA8lpW77gXRszOrGZ6EdbK35NLfoULByC55kcyNo5EUKhTqapbXV1ZqZXnOP4Zzcw+efpsbn6hsfj8xctXzaXlQ28rJ6kjrbbuOENPWhnqsGJNx6UjLDJNR9nZ3tg/OifnlTXfeFhSr8ATo3IlkYPUb+6mTBdcf7IOUGuwJRlQhsmdo/aw+iX1VeaJIS2QT7Os/jpaBZuDw4GqPKy9H0G/2Yrb8QRwj6zHyfZGAslUaYkp9vvNq3RgZVWQYanR+24Sl9yr0bGSmkaNtPJUojzDE+oGarAg36snr47gbVAGkIe4uTUME/X+Ro2F98MiC5PjxP6hNxb/53Urzrd6tTJlxWTk3aG80sAWxr3BQDmSrIeBoHQqZAV5ig5l6Mo3Qgl/P4XHSWetvd2ODz60dj5O25gXb8SKeCcSsSl2xGexLzpCiu/iUlyLm+hHdBXdRr/uRmei6c5r8Q+i338ACB+mkw==</latexit><latexit sha1_base64="gltKzb2mVrW89WLFxAVATWkF5vc=">AAACKXicdVDLThtBEJyFJIDJw5BjLi1MpBwiaxeF1w2CFCU3iGJA8lpW77gXRszOrGZ6EdbK35NLfoULByC55kcyNo5EUKhTqapbXV1ZqZXnOP4Zzcw+efpsbn6hsfj8xctXzaXlQ28rJ6kjrbbuOENPWhnqsGJNx6UjLDJNR9nZ3tg/OifnlTXfeFhSr8ATo3IlkYPUb+6mTBdcf7IOUGuwJRlQhsmdo/aw+iX1VeaJIS2QT7Os/jpaBZuDw4GqPKy9H0G/2Yrb8QRwj6zHyfZGAslUaYkp9vvNq3RgZVWQYanR+24Sl9yr0bGSmkaNtPJUojzDE+oGarAg36snr47gbVAGkIe4uTUME/X+Ro2F98MiC5PjxP6hNxb/53Urzrd6tTJlxWTk3aG80sAWxr3BQDmSrIeBoHQqZAV5ig5l6Mo3Qgl/P4XHSWetvd2ODz60dj5O25gXb8SKeCcSsSl2xGexLzpCiu/iUlyLm+hHdBXdRr/uRmei6c5r8Q+i338ACB+mkw==</latexit>

   

Prx⇠{±1}n

[w · x 2 I ] . 1pn.

<latexit sha1_base64="JhAARpKB7Fd3lbl+IEdqrhTLtZI=">AAACV3icdVFNbxMxEPUu/QihhRSOXCwipB6qaBe1tL1VcIFbKjW0UryNvF5va8UfW3sWiCz/SSQO8Fe44E1Tqa1gJGue3szTzDyXjRQOsuxXkj5ZW9/Y7D3tP9vafv5isPPyizOtZXzCjDT2oqSOS6H5BARIftFYTlUp+Xk5/9jVz79y64TRZ7BoeKHolRa1YBQiNRsYoihcm8Yvs1V+bEOYeVIaWbmFisl/D8QJRTxpFM5JuNRhSva+EVYZwI/6hMafyV6BieTORREmtaUs98TdWPA6hNFsMMxG2TLwPXCQ5cfvc5yvmCFaxXg2+EEqw1rFNTBJnZvmWQOFpxYEkzz0Set4Q9mcXvFphJoq7gq/NCbgt5GpcG1sfBrwkr2v8FS5bvvY2Z3vHtc68l+1aQv1UeGFblrgmt0OqluJweDOZVwJyxnIRQSUWRF3xeyaRi8g/kU/mnB3Kf4/mLwbHY+y0/3hyYeVGz30Gr1BuyhHh+gEfUJjNEEM/UR/krVkPfmdonQj7d22pslK8wo9iHTnL7RZtuw=</latexit><latexit sha1_base64="JhAARpKB7Fd3lbl+IEdqrhTLtZI=">AAACV3icdVFNbxMxEPUu/QihhRSOXCwipB6qaBe1tL1VcIFbKjW0UryNvF5va8UfW3sWiCz/SSQO8Fe44E1Tqa1gJGue3szTzDyXjRQOsuxXkj5ZW9/Y7D3tP9vafv5isPPyizOtZXzCjDT2oqSOS6H5BARIftFYTlUp+Xk5/9jVz79y64TRZ7BoeKHolRa1YBQiNRsYoihcm8Yvs1V+bEOYeVIaWbmFisl/D8QJRTxpFM5JuNRhSva+EVYZwI/6hMafyV6BieTORREmtaUs98TdWPA6hNFsMMxG2TLwPXCQ5cfvc5yvmCFaxXg2+EEqw1rFNTBJnZvmWQOFpxYEkzz0Set4Q9mcXvFphJoq7gq/NCbgt5GpcG1sfBrwkr2v8FS5bvvY2Z3vHtc68l+1aQv1UeGFblrgmt0OqluJweDOZVwJyxnIRQSUWRF3xeyaRi8g/kU/mnB3Kf4/mLwbHY+y0/3hyYeVGz30Gr1BuyhHh+gEfUJjNEEM/UR/krVkPfmdonQj7d22pslK8wo9iHTnL7RZtuw=</latexit><latexit sha1_base64="JhAARpKB7Fd3lbl+IEdqrhTLtZI=">AAACV3icdVFNbxMxEPUu/QihhRSOXCwipB6qaBe1tL1VcIFbKjW0UryNvF5va8UfW3sWiCz/SSQO8Fe44E1Tqa1gJGue3szTzDyXjRQOsuxXkj5ZW9/Y7D3tP9vafv5isPPyizOtZXzCjDT2oqSOS6H5BARIftFYTlUp+Xk5/9jVz79y64TRZ7BoeKHolRa1YBQiNRsYoihcm8Yvs1V+bEOYeVIaWbmFisl/D8QJRTxpFM5JuNRhSva+EVYZwI/6hMafyV6BieTORREmtaUs98TdWPA6hNFsMMxG2TLwPXCQ5cfvc5yvmCFaxXg2+EEqw1rFNTBJnZvmWQOFpxYEkzz0Set4Q9mcXvFphJoq7gq/NCbgt5GpcG1sfBrwkr2v8FS5bvvY2Z3vHtc68l+1aQv1UeGFblrgmt0OqluJweDOZVwJyxnIRQSUWRF3xeyaRi8g/kU/mnB3Kf4/mLwbHY+y0/3hyYeVGz30Gr1BuyhHh+gEfUJjNEEM/UR/krVkPfmdonQj7d22pslK8wo9iHTnL7RZtuw=</latexit>

R<latexit sha1_base64="Y4cssu/Y5xLGAWxQ8Y3Sa5FTCBo=">AAAB8HicdVDLSsNAFL2pr1pfVZduBovgqiTiq7uiG5dVjC22oUymk3boZBJmJkIJ+Qs3LlTc+jnu/BsnbYQqemDgcM69zLnHjzlT2rY/rdLC4tLySnm1sra+sblV3d65U1EiCXVJxCPZ8bGinAnqaqY57cSS4tDntO2PL3O//UClYpG41ZOYeiEeChYwgrWR7nsh1iPfT2+yfrVm1+0p0Bw5sZ3GqYOcQqlBgVa/+tEbRCQJqdCEY6W6jh1rL8VSM8JpVuklisaYjPGQdg0VOKTKS6eJM3RglAEKImme0Giqzm+kOFRqEvpmMk+ofnu5+JfXTXRw7qVMxImmgsw+ChKOdITy89GASUo0nxiCiWQmKyIjLDHRpqSKKeH7UvQ/cY/qjbp9fVxrXhRtlGEP9uEQHDiDJlxBC1wgIOARnuHFUtaT9Wq9zUZLVrGzCz9gvX8BRsaQ2w==</latexit><latexit sha1_base64="Y4cssu/Y5xLGAWxQ8Y3Sa5FTCBo=">AAAB8HicdVDLSsNAFL2pr1pfVZduBovgqiTiq7uiG5dVjC22oUymk3boZBJmJkIJ+Qs3LlTc+jnu/BsnbYQqemDgcM69zLnHjzlT2rY/rdLC4tLySnm1sra+sblV3d65U1EiCXVJxCPZ8bGinAnqaqY57cSS4tDntO2PL3O//UClYpG41ZOYeiEeChYwgrWR7nsh1iPfT2+yfrVm1+0p0Bw5sZ3GqYOcQqlBgVa/+tEbRCQJqdCEY6W6jh1rL8VSM8JpVuklisaYjPGQdg0VOKTKS6eJM3RglAEKImme0Giqzm+kOFRqEvpmMk+ofnu5+JfXTXRw7qVMxImmgsw+ChKOdITy89GASUo0nxiCiWQmKyIjLDHRpqSKKeH7UvQ/cY/qjbp9fVxrXhRtlGEP9uEQHDiDJlxBC1wgIOARnuHFUtaT9Wq9zUZLVrGzCz9gvX8BRsaQ2w==</latexit><latexit sha1_base64="Y4cssu/Y5xLGAWxQ8Y3Sa5FTCBo=">AAAB8HicdVDLSsNAFL2pr1pfVZduBovgqiTiq7uiG5dVjC22oUymk3boZBJmJkIJ+Qs3LlTc+jnu/BsnbYQqemDgcM69zLnHjzlT2rY/rdLC4tLySnm1sra+sblV3d65U1EiCXVJxCPZ8bGinAnqaqY57cSS4tDntO2PL3O//UClYpG41ZOYeiEeChYwgrWR7nsh1iPfT2+yfrVm1+0p0Bw5sZ3GqYOcQqlBgVa/+tEbRCQJqdCEY6W6jh1rL8VSM8JpVuklisaYjPGQdg0VOKTKS6eJM3RglAEKImme0Giqzm+kOFRqEvpmMk+ofnu5+JfXTXRw7qVMxImmgsw+ChKOdITy89GASUo0nxiCiWQmKyIjLDHRpqSKKeH7UvQ/cY/qjbp9fVxrXhRtlGEP9uEQHDiDJlxBC1wgIOARnuHFUtaT9Wq9zUZLVrGzCz9gvX8BRsaQ2w==</latexit>

|I|=2  

Let w 2 Rnwhere |wi| � 1 for all i.

<latexit sha1_base64="UUvxzzUOfvX8vGRoHAuL38u180Y=">AAACKnicdVBNT9tAEF1ToBC+UjhyGREjcYpsBG25IXrh0ANFBJDiEK0342TFem3tjhsi4//Dhb/CgR4A9coPwQlBAgTv9PTejGbeC1MlLXnegzPxZXJq+uvMbGVufmFxqfpt+dgmmRHYEIlKzGnILSqpsUGSFJ6mBnkcKjwJz38N/ZO/aKxM9BENUmzFvKtlJAWnUmpX9wLCC8p/I4Hbh0BqCGJOvTDMD4sz7UK/hwbBvey3c1lcBl0E34UoMcCVAle69QLa1ZpX90aAV2Tb83e+++CPlRob46BdvQ06ichi1CQUt7bpeym1cm5ICoVFJcgsplyc8y42S6p5jLaVj7IWsF4qndEHUaIJRurrjZzH1g7isJwcBrHvvaH4kdfMKPrZyqVOM0Itng9FmQJKYFgcdKRBQWpQEi6MLH8F0eOGCyrrrZQlvCSFz0ljs75T9/5s1Xb3xm3MsFW2xjaYz36wXbbPDliDCXbFbtgdu3eunX/Og/P/eXTCGe+ssDdwHp8A2vmlwg==</latexit><latexit sha1_base64="UUvxzzUOfvX8vGRoHAuL38u180Y=">AAACKnicdVBNT9tAEF1ToBC+UjhyGREjcYpsBG25IXrh0ANFBJDiEK0342TFem3tjhsi4//Dhb/CgR4A9coPwQlBAgTv9PTejGbeC1MlLXnegzPxZXJq+uvMbGVufmFxqfpt+dgmmRHYEIlKzGnILSqpsUGSFJ6mBnkcKjwJz38N/ZO/aKxM9BENUmzFvKtlJAWnUmpX9wLCC8p/I4Hbh0BqCGJOvTDMD4sz7UK/hwbBvey3c1lcBl0E34UoMcCVAle69QLa1ZpX90aAV2Tb83e+++CPlRob46BdvQ06ichi1CQUt7bpeym1cm5ICoVFJcgsplyc8y42S6p5jLaVj7IWsF4qndEHUaIJRurrjZzH1g7isJwcBrHvvaH4kdfMKPrZyqVOM0Itng9FmQJKYFgcdKRBQWpQEi6MLH8F0eOGCyrrrZQlvCSFz0ljs75T9/5s1Xb3xm3MsFW2xjaYz36wXbbPDliDCXbFbtgdu3eunX/Og/P/eXTCGe+ssDdwHp8A2vmlwg==</latexit><latexit sha1_base64="UUvxzzUOfvX8vGRoHAuL38u180Y=">AAACKnicdVBNT9tAEF1ToBC+UjhyGREjcYpsBG25IXrh0ANFBJDiEK0342TFem3tjhsi4//Dhb/CgR4A9coPwQlBAgTv9PTejGbeC1MlLXnegzPxZXJq+uvMbGVufmFxqfpt+dgmmRHYEIlKzGnILSqpsUGSFJ6mBnkcKjwJz38N/ZO/aKxM9BENUmzFvKtlJAWnUmpX9wLCC8p/I4Hbh0BqCGJOvTDMD4sz7UK/hwbBvey3c1lcBl0E34UoMcCVAle69QLa1ZpX90aAV2Tb83e+++CPlRob46BdvQ06ichi1CQUt7bpeym1cm5ICoVFJcgsplyc8y42S6p5jLaVj7IWsF4qndEHUaIJRurrjZzH1g7isJwcBrHvvaH4kdfMKPrZyqVOM0Itng9FmQJKYFgcdKRBQWpQEi6MLH8F0eOGCyrrrZQlvCSFz0ljs75T9/5s1Xb3xm3MsFW2xjaYz36wXbbPDliDCXbFbtgdu3eunX/Og/P/eXTCGe+ssDdwHp8A2vmlwg==</latexit> In  fact:  

[Erdős  45]  

n

bn/2c

◆· 2�n

<latexit sha1_base64="GEOQMZCro95ZUGOw04o4hnDwpa8=">AAACFnicdVC7SgNBFJ2NrxhfUUubwSDYGHeDr3RBG8sIxgSyMcxO7iZDZmeWmVkhLPkLG3/FxkLFVuz8GycPIYqe6nDOvdxzTxBzpo3rfjqZufmFxaXscm5ldW19I7+5daNloijUqORSNQKigTMBNcMMh0asgEQBh3rQvxj59TtQmklxbQYxtCLSFSxklBgrtfNFnwNOBfZpT0oN2Ochl1JhcVjy1ZgOfdqRBpdu0wMxbOcLbtEdA8+QY9crn3jYmyoFNEW1nf/wO5ImEQhDOdG66bmxaaVEGUY5DHN+oiEmtE+60LRUkAh0Kx3/NcR7Vung0MYJpTB4rM5upCTSehAFdjIipqd/eyPxL6+ZmPCslTIRJwYEnRwKE46NxKOScIcpoIYPLCFUMZsV0x5RhBpbZc6W8P0p/p/USsVy0b06KlTOp21k0Q7aRfvIQ6eogi5RFdUQRffoET2jF+fBeXJenbfJaMaZ7myjH3DevwC9Z59C</latexit><latexit sha1_base64="GEOQMZCro95ZUGOw04o4hnDwpa8=">AAACFnicdVC7SgNBFJ2NrxhfUUubwSDYGHeDr3RBG8sIxgSyMcxO7iZDZmeWmVkhLPkLG3/FxkLFVuz8GycPIYqe6nDOvdxzTxBzpo3rfjqZufmFxaXscm5ldW19I7+5daNloijUqORSNQKigTMBNcMMh0asgEQBh3rQvxj59TtQmklxbQYxtCLSFSxklBgrtfNFnwNOBfZpT0oN2Ochl1JhcVjy1ZgOfdqRBpdu0wMxbOcLbtEdA8+QY9crn3jYmyoFNEW1nf/wO5ImEQhDOdG66bmxaaVEGUY5DHN+oiEmtE+60LRUkAh0Kx3/NcR7Vung0MYJpTB4rM5upCTSehAFdjIipqd/eyPxL6+ZmPCslTIRJwYEnRwKE46NxKOScIcpoIYPLCFUMZsV0x5RhBpbZc6W8P0p/p/USsVy0b06KlTOp21k0Q7aRfvIQ6eogi5RFdUQRffoET2jF+fBeXJenbfJaMaZ7myjH3DevwC9Z59C</latexit><latexit sha1_base64="GEOQMZCro95ZUGOw04o4hnDwpa8=">AAACFnicdVC7SgNBFJ2NrxhfUUubwSDYGHeDr3RBG8sIxgSyMcxO7iZDZmeWmVkhLPkLG3/FxkLFVuz8GycPIYqe6nDOvdxzTxBzpo3rfjqZufmFxaXscm5ldW19I7+5daNloijUqORSNQKigTMBNcMMh0asgEQBh3rQvxj59TtQmklxbQYxtCLSFSxklBgrtfNFnwNOBfZpT0oN2Ochl1JhcVjy1ZgOfdqRBpdu0wMxbOcLbtEdA8+QY9crn3jYmyoFNEW1nf/wO5ImEQhDOdG66bmxaaVEGUY5DHN+oiEmtE+60LRUkAh0Kx3/NcR7Vung0MYJpTB4rM5upCTSehAFdjIipqd/eyPxL6+ZmPCslTIRJwYEnRwKE46NxKOScIcpoIYPLCFUMZsV0x5RhBpbZc6W8P0p/p/USsVy0b06KlTOp21k0Q7aRfvIQ6eogi5RFdUQRffoET2jF+fBeXJenbfJaMaZ7myjH3DevwC9Z59C</latexit>

PDF  of  w    x    .  

(Exactly  Pght  for  w  =  1n)  

Page 47: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

A  high-­‐dimensional  Litlewood–Offord  inequality  (LO:  m=1  case)    

?  

Let A 2 Rm⇥nwhere |Aij | � 1 for all i, j.

<latexit sha1_base64="o8g+mN88D6AAb4esqEJhOAb/UCU=">AAACN3icdVBNT9tAEF0DLTQtbaBHLiNipB5QZKPydYP2wqFSKSKAFKfRejNOFtZra3cMjYx/Vi/9Gb1VvfRQUK/8AzYhSLSic3p6b0bz3otzJS0FwQ9vanrmydPZuWe15y/mX76qLywe2awwAlsiU5k5iblFJTW2SJLCk9wgT2OFx/HZ+5F+fI7Gykwf0jDHTsr7WiZScHJUt/4xIvxC5Qck8HchkhqilNMgjsuD6nOZRiRTtKArHy4GaBD8y91uKU+ry6iPEPqQZAa4UuDL1VO/WUG33giawXjgAVgPwu2NEMIJ02CT2e/Wv0e9TBQpahKKW9sOg5w6JTckhcKqFhUWcy7OeB/bDmru/HTKcfAKVhzTG3tIMk0wZh9elDy1dpjGbnOUyv6rjcjHtHZByVanlDovCLW4e5QUCiiDUYvQkwYFqaEDXBjpvIIYcMMFua5rroT7pPB/0FprbjeDT28bO+8mbcyxJbbM3rCQbbIdtsf2WYsJ9pX9ZL/ZlffN++Vde3/uVqe8yc1r9td4N7cG8qrb</latexit><latexit sha1_base64="o8g+mN88D6AAb4esqEJhOAb/UCU=">AAACN3icdVBNT9tAEF0DLTQtbaBHLiNipB5QZKPydYP2wqFSKSKAFKfRejNOFtZra3cMjYx/Vi/9Gb1VvfRQUK/8AzYhSLSic3p6b0bz3otzJS0FwQ9vanrmydPZuWe15y/mX76qLywe2awwAlsiU5k5iblFJTW2SJLCk9wgT2OFx/HZ+5F+fI7Gykwf0jDHTsr7WiZScHJUt/4xIvxC5Qck8HchkhqilNMgjsuD6nOZRiRTtKArHy4GaBD8y91uKU+ry6iPEPqQZAa4UuDL1VO/WUG33giawXjgAVgPwu2NEMIJ02CT2e/Wv0e9TBQpahKKW9sOg5w6JTckhcKqFhUWcy7OeB/bDmru/HTKcfAKVhzTG3tIMk0wZh9elDy1dpjGbnOUyv6rjcjHtHZByVanlDovCLW4e5QUCiiDUYvQkwYFqaEDXBjpvIIYcMMFua5rroT7pPB/0FprbjeDT28bO+8mbcyxJbbM3rCQbbIdtsf2WYsJ9pX9ZL/ZlffN++Vde3/uVqe8yc1r9td4N7cG8qrb</latexit><latexit sha1_base64="o8g+mN88D6AAb4esqEJhOAb/UCU=">AAACN3icdVBNT9tAEF0DLTQtbaBHLiNipB5QZKPydYP2wqFSKSKAFKfRejNOFtZra3cMjYx/Vi/9Gb1VvfRQUK/8AzYhSLSic3p6b0bz3otzJS0FwQ9vanrmydPZuWe15y/mX76qLywe2awwAlsiU5k5iblFJTW2SJLCk9wgT2OFx/HZ+5F+fI7Gykwf0jDHTsr7WiZScHJUt/4xIvxC5Qck8HchkhqilNMgjsuD6nOZRiRTtKArHy4GaBD8y91uKU+ry6iPEPqQZAa4UuDL1VO/WUG33giawXjgAVgPwu2NEMIJ02CT2e/Wv0e9TBQpahKKW9sOg5w6JTckhcKqFhUWcy7OeB/bDmru/HTKcfAKVhzTG3tIMk0wZh9elDy1dpjGbnOUyv6rjcjHtHZByVanlDovCLW4e5QUCiiDUYvQkwYFqaEDXBjpvIIYcMMFua5rroT7pPB/0FprbjeDT28bO+8mbcyxJbbM3rCQbbIdtsf2WYsJ9pX9ZL/ZlffN++Vde3/uVqe8yc1r9td4N7cG8qrb</latexit>

For all orthant boundaries B ⇢ Rmof width 2,

<latexit sha1_base64="1MQmwp0WnrTnnVxJVcx4JvdJLRQ=">AAACMXicdVDLbhNBEJwNr2BeBo5cWthIHJC1G4VHblEiIbgFhEkkr7F6ZnvjUWZnVjO9JNbK35QLX4LEAQ6AuPITjB0jBQR1KlV1q6tL1kYHTtPPydqFi5cuX1m/2rl2/cbNW93bd94G13hFQ+WM8wcSAxltaciaDR3UnrCShvbl0e7C339PPmhn3/CspnGFh1aXWiFHadJ9mTOdcPvceUBjwHmeomWQrrEFek0B+juQh0YGYsgr5KmU7ev5u6oProRjXfAU+hv9R3OYdHvpIF0CzpHHabb1JINspfTECnuT7se8cKqpyLIyGMIoS2set+hZK0PzTt4EqlEd4SGNIrVYURi3y5fn8CAqBZQxduli3qV6fqPFKoRZJePkInT421uI//JGDZfPxq22dcNk1dmhsjHADhb9QaE9KTazSFB5HbOCmqJHxbHlTizh96fwfzLcGGwN0lebve2dVRvr4p64Lx6KTDwV2+KF2BNDocSp+CS+im/Jh+RL8j35cTa6lqx27oo/kPz8BZ6hqUk=</latexit><latexit sha1_base64="1MQmwp0WnrTnnVxJVcx4JvdJLRQ=">AAACMXicdVDLbhNBEJwNr2BeBo5cWthIHJC1G4VHblEiIbgFhEkkr7F6ZnvjUWZnVjO9JNbK35QLX4LEAQ6AuPITjB0jBQR1KlV1q6tL1kYHTtPPydqFi5cuX1m/2rl2/cbNW93bd94G13hFQ+WM8wcSAxltaciaDR3UnrCShvbl0e7C339PPmhn3/CspnGFh1aXWiFHadJ9mTOdcPvceUBjwHmeomWQrrEFek0B+juQh0YGYsgr5KmU7ev5u6oProRjXfAU+hv9R3OYdHvpIF0CzpHHabb1JINspfTECnuT7se8cKqpyLIyGMIoS2set+hZK0PzTt4EqlEd4SGNIrVYURi3y5fn8CAqBZQxduli3qV6fqPFKoRZJePkInT421uI//JGDZfPxq22dcNk1dmhsjHADhb9QaE9KTazSFB5HbOCmqJHxbHlTizh96fwfzLcGGwN0lebve2dVRvr4p64Lx6KTDwV2+KF2BNDocSp+CS+im/Jh+RL8j35cTa6lqx27oo/kPz8BZ6hqUk=</latexit><latexit sha1_base64="1MQmwp0WnrTnnVxJVcx4JvdJLRQ=">AAACMXicdVDLbhNBEJwNr2BeBo5cWthIHJC1G4VHblEiIbgFhEkkr7F6ZnvjUWZnVjO9JNbK35QLX4LEAQ6AuPITjB0jBQR1KlV1q6tL1kYHTtPPydqFi5cuX1m/2rl2/cbNW93bd94G13hFQ+WM8wcSAxltaciaDR3UnrCShvbl0e7C339PPmhn3/CspnGFh1aXWiFHadJ9mTOdcPvceUBjwHmeomWQrrEFek0B+juQh0YGYsgr5KmU7ev5u6oProRjXfAU+hv9R3OYdHvpIF0CzpHHabb1JINspfTECnuT7se8cKqpyLIyGMIoS2set+hZK0PzTt4EqlEd4SGNIrVYURi3y5fn8CAqBZQxduli3qV6fqPFKoRZJePkInT421uI//JGDZfPxq22dcNk1dmhsjHADhb9QaE9KTazSFB5HbOCmqJHxbHlTizh96fwfzLcGGwN0lebve2dVRvr4p64Lx6KTDwV2+KF2BNDocSp+CS+im/Jh+RL8j35cTa6lqx27oo/kPz8BZ6hqUk=</latexit>

Prx⇠{±1}n

[Ax 2 B ] .<latexit sha1_base64="6b2WMCRdieGLyKzZTBxVhVqwG/M=">AAACQnicdVDLSgMxFM34tr6qLt0Ei+BCyoz43GnduKxgVWzGkklTDeYxJBmxhPk3N/6AO3/AjQsVty7MtBVU9EK4h3POJfeeJOXM2DB8DIaGR0bHxicmS1PTM7Nz5fmFE6MyTWiDKK70WYIN5UzShmWW07NUUywSTk+T64NCP72h2jAlj203pbHAl5J1GMHWU63yORLYXqnU9boWrq7zvOVQonjbdIVv7jZHhgnkUCpghPILmTfR2j78aYGISVhDazFEnBrjB2CrXAmrYa/gN7AZRrtbEYwGTAUMqt4qP6C2Ipmg0hKOjWlGYWpjh7VlhNO8hDJDU0yu8SVteiixoCZ2vQxyuOKZNuwo7Z+0sMd+n3BYmGJb7ywuNb+1gvxLa2a2sxM7JtPMUkn6H3UyDq2CRaCwzTQllnc9wEQzvyskV1hjYn3sJR/C16Xwf9BYr+5Ww6ONyl5tkMYEWALLYBVEYBvsgUNQBw1AwB14Ai/gNbgPnoO34L1vHQoGM4vgRwUfn3DHsxY=</latexit><latexit sha1_base64="6b2WMCRdieGLyKzZTBxVhVqwG/M=">AAACQnicdVDLSgMxFM34tr6qLt0Ei+BCyoz43GnduKxgVWzGkklTDeYxJBmxhPk3N/6AO3/AjQsVty7MtBVU9EK4h3POJfeeJOXM2DB8DIaGR0bHxicmS1PTM7Nz5fmFE6MyTWiDKK70WYIN5UzShmWW07NUUywSTk+T64NCP72h2jAlj203pbHAl5J1GMHWU63yORLYXqnU9boWrq7zvOVQonjbdIVv7jZHhgnkUCpghPILmTfR2j78aYGISVhDazFEnBrjB2CrXAmrYa/gN7AZRrtbEYwGTAUMqt4qP6C2Ipmg0hKOjWlGYWpjh7VlhNO8hDJDU0yu8SVteiixoCZ2vQxyuOKZNuwo7Z+0sMd+n3BYmGJb7ywuNb+1gvxLa2a2sxM7JtPMUkn6H3UyDq2CRaCwzTQllnc9wEQzvyskV1hjYn3sJR/C16Xwf9BYr+5Ww6ONyl5tkMYEWALLYBVEYBvsgUNQBw1AwB14Ai/gNbgPnoO34L1vHQoGM4vgRwUfn3DHsxY=</latexit><latexit sha1_base64="6b2WMCRdieGLyKzZTBxVhVqwG/M=">AAACQnicdVDLSgMxFM34tr6qLt0Ei+BCyoz43GnduKxgVWzGkklTDeYxJBmxhPk3N/6AO3/AjQsVty7MtBVU9EK4h3POJfeeJOXM2DB8DIaGR0bHxicmS1PTM7Nz5fmFE6MyTWiDKK70WYIN5UzShmWW07NUUywSTk+T64NCP72h2jAlj203pbHAl5J1GMHWU63yORLYXqnU9boWrq7zvOVQonjbdIVv7jZHhgnkUCpghPILmTfR2j78aYGISVhDazFEnBrjB2CrXAmrYa/gN7AZRrtbEYwGTAUMqt4qP6C2Ipmg0hKOjWlGYWpjh7VlhNO8hDJDU0yu8SVteiixoCZ2vQxyuOKZNuwo7Z+0sMd+n3BYmGJb7ywuNb+1gvxLa2a2sxM7JtPMUkn6H3UyDq2CRaCwzTQllnc9wEQzvyskV1hjYn3sJR/C16Xwf9BYr+5Ww6ONyl5tkMYEWALLYBVEYBvsgUNQBw1AwB14Ai/gNbgPnoO34L1vHQoGM4vgRwUfn3DHsxY=</latexit>

§  1-­‐dimensional  LO  +  union  bound:    

§  We  prove                                                    ,  which  we  show  is  Pght      

§  Need  various  technical  extensions  for  our  purposes    

O(m/pn)

<latexit sha1_base64="FOYejs0cKk8a5V5ZFTu9f/hu+ew=">AAAB83icdVBNS8NAEJ34WetX1aOXxSLUS03Er96KXrxZwdhCG8pmu2mXbjbp7qZQQn+HFw8qXv0z3vw3btsIVfTBwOO9GWbm+TFnStv2p7WwuLS8sppby69vbG5tF3Z2H1SUSEJdEvFINnysKGeCupppThuxpDj0Oa37/euJXx9SqVgk7vUopl6Iu4IFjGBtJO+2FB631EDqVIyP2oWiXbanQHPkzHYq5w5yMqUIGWrtwkerE5EkpEITjpVqOnasvRRLzQin43wrUTTGpI+7tGmowCFVXjo9eowOjdJBQSRNCY2m6vxEikOlRqFvOkOse+q3NxH/8pqJDi69lIk40VSQ2aIg4UhHaJIA6jBJieYjQzCRzNyKSA9LTLTJKW9C+P4U/U/ck3KlbN+dFqtXWRo52IcDKIEDF1CFG6iBCwQG8AjP8GINrSfr1XqbtS5Y2cwe/ID1/gXOqZGt</latexit><latexit sha1_base64="FOYejs0cKk8a5V5ZFTu9f/hu+ew=">AAAB83icdVBNS8NAEJ34WetX1aOXxSLUS03Er96KXrxZwdhCG8pmu2mXbjbp7qZQQn+HFw8qXv0z3vw3btsIVfTBwOO9GWbm+TFnStv2p7WwuLS8sppby69vbG5tF3Z2H1SUSEJdEvFINnysKGeCupppThuxpDj0Oa37/euJXx9SqVgk7vUopl6Iu4IFjGBtJO+2FB631EDqVIyP2oWiXbanQHPkzHYq5w5yMqUIGWrtwkerE5EkpEITjpVqOnasvRRLzQin43wrUTTGpI+7tGmowCFVXjo9eowOjdJBQSRNCY2m6vxEikOlRqFvOkOse+q3NxH/8pqJDi69lIk40VSQ2aIg4UhHaJIA6jBJieYjQzCRzNyKSA9LTLTJKW9C+P4U/U/ck3KlbN+dFqtXWRo52IcDKIEDF1CFG6iBCwQG8AjP8GINrSfr1XqbtS5Y2cwe/ID1/gXOqZGt</latexit><latexit sha1_base64="FOYejs0cKk8a5V5ZFTu9f/hu+ew=">AAAB83icdVBNS8NAEJ34WetX1aOXxSLUS03Er96KXrxZwdhCG8pmu2mXbjbp7qZQQn+HFw8qXv0z3vw3btsIVfTBwOO9GWbm+TFnStv2p7WwuLS8sppby69vbG5tF3Z2H1SUSEJdEvFINnysKGeCupppThuxpDj0Oa37/euJXx9SqVgk7vUopl6Iu4IFjGBtJO+2FB631EDqVIyP2oWiXbanQHPkzHYq5w5yMqUIGWrtwkerE5EkpEITjpVqOnasvRRLzQin43wrUTTGpI+7tGmowCFVXjo9eowOjdJBQSRNCY2m6vxEikOlRqFvOkOse+q3NxH/8pqJDi69lIk40VSQ2aIg4UhHaJIA6jBJieYjQzCRzNyKSA9LTLTJKW9C+P4U/U/ck3KlbN+dFqtXWRo52IcDKIEDF1CFG6iBCwQG8AjP8GINrSfr1XqbtS5Y2cwe/ID1/gXOqZGt</latexit>

   

     {  x  :  Ax  ≤  b  }  \  {  x  :  Ax  ≤  b−2  }  

O(

plogm/

pn)

<latexit sha1_base64="upnZ1H/v78hT/WIMJAK9ydictHQ=">AAACAXicdVDLSsNAFJ3UV62vqCtxM1iEuqmJ+Oqu6MadFYwtNKFMppN26GQSZyZCCcGNv+LGhYpb/8Kdf+O0jVBFD1w4c869zL3HjxmVyrI+jcLM7Nz8QnGxtLS8srpmrm/cyCgRmDg4YpFo+UgSRjlxFFWMtGJBUOgz0vQH5yO/eUeEpBG/VsOYeCHqcRpQjJSWOubWZcWVt0KlLot6MMz2Jy+e7XXMslW1xoBT5Miya8c2tHOlDHI0OuaH241wEhKuMENStm0rVl6KhKKYkazkJpLECA9Qj7Q15Sgk0kvHJ2RwVytdGERCF1dwrE5PpCiUchj6ujNEqi9/eyPxL6+dqODUSymPE0U4nnwUJAyqCI7ygF0qCFZsqAnCgupdIe4jgbDSqZV0CN+Xwv+Jc1CtVa2rw3L9LE+jCLbBDqgAG5yAOrgADeAADO7BI3gGL8aD8WS8Gm+T1oKRz2yCHzDevwCzn5cy</latexit><latexit sha1_base64="upnZ1H/v78hT/WIMJAK9ydictHQ=">AAACAXicdVDLSsNAFJ3UV62vqCtxM1iEuqmJ+Oqu6MadFYwtNKFMppN26GQSZyZCCcGNv+LGhYpb/8Kdf+O0jVBFD1w4c869zL3HjxmVyrI+jcLM7Nz8QnGxtLS8srpmrm/cyCgRmDg4YpFo+UgSRjlxFFWMtGJBUOgz0vQH5yO/eUeEpBG/VsOYeCHqcRpQjJSWOubWZcWVt0KlLot6MMz2Jy+e7XXMslW1xoBT5Miya8c2tHOlDHI0OuaH241wEhKuMENStm0rVl6KhKKYkazkJpLECA9Qj7Q15Sgk0kvHJ2RwVytdGERCF1dwrE5PpCiUchj6ujNEqi9/eyPxL6+dqODUSymPE0U4nnwUJAyqCI7ygF0qCFZsqAnCgupdIe4jgbDSqZV0CN+Xwv+Jc1CtVa2rw3L9LE+jCLbBDqgAG5yAOrgADeAADO7BI3gGL8aD8WS8Gm+T1oKRz2yCHzDevwCzn5cy</latexit><latexit sha1_base64="upnZ1H/v78hT/WIMJAK9ydictHQ=">AAACAXicdVDLSsNAFJ3UV62vqCtxM1iEuqmJ+Oqu6MadFYwtNKFMppN26GQSZyZCCcGNv+LGhYpb/8Kdf+O0jVBFD1w4c869zL3HjxmVyrI+jcLM7Nz8QnGxtLS8srpmrm/cyCgRmDg4YpFo+UgSRjlxFFWMtGJBUOgz0vQH5yO/eUeEpBG/VsOYeCHqcRpQjJSWOubWZcWVt0KlLot6MMz2Jy+e7XXMslW1xoBT5Miya8c2tHOlDHI0OuaH241wEhKuMENStm0rVl6KhKKYkazkJpLECA9Qj7Q15Sgk0kvHJ2RwVytdGERCF1dwrE5PpCiUchj6ujNEqi9/eyPxL6+dqODUSymPE0U4nnwUJAyqCI7ygF0qCFZsqAnCgupdIe4jgbDSqZV0CN+Xwv+Jc1CtVa2rw3L9LE+jCLbBDqgAG5yAOrgADeAADO7BI3gGL8aD8WS8Gm+T1oKRz2yCHzDevwCzn5cy</latexit>

~<latexit sha1_base64="0mgXs7qU24tVY73fsygkWKmFsY8=">AAAB7HicdZDLSgMxFIbPeK31VnXpJlgEV0NGvHVXdOOygtMW2qFk0rSNzWSGJFMoQ9/BjQsVtz6QO9/GtB1FRX8IHL7/HHLOHyaCa4Pxu7OwuLS8slpYK65vbG5tl3Z26zpOFWU+jUWsmiHRTHDJfMONYM1EMRKFgjXC4dXUb4yY0jyWt2acsCAifcl7nBJjUb09YjSbdEpl7J5ir3LmIezimdAX8XJShly1Tumt3Y1pGjFpqCBatzycmCAjynAq2KTYTjVLCB2SPmvZUpKI6SCbbTtBh5Z0US9W9kmDZvT7REYircdRaDsjYgb6tzeFf3mt1PQugozLJDVM0vlHvVQgE6Pp6ajLFaNGjG1BqOJ2V0QHRBFqbEBFG8Lnpej/wj92Ky6+OSlXL/M0CrAPB3AEHpxDFa6hBj5QuIN7eIQnJ3YenGfnZd664OQze/BDzusHf+qPRw==</latexit><latexit sha1_base64="0mgXs7qU24tVY73fsygkWKmFsY8=">AAAB7HicdZDLSgMxFIbPeK31VnXpJlgEV0NGvHVXdOOygtMW2qFk0rSNzWSGJFMoQ9/BjQsVtz6QO9/GtB1FRX8IHL7/HHLOHyaCa4Pxu7OwuLS8slpYK65vbG5tl3Z26zpOFWU+jUWsmiHRTHDJfMONYM1EMRKFgjXC4dXUb4yY0jyWt2acsCAifcl7nBJjUb09YjSbdEpl7J5ir3LmIezimdAX8XJShly1Tumt3Y1pGjFpqCBatzycmCAjynAq2KTYTjVLCB2SPmvZUpKI6SCbbTtBh5Z0US9W9kmDZvT7REYircdRaDsjYgb6tzeFf3mt1PQugozLJDVM0vlHvVQgE6Pp6ajLFaNGjG1BqOJ2V0QHRBFqbEBFG8Lnpej/wj92Ky6+OSlXL/M0CrAPB3AEHpxDFa6hBj5QuIN7eIQnJ3YenGfnZd664OQze/BDzusHf+qPRw==</latexit><latexit sha1_base64="0mgXs7qU24tVY73fsygkWKmFsY8=">AAAB7HicdZDLSgMxFIbPeK31VnXpJlgEV0NGvHVXdOOygtMW2qFk0rSNzWSGJFMoQ9/BjQsVtz6QO9/GtB1FRX8IHL7/HHLOHyaCa4Pxu7OwuLS8slpYK65vbG5tl3Z26zpOFWU+jUWsmiHRTHDJfMONYM1EMRKFgjXC4dXUb4yY0jyWt2acsCAifcl7nBJjUb09YjSbdEpl7J5ir3LmIezimdAX8XJShly1Tumt3Y1pGjFpqCBatzycmCAjynAq2KTYTjVLCB2SPmvZUpKI6SCbbTtBh5Z0US9W9kmDZvT7REYircdRaDsjYgb6tzeFf3mt1PQugozLJDVM0vlHvVQgE6Pp6ajLFaNGjG1BqOJ2V0QHRBFqbEBFG8Lnpej/wj92Ky6+OSlXL/M0CrAPB3AEHpxDFa6hBj5QuIN7eIQnJ3YenGfnZd664OQze/BDzusHf+qPRw==</latexit>

Page 48: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

Recap  of  proof  structure  

1.  A  useful  decomposiPon  of  polytopes  

2.  “Smooth  version”  of  the  problem  

3.  Proving  the  smooth  version  

4.  Going  from  smooth  version  to  actual  version  

≈  1  

≈  0  

Page 49: Fooling’Polytopes’theory.stanford.edu/~liyang/polytopes.pdf · Fooling’Polytopes’ Li/Yang’Tan’(Stanford)’ Jointwork’with’Ryan’O’Donnell’ (CMU)’and’Rocco’Servedio’(Columbia)’

§  Previous  best  seed  length  had  linear  dependence  on  m  

§  Many  interesPng  future  direcPons:    

§  Other  complexity  measures  of  polytopes?  

§  ConnecPons  to  extension  complexity?  

§  PRGs  for  other  geometric  sets?  

§  PRG  for  all  convex  sets?    

Summary  

An  ε-­‐PRG  for  m-­‐facet  polytopes  over  {0,1}n  with  seed  length:  

Our  main  result  

of  size  n                                polylog(m)  Discrepancy  set  

poly(log  m,  1/ε)      log  n      .