讨论班和报告
 Learning low-degree functions on the discrete hypercube
发布人:许全华  发布时间:2022-11-30   浏览次数:118

题目:Learning low-degree functions on the discrete hypercube


报告人Alexandros EskenazisCentre national de la recherche scientifique, CNRS


时间:2022年12月7日(星期三),16:00-17:30

 

Zoom会议:会议号:882 8540 7533,会议密码:028422


会议链接:https://zoom.us/j/88285407533?pwd=NFlsWlZlb2F3c3VmMHBqOXVud1NpQT09

  

摘要:Let f be an unknown function on the n-dimensional discrete hypercube. How many values of f do we need in order to approximately reconstruct the function? In this talk, we shall discuss the random query model for this fundamental problem from computational learning theory. We will explain a newly discovered connection with a family of polynomial inequalities going back to Littlewood (1930) which will in turn allow us to derive sharper estimates for the query complexity of this model, exponentially improving those which follow from the classical Low-Degree Algorithm of Linial, Mansour and Nisan (1989), while maintaining a running time of the same order. Time permitting, we will also show a matching information-theoretic lower bound. Based on joint works with Paata Ivanisvili (UC Irvine) and Lauritz Streck (Cambridge).


  

  

更多相关信息请参见泛函分析研讨班网页