报告名称：An Optimal “Ain’t Over till It’s Over” Theorem

主讲人：Pei Wu (Institute for Advanced Study)

时间：9月21日（星期三）上午9: 00--11:00

地点：线上Zoom会议

联系人：常帆 cf25264@163.com

报告摘要:

We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let f be a Boolean function such that the variance of f is Ω(1) and all its individual influences are bounded by τ. We show that when restricting all but a ρ = ˜Ω((log 1/τ)⁻¹) fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function $AND_{n/C\log n} \circ OR_{C\log n}$.

We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability 1-o(1). This gives a sharp version of the ``it ain't over till it's over'' theorem due to Mossel, O'Donnell, and Oleszkiewicz. Our proof is discrete, and avoids the use of the invariance principle.

Joint work with Ronen Eldan and Avi Wigderson.

个人简介:

Pei obtained his Ph.D. degree from UCLA. He is currently a postdoc at Institute for Advanced Study.

邀请人：王光辉教授