Some known results Results on learnability*1,testability*2,etc. A structural result by Green and Sanders. 。Theorem*3.f:{0,1r→{0,1}can be written as - ±1v where L1 =fl,and Vi's are subspaces. Question:Improve the doubly exponential bound? *1.Kushilevitz,Mansour,SIAMJ.on Computing,1993. *2.Gopalan,O'Donnell,Servedio,Shpilka,Wimmer,SIAM J.on Computing,2011. *3.Green and Sanders.Geometric and Functional Analysis,2008. 3Some known results • Results on learnability* 1 ,testability* 2 , etc. • A structural result by Green and Sanders. • Theorem* 3 . ∀𝑓: 0,1 𝑛 → {0,1} can be written as 𝑓 = σ𝑖=1 2 2 𝑂 𝐿1 4 ±𝟏𝑉𝑖 , where 𝐿1 = 𝑓መ 1 and 𝑉𝑖 ’s are subspaces. • Question: Improve the doubly exponential bound? *1. Kushilevitz, Mansour, SIAM J. on Computing, 1993. *2. Gopalan, O’Donnell, Servedio, Shpilka, Wimmer, SIAM J. on Computing, 2011. *3. Green and Sanders. Geometric and Functional Analysis, 2008. 3