演讲人： Ning Xie MIT
时间： 2009-04-09 16:00-2009-04-09 17:00
地点：FIT Building 4-603, Tsinghua University
课件下载：点击下载
内容：

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions.

The previously best bounds for $\textsc{rej}(\epsilon)$ were obtained by Bellare, Coppersmith, H{ {a}}stad, Kiwi and Sudan. They used Fourier analysis to show that $\textsc{rej}(\epsilon) \geq \e$ for every $0 \leq \epsilon \leq
\frac{1}{2}$. They also conjectured that this bound might not be tight for $\epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $\textsc{rej}(\epsilon) \geq \epsilon$ by an additive constant that depends only on $\epsilon$: $\textsc{rej}(\epsilon) \geq \epsilon + \min \{1376\epsilon^{3}(1-2\epsilon)^{12}, \frac{1}{4}\epsilon(1-2\epsilon)^{4}\}$,  for every $0 \leq  \epsilon \leq \frac{1}{2}$. Our analysis is based on a relationship between $\textsc{rej}(\epsilon)$ and the weight distribution of a coset of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

Joint work with Tali Kaufman and Simon Litsyn.

个人简介:
Mr.Ning Xie is a Ph.D. student in MIT, and his research interest lies in complexity theory.