文章基本信息

标题：Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
本地全文：下载
作者：Madhav Jha ; Sofya Raskhodnikova
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：and Spielman (IEEE IT, 1996) showed that any (cd) -regular expander code with expansion parameter 43 is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007) proved that expansion parameter 32+13c is sufficient to correct a constant fraction of errors in \emph{polynomial time} using LP decoding. In this work we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in \emph{linear time} and works for any expansion parameter 32−16c.
关键词：decoding, Error-correcting codes, expander codes, LDPC codes