题目：A contractive inequality for functions on the boolean cube

主讲人：Alex Samorodnitsky

时间：2020年11月16日14：00-15：00

地址： ZOOM会议650 7606 7714

摘要：We will describe a contractive inequality for functions on the boolean cube, upper-bounding the l_p norm of the image of a function F under the noise operator by the expected norm of a projection of F on a random coordinate subset of a certain size. We will use this inequality to obtain new bounds on the weight distribution of Reed Muller codes of positive rate, deducing that a Reed-Muller code C of rate R decodes errors on BSC(p) with high probability if R < 1 - log_2( 1 + sqrt( 4p(1-p) ) ). based in part on a joint work with ori sberlo.

主讲人简介：Alex Samorodnitsky is an Associate Professor of Computer Science at the Hebrew University of Jerusalem. He works in theoretical computer science and is also interested in coding theory and combinatorics. Most of Samorodnitsky’s work deals with investigating various properties of Boolean functions—very basic objects that can be interpreted as belonging to surprisingly many mathematical settings. Samorodnitsky studied at the Hebrew University in Jerusalem, where he earned his bachelor‘s, master’s, and doctoral degrees. He was a postdoctoral fellow at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University and at the Institute for Advanced Study in Princeton, and a visiting scientist at Microsoft Research New England.

邀请人：胡思煌