Jiyou Li


Shanghai Jiaotong University


Tuesday, January 22, 2013 - 2:00pm to 3:00pm




A subset $X$ in $\{0,1\}^n$ is a called an $\epsilon$-biased set if for any nonempty subset $T\subseteq [n]$ the following condition holds. Randomly choosing an element $x\in X$, the parity of its T-coordinates sum has bias at most $\epsilon$. This concept is essentially equivalent or close to expanders, pseudorandom generators and linear codes of certain parameters. For instance, viewing $X$ as a generator matrix, an $\epsilon$-biased set is equivalent to an $[|X|, n]_2$-linear code of relative distance at least $1/2-\epsilon$. For fixed $n$ and $\epsilon$, it's a challenging problem to construct smallest $\epsilon$-biased sets. In this talk we will first introduce several known constructions of $\epsilon$-bias sets with the methods from number theory and geometrical coding theory. Then we will present a construction with a conjecture, which is closely related to the subset sum problem over prime fields.