文章基本信息

标题：Testing of exponentially large codes, by a new extension to Weil bound for character sums
本地全文：下载
作者：Tali Kaufman, Shachar Lovett
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this work we consider linear codes which are locally testable in a sublinear number of queries. We give the first general family of locally testable codes of exponential size. Previous results of this form were known only for codes of quasi-polynomial size (e.g. Reed-Muller codes). We accomplish this by showing that any affine invariant code over Fpn of size pp(n) is locally testable using poly(logpn) queries. Previous general result for affine invariant codes were known only for sparse codes, i.e. codes of size pO(n). The main new ingredients used in our proof are a new extension of the Weil bound for character sums, and a Fourier-analytic approach for estimating the weight distribution of affine invariant codes.
关键词：affine invariant codes, local testing, weil bound