欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
The p -subspace sketch problem with applications to non-embeddability
时间  Datetime
2019-05-30 14:30 — 16:00 
地点  Venue
Large Conference Room(706)
报告人  Speaker
Yi Li (李翼)
单位  Affiliation
Nanyang Technological University
邀请人  Host
数学系
报告摘要  Abstract

Consider the classical problem of finding the smallest n such that any d-dimensional subspace of Lp(0,1) can be (1+?)-embedded into (Rn,||.||p). We show that when p≥1 is not an even integer and dClog(1/?), it is necessary that nC′/(?2polylog(1/?)), which is the optimal dependence on eps up to polylogarithmic factors, extending the previously known best eps-dependence of 1/?2−o(1) for p=1 to a general p. The proof uses techniques in communication complexity by studying the following ?p-subspace sketch problem. There are two players Alice and Bob. Alice has the subspace and sends a message to Bob such that Bob can approximate the ellp norm of any vector in the subspace. We show that the message length needs to be at least d/(?2polylog(1/?)) bits, from which the embedding dimension lower bound follows.

http://math.sjtu.edu.cn/conference/Bannai/2019/talk.php?20190531A