**Speaker: ** Ning Xie MIT

**Time: ** 2009-04-09 16:00-2009-04-09 17:00

**Venue: **FIT Building 4-603, Tsinghua University

**Download: **Click!

**Abstract: **

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.

**Short Bio: **

Mr.Ning Xie is a Ph.D. student in MIT, and his research interest lies in complexity theory.