■
- V. Guruswami, C. Umans and S. Vadhan
- "Extractors and condensers from univariate polynomials."
CCC 2007に採録された論文．最適なパラメータを達成するrandomness extractorとloss-less condenserを以前の多変数多項式符号(Reed-Muller)に基づく構成とは異なり，一変数多項式に基づく符号を使って達成している．既に最適なパラメータを達成するrandomness extractorは知られていたが，*1それに比べて非常に単純化されているのが特徴．
具体的にはReed-Solomon符号の亜種であるParvaresh-Vardy符号*2（とalmost 2-universal hash）を用いてloss-less condenserを構成し，それを利用することでextractorの構成を与えている．
